# Reducing Coverage Depth in DNA Storage:
A Combinatorial Perspective on Random Access Efficiency

Anina Gruica1, Daniella Bar-Lev2, Alberto Ravagnani1, and Eitan Yaakobi2
{a.gruica<EMAIL_ADDRESS>{daniellalev<EMAIL_ADDRESS>1Dept. of Mathematics and Computer Science, Eindhoven University of
Technology, the Netherlands  2Faculty of Computer Science, Technion—Israel
Institute of Technology, Israel

###### Abstract

We investigate the fundamental limits of the recently proposed _random access
coverage depth problem_ for DNA data storage. Under this paradigm, it is
assumed that the user information consists of $k$ information strands, which
are encoded into $n$ strands via some generator matrix $G$. In the sequencing
process, the strands are read uniformly at random, since each strand is
available in a large number of copies. In this context, the random access
coverage depth problem refers to the expected number of reads (i.e., sequenced
strands) until it is possible to decode a specific information strand, which
is requested by the user. The goal is to minimize the maximum expectation over
all possible requested information strands, and this value is denoted by
$T_{\max}(G)$. This paper introduces new techniques to investigate the random
access coverage depth problem, which capture its combinatorial nature. We
establish two general formulas to find $T_{\max}(G)$ for arbitrary matrices.
We introduce the concept of _recovery balanced codes_ and combine all these
results and notions to compute $T_{\max}(G)$ for MDS, simplex, and Hamming
codes. We also study the performance of modified systematic MDS matrices and
our results show that the best results for $T_{\max}(G)$ are achieved with a
specific mix of encoded strands and replication of the information strands.

##  I Introduction

With the demand for storage capacity consistently outpacing the capabilities
of existing technologies to store it [1], there is a critical need for
alternative approaches. In response to this pressing challenge, DNA storage
emerges as a promising solution for long-term data storage, offering
exceptional density and durability [2, 3]. A typical DNA storage system is
composed of three main components: DNA synthesis, storage containers, and DNA
sequencing. Initially, synthetic DNA strands, or _oligos_ , are created to
encode the user’s information. These strands are then stored in an unordered
manner in a storage container. Subsequently, DNA sequencing translates the
stored strands into digital sequences, called _reads_ , that should be decoded
back to the user’s information. Due to current technology limitations, this
process results in multiple noisy copies for each designed strand, that are
obtained without order.

While several works demonstrated the potential of DNA as a storage medium [4,
5, 6, 7, 8, 9, 10], the efficiency of DNA sequencers remains a bottleneck,
with slow throughput and high costs compared to alternative storage
technologies [11, 12, 2]. This bottleneck is intricately tied to the concept
of the _coverage depth_ [13], defined as the ratio between the number of
sequenced reads and the number of designed DNA strands. Reducing the coverage
depth presents an opportunity for a drastic improvement in latency and cost
reduction [14, 15, 16, 17].

Our point of departure in this paper is the recent work [16] which initiates
the study of the so-called _DNA coverage depth problem_. The aim in this
problem is to reduce the cost and latency of DNA sequencing, by studying the
expected number of reads that are required in order to retrieve the user’s
information. The authors of [16] investigated both the non-random and random
access scenarios. While in the former the goal is retrieve _all_ the user’s
information, the latter considers the random access case of retrieving only a
_single_ strand. Assume the $k$ information strands (representing the data)
are encoded into $n$ strands. Then, by drawing connection to the coupon
collector problem [18, 19, 20, 21], if the $k$ information strands are encoded
by an MDS code, then the expected number of reads to decode all $k$
information strands is $H_{n}-H_{n-k}$, where $H_{i}$ is the $i$-th harmonic
number. This result is optimal for minimizing the expected number of reads.
Using the same MDS code for the random access case, it was shown that the
expected number of reads is $k$, however this result is far from optimality.
Several more codes also obtained the same result or even a larger expectation
value than $k$.

A related concept was also explored in [15], where the authors investigated
the trade-offs between the reading costs, directly associated with coverage
depth, and the writing costs. The non-random access scenario of the DNA
coverage depth problem was further extended in [17] to support the setup of
the combinatorial composite of DNA shortmers [22]. Another extension to the
random access setup was studied in [23], however the goal is not decode a
single strand but a group of strands that constitute a single file.

Motivated by the results and observations in [16], in this work we extend the
research of the random access coverage depth problem. The rest of the paper is
organized as follows. In Section II, we formally define the random access
coverage depth problem. Section III presents several properties of the random
access expectation and more precisely, gives two general formulas for the
expectation. In Section IV, we show an important observation on the average of
the random access expectation, which is then used in Section V to show that
certain families of codes (MDS, Hamming and simplex) have random access
expectation $k$. Lastly, Section VI presents a method to derive codes for
which their random access expectation is smaller than $k$.

##  II Problem Statement

Throughout this paper, $k$ and $n$ are positive integers with $2\leq k\leq n$,
$q$ denotes a prime power, and $\mathbb{F}_{q}$ is the finite field with $q$
elements. For a positive integer $n$, we let $[n]=\\{1,\ldots,n\\}$ and denote
by $H_{n}$ the $n$-th harmonic number.

We study the expected sample size for uniformly random access queries in DNA
storage systems. In DNA-based storage systems, the data is stored as a
length-$k$ vector of sequences (called strands) of length $\ell$ over the
alphabet $\Sigma=\\{A,C,G,T\\}$. We embed $\Sigma^{\ell}$ into a finite field
$\mathbb{F}_{q}$ and use a $k$-dimensional linear block code
$\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ to encode an information vector
$\smash{\bm{x}=(x_{1},\dots,x_{k})\in(\Sigma^{\ell})^{k}}\subseteq\mathbb{F}_{q}^{k}$
to a decoded vector $\smash{\bm{y}=(y_{1},\dots,y_{n})\in\mathbb{F}_{q}^{n}}$.

To retrieve the stored information at a later time, the strands are amplified
and then sequenced using DNA sequencing technology. This generates multiple
(erroneous) copies for different strands, referred to as _reads_. The output
of the reading process is a multiset of these reads, without any specific
order111The reads can be obtained all together or one after the other,
depending on the specific technology that is being used.. As current prices
and throughput for DNA sequencing still lag behind other archival storage
solutions, reducing the coverage depth required for information recovery is
crucial.

In the random access setup, the goal is to retrieve a single sequence $x_{i}$
for $i\in[k]$. It has been demonstrated [16] that the expected sample size of
a random access query in the DNA storage system can be decreased using an
appropriate coding scheme. We illustrate this concept with the following
example.

######  Example 1.

We wish to store an information vector of size $k=2$, namely
$(x_{1},x_{2})\in\mathbb{F}_{q}^{2}$. Without coding, the expected number
samples that are needed to recover each of the two information symbols is 2
(assuming that the samples are uniformly random). If
$\mathbb{F}_{2}\subseteq\mathbb{F}_{q}$, we can consider the matrix

$G=\begin{pmatrix}1&0&1&0&1\\\ 0&1&0&1&1\\\
\end{pmatrix}\in\mathbb{F}_{2}^{2\times 5}\vspace{-1ex}$

and store the entries of

$(x_{1},x_{2})G=(x_{1},x_{2},x_{1},x_{2},x_{1}+x_{2})\in\mathbb{F}_{q}^{5}.\vspace{-1ex}$

This time, using uniformly random sampling of the five encoded symbols, it can
be shown that the expected number samples that are needed to recover either of
the two information symbols is approximately $1.917<2$. Note that “recovering”
means being able to obtain the original information symbol as a linear
combination of the sampled symbols. For example, if the last two encoded
symbols are sampled, the information symbol $x_{1}$ can be recovered as
$x_{1}=x_{2}+(x_{1}+x_{2})$.

As demonstrated in Example 1, once the $k$ information strands are encoded
using a generator matrix $G\in\mathbb{F}_{q}^{k\times n}$ it is possible to
refer to every read of an encoded strand as reading its corresponding column
in the matrix $G$ and recovering the $i$-th information strand corresponds to
recovering the $i$-th basis vector, that is, it should belong to the span of
the already recovered columns of $G$. Motivated by these observations, we are
now ready to formally define the problem studied in this paper. We note that
in [16], this problem was referred to as the _singleton coverage depth
problem_ (Problem 3) and here we refer to it as the _random access coverage
depth problem_.

######  Problem 1 (The random access coverage depth problem).

Let $G\in\mathbb{F}_{q}^{k\times n}$ be a rank $k$ matrix. Suppose that the
columns of $G$ are drawn uniformly randomly, meaning that each column has
probability $1/n$ of being drawn and columns can be drawn multiple times. For
$i\in[k]$, let $\tau_{i}(G)$ denote the random variable that counts the
minimum number of columns of $G$ that are drawn until the standard basis
vector $e_{i}$ is in their $\mathbb{F}_{q}$-span. Compute the expectation
$\mathbb{E}[\tau_{i}(G)]$ and the maximum expectation
$T_{\max}(G)\triangleq\max_{i\in[k]}\mathbb{E}[\tau_{i}(G)]$. Furthermore, let
$T_{q}(n,k)\triangleq\min_{G\in\mathbb{F}_{q}^{k\times n}}{T_{\max}(G)}$ be
the smallest maximum random access expectation for any rank-$k$ matrix in
$\mathbb{F}_{q}^{k\times n}$ and
$T_{q}(k)\triangleq\liminf_{n\rightarrow\infty}{T_{q}(n,k)}$ the best maximum
random access for any rank-$k$ matrix over $\mathbb{F}_{q}$.

######  Remark 1.

In the sequel, $G\in\mathbb{F}_{q}^{k\times n}$ denotes a rank $k$ matrix and
$\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ the $k$-dimensional code having $G$
as its generator matrix. We do not assume that $G$ is systematic (i.e., that
the first $k$ columns of $G$ form the identity $k\times k$ matrix), unless
otherwise specified. Note that, in contrast with previous approaches, we
mostly focus on generator matrices and not on block codes. This is because the
parameters we consider in this paper do depend on the choice of the generator
matrices and not only on the code.

Studying the values $T_{\max}(G)$, $T_{q}(n,k)$, and $T_{q}(k)$ was initiated
in [16]. It was established that for various codes, such as the identity code,
simple parity code, and systematic MDS codes, for any $i\in[k]$ it follows
that $\mathbb{E}[\tau_{i}(G)]=k$, when $G$ is the systematic generator matrix
for every code. In particular, the result on the identity codes implied that
$T_{q}(k,k)=k$, but finding in general the value of $T_{q}(n,k)$ is an
intriguing question, and first steps towards solving this value were carried
in [16]. Several constructions were presented that achieve maximum expectation
strictly lower than $k$. More specifically, it was show that $T_{q}(k=2)\leq
0.91\cdot 2$, $T_{q}(k=3)\leq 0.89\cdot 3$ and for arbitrary $k$ which is a
multiple of $4$, it holds that $T_{q}(n=2k,k)\leq 0.95k$. Furthermore, two
lower bounds from [16] established that for any $n,k,q$ it holds
$T_{q}(n,k)\geq n-\frac{n(n-k)}{k}(H_{n}-H_{n-k})$ and
$T_{q}(k)\geq\frac{k+1}{2}$.

Despite these valuable contributions, the fundamental limits of the random
access coverage depth problem remain unclear. Specifically, the existing
results lack a comprehensive understanding of the properties that render a
generator matrix optimal for this purpose and in general to calculate the
value $T_{\max}(G)$. In this context, our goal is to contribute to the ongoing
research and identify generator matrices that minimize $T_{\max}(G)$ and help
in determining $T_{q}(n,k)$ and $T_{q}(k)$.

##  III General Formulas for Expectation

In this section, given any matrix $G\in\mathbb{F}_{q}^{k\times n}$, we give
two general formulas for the expected number of reads until one can recover
the $i$-th information strand, namely, for $\mathbb{E}[\tau_{i}(G)]$. This
will allow us to understand which properties of $G$ play a role in the
solution of Problem 1.

######  Definition 1.

We call $S\subseteq[n]$ a recovery set for the $i$-th information strand if
$e_{i}$ is in the span of the columns of $G$ indexed by $S$. We denote by
$\mathcal{R}(i)$ the set of minimal (with respect to inclusion) recovery sets
for the $i$-th information strand. We say that “we recovered the $i$-th
strand” if we drew columns of $G$ whose indices form a recovery set for $i$.

By definition, the columns of $G$ are in one-to-one correspondence with the
encoded strands. Denote the $j$-th column of $G$ by $g_{j}$ for $j\in[n]$ and
for $i\in[n]$ and $0\leq s\leq n$, let

$\displaystyle\alpha_{i}(s):={|\\{S\subseteq[n]:|S|=s,\,e_{i}\in\langle
g_{j}:j\in S\rangle\\}|}.$

The first formula we establish for $\mathbb{E}[\tau_{i}(G)]$ uses the values
$\alpha_{i}(s)$ we just introduced.

######  Lemma 1.

For $G\in\mathbb{F}_{q}^{k\times n}$ and for all $i\in[k]$ we have

$\displaystyle\mathbb{E}[\tau_{i}(G)]=nH_{n}-\sum_{s=1}^{n-1}\displaystyle\frac{\alpha_{i}(s)}{\binom{n-1}{s}}.\vspace{-1.5ex}$

###### Proof.

By definition,

$\displaystyle\mathbb{E}[\tau_{i}(G)]=\sum_{r=1}^{\infty}\Pr[\tau_{i}(G)\geq
r].\vspace{-1ex}$ (1)

For $r\geq 1$, let $\eta_{r}$ be the random variable that denotes the number
of distinct encoded strands that were sampled in the first $r$ draws, where we
set $\eta_{0}=0$. We have

$\Pr[\tau_{i}(G)\geq r]=\sum_{s=0}^{n-1}\Pr[\tau_{i}(G)\geq
r\mid\eta_{r-1}=s]\Pr[\eta_{r-1}=s],\vspace{-1ex}$ (2)

where the sum runs only up to $n-1$ since $\Pr[\tau_{i}(G)\geq
r\mid\eta_{r-1}=n]=0$ for all $r\geq 1$. In order to compute the probability
$\Pr[\tau_{i}(G)\geq r\mid\eta_{r-1}=s]$ we note that the number of subsets of
$s$ strands that recover the $i$-th strand is the same as the number of
subsets $S\subseteq[n]$ with $|S|=s$ that have the property that the columns
of $G$ indexed by $S$ contain $e_{i}$ in their span, which is exactly
$\alpha_{i}(s)$. Therefore, the number of sets of cardinality $s$ that do not
recover the $i$-th information strand is $\binom{n}{s}-\alpha_{i}(s)$.
Combining this with (1) and (2) gives

$\displaystyle\mathbb{E}[\tau_{i}(G)]=\sum_{r=1}^{\infty}\sum_{s=0}^{n-1}\left(1-\frac{\alpha_{i}(s)}{\binom{n}{s}}\right)\Pr[\eta_{r-1}=s].$

Using the Inclusion-Exclusion Principle, we further obtain

$\displaystyle\Pr[\eta_{r-1}=s]=\binom{n}{s}\displaystyle\sum_{j=0}^{s}\binom{s}{j}(-1)^{j}\left(\frac{s-j}{n}\right)^{r-1}.$

This gives that $\mathbb{E}[\tau_{i}(G)]$ is equal to

$\displaystyle\sum_{s=0}^{n-1}\left(\binom{n}{s}-{\alpha_{i}(s)}\right)\displaystyle\sum_{j=0}^{s}\binom{s}{j}(-1)^{j}\sum_{r=0}^{\infty}\left(\frac{s-j}{n}\right)^{r}$
$\displaystyle=\sum_{s=0}^{n-1}\left(\binom{n}{s}-{\alpha_{i}(s)}\right)\displaystyle\sum_{j=0}^{s}\binom{s}{j}(-1)^{j}\frac{n}{n-s+j}$
$\displaystyle=\sum_{s=0}^{n-1}\left(\binom{n}{s}-{\alpha_{i}(s)}\right)\displaystyle\frac{1}{\binom{n-1}{s}}=nH_{n}-\sum_{s=0}^{n-1}\displaystyle\frac{\alpha_{i}(s)}{\binom{n-1}{s}},$

where in the second-to-last equality we used the identity

$\displaystyle\sum_{j=0}^{s}\binom{s}{j}(-1)^{j}\frac{n}{n-s+j}=\frac{1}{\binom{n-1}{s}}\quad\mbox{for
$0\leq s\leq n-1$},\vspace{-1ex}$ (3)

which can be shown by induction. Finally, since $\alpha_{i}(0)=0$ for all
$i\in[n]$ we obtain the lemma. ∎

We illustrate how Lemma 1 can be used to compute $\mathbb{E}[\tau_{1}(G)]$ and
$\mathbb{E}[\tau_{2}(G)]$ for the matrix $G$ of Example 1.

######  Example 2.

Let $G$ be as in Example 1. We have

$\displaystyle\alpha_{1}(1)=2,\;\alpha_{1}(2)=9,\;\alpha_{1}(3)=\binom{5}{3},\;\alpha_{1}(4)=\binom{5}{4}.\vspace{-1ex}$

By Lemma 1 we obtain

$\displaystyle\mathbb{E}[\tau_{1}(G)]$
$\displaystyle=5H_{5}-\sum_{s=1}^{4}\displaystyle\frac{\alpha_{1}(s)}{\binom{4}{s}}=\frac{23}{12}\approx
1.917.\vspace{-1ex}$

It is easy to see that for $\tau_{2}(G)$ we have exactly the same numbers, and
thus $\mathbb{E}[\tau_{2}(G)]=23/12$ and $T_{\max}(G)=23/12.$

Using Lemma 1 we can also give an alternative (shorter) proof of [16, Theorem
9].

######  Corollary 1.

Let $G\in\mathbb{F}_{q}^{k\times n}$ be a systematic generator matrix of an
MDS code. We have $T_{\max}(G)=k$.

###### Proof.

Since $G$ is an MDS matrix, every $k$ columns of $G$ are linearly independent.
Thus, for any $i$,

$\displaystyle{\alpha}_{i}(s)=\begin{cases}\binom{n-1}{s-1}\quad&\textnormal{if
$s\in[k-1]$,}\\\ \binom{n}{s}\quad&\textnormal{if $s\geq k$.}\end{cases}$

By Lemma 1 we then have

$\displaystyle\mathbb{E}[\tau_{i}(G)]$
$\displaystyle=nH_{n}-\sum_{s=1}^{k-1}\frac{\binom{n-1}{s-1}}{\binom{n-1}{s}}-\sum_{s=k}^{n-1}\frac{\binom{n}{s}}{\binom{n-1}{s}}$
$\displaystyle=nH_{n}-\sum_{s=1}^{k-1}\frac{s}{n-s}-\sum_{s=k}^{n-1}\frac{n}{n-s},\vspace{-1ex}$

which simplifies to $k$ after straightforward computations. ∎

The other formula for the expectation of the random access problem we will use
in this paper relies on the recovery sets of the information strand and on
their intersection structure.

More precisely, for $i\in[k]$ and $\mathcal{R}(i)=\\{R_{1},\dots,R_{L}\\}$ we
denote by $\beta_{i}(s,j)$ the number of subsets $S\subseteq[L]$ of
cardinality $s$ such that $\bigcup_{h\in S}R_{h}$ has cardinality $j$. In
symbols, $\beta_{i}(s,j)=\left|\\{S\subseteq[L]:|S|=s,\,|\bigcup_{h\in
S}R_{h}|=j\\}\right|$. We then have the following result, which can be
obtained analogously to [16, Corollary 2].

######  Lemma 2.

For $G\in\mathbb{F}_{q}^{k\times n}$ and for $i\in[k]$ it holds that

$\displaystyle\mathbb{E}[\tau_{i}(G)]=n\Big{(}\sum_{j=1}^{n}H_{j}\sum_{s=1}^{L}(-1)^{s+1}\beta_{i}(s,j)\Big{)}.$

Although Lemmas 1 and 2 give general formulas for the expectation
$\mathbb{E}[\tau_{i}(G)]$, they are not necessarily easy to apply. This is
because for general codes it is not immediate to derive the values of
$\alpha_{i}(s)$ or $\beta_{i}(s,j)$, and even if one has their explicit
values, it can be tricky to evaluate the formulas for
$\mathbb{E}[\tau_{i}(G)]$. In particular, although the formulas give insight
about what matters for computing $\mathbb{E}[\tau_{i}(G)]$, it is still
unclear how to use them to find matrices/codes for which the random access
expectation value is below $k$. Yet, in the next section we show how to build
on these results in order to develop deeper insights on achieving codes for
the purpose of expectation below $k$.

##  IV The Average Expectation

In this section we give one of the main results of this paper. We obtain this
result by investigating a random variable that is different, but closely
related to $\tau_{i}(G)$.

######  Notation 1.

For $i\in[n]$, we denote by $\widetilde{\tau}_{i}(G)$ the random variable that
counts the number of columns of $G$ that need to be drawn until the $i$-th
column of $G$ can be recovered, i.e., it belongs to the $\mathbb{F}_{q}$-span
of drawn columns.

If the matrix $G$ is systematic, then $\widetilde{\tau}_{i}(G)={\tau}_{i}(G)$
for all $i\in[k]$. Moreover, it follows from Claim 2 that in contrast to
$\tau_{i}(G)$, $\widetilde{\tau}_{i}(G)$ only depends on the code generated by
$G$. More precisely:

######  Claim 1.

For a code with generator matrices $G,G^{\prime}\in\mathbb{F}_{q}^{k\times n}$
we have
$\mathbb{E}[\widetilde{\tau}_{i}(G)]=\mathbb{E}[\widetilde{\tau}_{i}(G^{\prime})]$
for all $i\in[n]$.

The following result shows that, _on average_ , for any rank $k$ matrix
$G\in\mathbb{F}_{q}^{k\times n}$ the expectation of $\widetilde{\tau}_{i}(G)$
is $k$.

######  Theorem 1.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be a code of dimension $k$ with
generator matrix $G$. We have
$\sum_{i=1}^{n}\mathbb{E}\left[\widetilde{\tau}_{i}(G)\right]=kn.$

To give an intuition for the proof of Theorem 1, we first give an example. We
introduce some new random variables, which we will also use in the proof: For
a generator matrix $G\in\mathbb{F}_{q}^{k\times n}$ and $i\in[k]$ we let
$t_{i}(G)$ be the random variable that governs the number of draws until we
read a new column after having read $i-1$ columns, i.e., a column that is not
a linear combination of the already recovered columns, and we let
$\delta_{i}(G)$ be the random variable that governs the number of columns that
are recovered together with the $i$-th column. We further define the random
variable $T_{i}(G)=\sum_{\ell=1}^{i}t_{\ell}(G)$, which governs the number of
draws until we recovered $i$ linearly independent columns. We observe that

$\displaystyle\sum_{i=1}^{n}\widetilde{\tau}_{i}(G)=\sum_{i=1}^{k}\delta_{i}(G)T_{i}(G)=\sum_{i=1}^{k}\delta_{i}(G)\sum_{\ell=1}^{i}t_{\ell}(G).\vspace{-1ex}$
(4)

######  Example 3.

Let $\mathcal{C}$ be the $q$-ary simplex code of dimension $4$ over
$\mathbb{F}_{2}$ and let $G\in\mathbb{F}_{2}^{4\times 15}$ be its generator
matrix. Note that since the columns of $G$ are all the non-zero vectors in
$\mathbb{F}_{2}^{4}$, every time we read a new (linearly independent) column,
we recover not only this column, but also the sum of this column with any of
the previously recovered columns. Therefore,

$\displaystyle\delta_{1}(G)=1,\,\delta_{2}(G)=2,\,\delta_{3}(G)=4,\,\delta_{4}(G)=8,$
(5)

and since $t_{i}(G)$ is a geometric random variable with success probability
${\left(15-\delta\right)}/15$, where
$\sum_{\ell=1}^{i-1}\delta_{\ell}(G)=\delta$, we have

$\displaystyle\mathbb{E}[t_{1}(G)]={15}/{15},\;\mathbb{E}[t_{2}(G)]={15}/{14},$
$\displaystyle\mathbb{E}[t_{3}(G)]={15}/{12},\;\mathbb{E}[t_{4}(G)]={15}/{8}.$
(6)

Combining (4) with (5) and (3), we obtain

$\displaystyle\sum_{i=1}^{15}\mathbb{E}\left[\widetilde{\tau}_{i}(G)\right]$
$\displaystyle=\sum_{i=1}^{4}\delta_{i}(G)\sum_{\ell=1}^{i}\mathbb{E}\left[t_{\ell}(G)\right]=4\cdot
15=60.\vspace{-1ex}$

We can now prove Theorem 1 using analogous random variables to the ones used
in Example 3.

###### Proof of Theorem 1.

For $\ell\in[k]$ we let $\Delta_{\ell}:=\sum_{i=1}^{\ell-1}\delta_{i}(G)$.
Notice that if $\Delta_{\ell}=\delta$, then $t_{i}(G)$ is a geometric random
variable with success probability ${\left(n-\delta\right)}/n$ and so

$\displaystyle\mathbb{E}\Big{[}t_{i}(G)\,\big{|}\,\Delta_{\ell}=\delta\Big{]}=\frac{n}{n-\delta}\;\textnormal{
for all $i\in[k]$}.$ (7)

Rewriting (4) we have

$\displaystyle\sum_{i=1}^{n}\widetilde{\tau}_{i}(G)=\sum_{\ell=1}^{k}t_{\ell}(G)\sum_{i=\ell}^{k}\delta_{i}(G)=\sum_{\ell=1}^{k}t_{\ell}(G)\big{(}n-\Delta_{\ell}\big{)},$

where we used that $\sum_{i=1}^{k}\delta_{i}(G)=n$ and so
$\sum_{i=\ell}^{k}\delta_{i}(G)=n-\Delta_{\ell}$. Summing over all possible
outcomes of $\Delta_{\ell}$ for $\ell\in[k]$, by the law of total expectation,
have that $\mathbb{E}\left[\sum_{i=1}^{n}\widetilde{\tau}_{i}(G)\right]$ is

$\displaystyle\sum_{\ell=1}^{k}\sum_{\delta=0}^{n-1}\mathbb{E}\Big{[}t_{\ell}(G)\big{(}n-\Delta_{\ell}\big{)}\,\big{|}\,\Delta_{\ell}=\delta\Big{]}\cdot\Pr\Big{[}\Delta_{\ell}=\delta\Big{]}=$
$\displaystyle\sum_{\ell=1}^{k}\sum_{\delta=0}^{n-1}\frac{n(n-\delta)}{n-\delta}\Pr\Big{[}\Delta_{\ell}=\delta\Big{]}=kn\sum_{\delta=0}^{n-1}\Pr\Big{[}\Delta_{\ell}=\delta\Big{]}=kn,$

where the second-to-last equality follows from (7). ∎

The result of Theorem 1 inspires the following definition.

######  Definition 2.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be a code with generator matrix
$G$. We call $\mathcal{C}$ a recovery balanced code if
${\mathbb{E}[\widetilde{\tau}_{1}(G)]=\dots=\mathbb{E}[\widetilde{\tau}_{n}(G)].}$
Note that, by Claim 1, recovery balance is indeed a code property and does not
depend on the choice of the generator matrix $G$.

The following is an immediate consequence of Theorem 1.

######  Corollary 2.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be a recovery balanced code and
let $G$ be the systematic generator matrix of $\mathcal{C}$. We have
$\mathbb{E}[\widetilde{\tau}_{i}(G)]=k$ for all $i\in[n]$ and $T_{\max}(G)=k$.

##  V Recovery Balanced Codes

This section studies more in detail codes that are recovery balanced; see
Definition 2. We prove that MDS, Hamming and simplex codes are all recovery
balanced. This allows us to compute the value of $T_{\max}(G)$ for any of
their systematic generator matrices by Corollary 2.

There are various ways of showing that a code is recovery balanced. We give
two sufficient conditions for a code to be recovery balanced, which we apply
in the sequel. The following lemma follows immediately from the definition of
recovery balanced codes and the natural analogues of Lemmas 1 and 2.

######  Lemma 3.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be a code with generator matrix
$G$.

  * (i)

Let $\widetilde{\alpha}_{i}(s)={|\\{S\subseteq[n]:|S|=s,\,g_{i}\in\langle
g_{j}:j\in S\rangle\\}|}$. If the sequence
$(\widetilde{\alpha}_{i}(s):s\in[n])$ is the same for all $i\in[n]$, then
$\mathcal{C}$ is recovery balanced.

  * (ii)

Let $\widetilde{\mathcal{R}}(i)=\\{R_{1},\dots,R_{L}\\}$ be the recovery sets
for the $i$-th encoded strand and let
$\widetilde{\beta}_{i}(s,j)=\left|\\{S\subseteq[L]:|S|=s,\,|\bigcup_{h\in
S}R_{h}|=j\\}\right|$. If the sequence $(\beta_{i}(s,j):s\in[L],j\in[n])$ is
the same for all $i\in[n]$, then $\mathcal{C}$ is recovery balanced.

In the sequel we show how one can apply Lemma 3 to three classes of codes. We
start with a result whose proof is analogous to that of Corollary 1.

######  Proposition 1.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be an MDS code of dimension $k$,
and let $G$ be a generator matrix of $\mathcal{C}$. For all $i,s\in[n]$ we
have

$\displaystyle\widetilde{\alpha}_{i}(s)=\begin{cases}\binom{n-1}{s-1}\quad&\textnormal{if
$s\in[k-1]$,}\\\ \binom{n}{s}\quad&\textnormal{if $s\geq k$,}\end{cases}$

In particular, $\mathcal{C}$ is recovery balanced and $T_{\max}(G)=k$ if $G$
is systematic.

We now turn to $q$-ary Hamming and simplex codes. We show that they are
recovery balanced, which allows us to compute the value of $T_{\max}(G)$ for
any of their systematic generator matrices. We believe the proof techniques we
use are interesting and novel, but because of space constraints we move them
to the Appendix A.

######  Proposition 2.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be the $q$-ary Hamming code of
redundancy $k$. For $i\in[n]$, $s\in[q^{k-1}+1]$ and $j\in[(q^{k}-1)/(q-1)]$
we have

$\displaystyle\widetilde{\beta}_{i}(s,j)=\begin{cases}\gamma(s,v)\quad&\textnormal{if
$j=(q^{k}-q^{v})/(q-1)-1$,}\\\ \gamma(s-1,v)\quad&\textnormal{if
$j=(q^{k}-q^{v})/(q-1)$,}\end{cases}$

where $\gamma(s,v)$ is equal to

$\left[\begin{matrix}k-1\\\
v\end{matrix}\right]_{q}\sum_{u=v}^{k-1}q^{u}\left[\begin{matrix}k-v-1\\\
u-v\end{matrix}\right]_{q}\binom{q^{k-u-1}}{s}(-1)^{u-v}q^{\binom{u-v}{2}}.$

In particular, $\mathcal{C}$ is recovery balanced and $T_{\max}(G)=k$ if $G$
is systematic.

######  Proposition 3.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be the $q$-ary simplex code of
dimension $k$. For all $i,s\in[n]$ we have

$\displaystyle\widetilde{\alpha}_{i}(s)=\sum_{d=1}^{s}\left[\begin{matrix}k-1\\\
d-1\end{matrix}\right]_{q}\sum_{r=1}^{d}\left[\begin{matrix}d\\\
r\end{matrix}\right]_{q}\binom{\frac{q^{r}-1}{q-1}}{s}(-1)^{d-r}q^{\binom{d-r}{2}}.$

In particular, $\mathcal{C}$ is recovery balanced and $T_{\max}(G)=k$ if $G$
is systematic.

##  VI Breaking the Balance of MDS Codes

In this section we focus on code constructions. Inspired by Theorem 1 and
Lemma 1, we show how we can perturb the “recovery balance” of MDS codes to
obtain a better performance for the random access problem. We do this by
taking the generator matrix of an MDS code and appending identity matrices.
While we are not able to identify the optimum number of identity matrices one
should append, we give closed formulas for the performance indicators and
include plots. We start with the following notation.

######  Notation 2.

Let $G=(I_{k}\mid R)\in\mathbb{F}_{q}^{k\times n}$ be a systematic generator
matrix of an MDS code, which we fix in this section. For $x\geq 1$, we let
$G^{x}=(I_{k}\mid I_{k}\mid\dots\mid I_{k}\mid R)\in\mathbb{F}_{q}^{k\times
N}$ (where $N=xk+n-k$) be the matrix obtained by appending $x-1$ more identity
matrices to $G$.

By concatenating identity matrices to the generator matrix of a recovery
balanced code, it is possible to “break” the balance and improve its
performance. The following result gives an explicit formula for the random
access expectation of “perturbed” MDS codes.

######  Proposition 4.

Let $N=xk+n-k$. For all $i\in[k]$ we have

$\displaystyle
T_{\max}(G^{x})=1+\sum_{s=1}^{N-1}\frac{\binom{N-x}{s}}{\binom{N-1}{s}}-\sum_{s=k}^{N-1}\sum_{a=0}^{k-1}\frac{\binom{k-1}{a}}{\binom{N-1}{s}}\cdot$
$\displaystyle\qquad\qquad\sum_{m=0}^{s-k}\binom{n-k}{s-a-m}\sum_{t=0}^{a}(-1)^{t}\binom{a}{t}\binom{(a-t)x}{m+a}.$

###### Proof.

In order to give an expression for $\mathbb{E}[\tau_{i}(G^{x})]$, by (the
natural analogue of) Lemma 1 it suffices to compute
$\widetilde{\alpha}_{i}(s)$ for the code generated by $G^{x}$. Since $G$ is a
generator matrix of an MDS code, the only possible ways to recover the $i$-th
information strand is by either sampling the strand itself, or by sampling at
least $k$ distinct columns of $G^{x}$.

If $1\leq s\leq k-1$, it is not hard to see that

$\displaystyle\widetilde{\alpha}_{i}(s)=\binom{N}{s}-\binom{N-x}{s}.$

We then focus on the case $k\leq s\leq N-1$. We can recover $e_{i}$ from $s$
columns of $G^{x}$ if $e_{i}$ is one of them. The only other way to recover
$e_{i}$ from $s$ columns of $G^{x}$ is by sampling at least $k$ distinct
columns. Therefore we need to find the size the set
$\\{S\subseteq[N]:|S|=s,\,e_{i}\notin\\{g_{j}:j\in S\\},\,|\\{g_{j}:j\in
S\\}|\geq k\\}$, which we denote by $\mathcal{S}$ in the sequel.

Let $\mathcal{A}=[xk]\setminus\\{i,2i,\dots,xi\\}$ and
$\mathcal{B}=\\{xk+1,\dots,N\\}$, so that we have $g_{j}=e_{j}$ for all
$j\in\mathcal{A}$ and the columns indexed by $\mathcal{B}$ correspond to the
columns of $R$, which is the redundancy part of $G=(I_{k}\mid R)$ as in
Notation 2. We have that $|\mathcal{S}|$ is

$\displaystyle\sum_{a=0}^{k-1}$ $\displaystyle|\\{(A,B)\in
2^{\mathcal{A}}\times 2^{\mathcal{B}}:|\\{g_{j}:j\in A\\}|=a,|B|=s-|A|\\}|$
$\displaystyle=\sum_{a=0}^{k-1}\sum_{m=0}^{s-k}\sum_{\begin{subarray}{c}A\subseteq\mathcal{A}\\\
|A|=a+m\\\ |\\{g_{j}:j\in
A\\}|=a\end{subarray}}|\\{B\subseteq\mathcal{B}:|B|=s-|A|\\}|$
$\displaystyle=\sum_{a=0}^{k-1}\sum_{m=0}^{s-k}\sum_{\begin{subarray}{c}A\subseteq\mathcal{A}\\\
|A|=a+m\\\ |\\{g_{j}:j\in A\\}|=a\end{subarray}}\binom{N-xk}{s-a-m}.$ (8)

For any $a\in\\{0,\dots,k-1\\}$ and $m\in\\{0,\dots,s-k\\}$, we are left with
computing the size of the set

$\displaystyle|\\{A\subseteq\mathcal{A}:|\\{g_{j}:j\in A\\}|=a,|A|=a+m\\}|.$

Let $C\subseteq\\{g_{j}:j\in\mathcal{A}\\}$ with $|C|=a$. Using the Inclusion-
Exclusion Principle, one can check that we have

$\displaystyle|\\{A\subseteq\mathcal{A}:\\{g_{j}:j\in A\\}=C,|A|=a+m\\}|$
$\displaystyle=\sum_{t=0}^{a}(-1)^{t}\binom{a}{t}\binom{(a-t)x}{m+a}$

Summing over all $C\subseteq\\{g_{j}:j\in\mathcal{A}\\}$ with $|C|=a$ together
with (VI) gives that $|\mathcal{S}|$ equals

$\displaystyle\sum_{a=0}^{k-1}\binom{k-1}{a}\sum_{m=0}^{s-k}\binom{N-xk}{s-a-m}\sum_{t=0}^{a}(-1)^{t}\binom{a}{t}\binom{(a-t)x}{m+a}.$

By combining all of this with Lemma 1 we finally obtain

$\displaystyle\mathbb{E}[\tau_{i}(G^{x})]=NH_{N}-\sum_{s=1}^{N-1}\frac{\binom{N}{s}-\binom{N-x}{s}}{\binom{N-1}{s}}-\sum_{s=k}^{N-1}\frac{|\mathcal{S}|}{\binom{N-1}{s}},$

which does not depend on the coordinate $i$ and therefore, after simplifying,
gives the statement of the proposition. ∎

$1$$5$$10$$15$$20$$25$$30$$35$$40$$0.87$$0.88$$0.9$$0.93$$0.95$$0.98$$1$Values
of $x$rate $=1/2$rate $=1/3$rate $=1/4$rate $=1/5$rate $=1/10$rate $=1/20$
Figure 1:  Normalized random access coverage depth $T_{\max}(G^{x})$ from
Proposition 1 for $k=5$ and various rates.

Unfortunately, the formula in Proposition 4 is not easy to evaluate
explicitly. However, experimental results indicate that already for $x=2$ (and
any MDS code) the random access expectation is strictly smaller than $k$. In
Figure 1 we give an example of how the (normalized by $k$) expectation of the
code obtained by concatenating $x-1$ identity matrices changes, depending on
$x$. The plot in Figure 1 is for $k=5$ and various rates (where the rate is
the ratio between the dimension $k=5$ and the $n$, the length of the MDS code
that we started with).

##  VII Discussion and Future Work

In this paper, we studied the random access coverage depth problem and
specifically, we focused on the task of determining the values of $T_{\max}$,
$T(n,k)$, and $T(k)$. Our results give important steps towards understanding
what structural properties of generating matrices result in random access
expectation which is smaller than $k$. While the results in the paper provide
a significant contribution to the study of the random access coverage depth
problem, there are still several interesting problems, which are left open. A
natural problem inspired by our results is that of understanding better which
codes are recovery balanced. In particular, we conjecture that the property of
being recovery balanced is closed under duality and there are only a handful
of other families of recovery balanced codes beyond the ones we present here.
Moreover, experiments, and also intuitive reasoning, suggest that systematic
generator matrices outperform non-systematic generator matrices when
addressing this problem. However, showing this property remains for future
work. An extended version of this paper is anticipated, where we aim to
develop a more complete theory on recovery balanced codes, to construct other
“good” codes in terms of having small random access expectation, and to study
the random access for retrieving a subset of the information strands, and not
only a single strand.

## References

  * [1] J. Rydning, “Worldwide idc global datasphere forecast, 2022–2026: Enterprise organizations driving most of the data growth,” tech. rep., Technical Report, 2022.
  * [2] DNA Data Storage Alliance, “Preserving our digital legacy: an introduction to DNA data storage,” 2021.
  * [3] D. Markowitz, “Biology is all you need,” The International Conference for High Performance Computing, Networking, Storage, and Analysis, 2023.
  * [4] L. Anavy, I. Vaknin, O. Atar, R. Amit, and Z. Yakhini, “Data storage in DNA with fewer synthesis cycles using composite DNA letters,” Nature biotechnology, vol. 37, no. 10, pp. 1229–1236, 2019.
  * [5] M. Blawat, K. Gaedke, I. Huetter, X.-M. Chen, B. Turczyk, S. Inverso, B. W. Pruitt, and G. M. Church, “Forward error correction for DNA data storage,” Procedia Computer Science, vol. 80, pp. 1011–1022, 2016.
  * [6] J. Bornholt, R. Lopez, D. M. Carmean, L. Ceze, G. Seelig, and K. Strauss, “A DNA-based archival storage system,” in Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 637–649, 2016.
  * [7] L. Organick, S. D. Ang, Y.-J. Chen, R. Lopez, S. Yekhanin, K. Makarychev, M. Z. Racz, G. Kamath, P. Gopalan, B. Nguyen, et al., “Random access in large-scale DNA data storage,” Nature biotechnology, vol. 36, no. 3, pp. 242–248, 2018.
  * [8] S. H. T. Yazdi, R. Gabrys, and O. Milenkovic, “Portable and error-free DNA-based data storage,” Scientific reports, vol. 7, no. 1, p. 5011, 2017.
  * [9] S. Tabatabaei Yazdi, Y. Yuan, J. Ma, H. Zhao, and O. Milenkovic, “A rewritable, random-access DNA-based storage system,” Scientific reports, vol. 5, no. 1, pp. 1–10, 2015.
  * [10] D. Bar-Lev, I. Orr, O. Sabary, T. Etzion, and E. Yaakobi, “Deep DNA storage: Scalable and robust DNA storage via coding theory and deep learning,” arXiv preprint arXiv:2109.00031, 2021.
  * [11] I. Shomorony, R. Heckel, et al., “Information-theoretic foundations of DNA data storage,” Foundations and Trends® in Communications and Information Theory, vol. 19, no. 1, pp. 1–106, 2022.
  * [12] S. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao, and O. Milenkovic, “DNA-based storage: Trends and methods,” IEEE Transactions on Molecular, Biological and Multi-Scale Communications, vol. 1, no. 3, pp. 230–248, 2015.
  * [13] R. Heckel, G. Mikutis, and R. N. Grass, “A characterization of the DNA data storage channel,” Scientific reports, vol. 9, no. 1, p. 9663, 2019.
  * [14] Y. Erlich and D. Zielinski, “DNA fountain enables a robust and efficient storage architecture,” science, vol. 355, no. 6328, pp. 950–954, 2017.
  * [15] S. Chandak, K. Tatwawadi, B. Lau, J. Mardia, M. Kubit, J. Neu, P. Griffin, M. Wootters, T. Weissman, and H. Ji, “Improved read/write cost tradeoff in DNA-based data storage using LDPC codes,” in 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 147–156, IEEE, 2019.
  * [16] D. Bar-Lev, O. Sabary, R. Gabrys, and E. Yaakobi, “Cover your bases: How to minimize the sequencing coverage in DNA storage systems,” arXiv preprint arXiv:2305.05656, 2023.
  * [17] I. Preuss, B. Galili, Z. Yakhini, and L. Anavy, “Sequencing coverage analysis for combinatorial DNA-based storage systems,” bioRxiv, pp. 2024–01, 2024.
  * [18] P. Erdős and A. Rényi, “On a classical problem of probability theory,” Magyar Tud. Akad. Mat. Kutató Int. Közl, vol. 6, no. 1, pp. 215–220, 1961.
  * [19] W. Felleb, “An introduction to probability theory and its applications, vol. 1,” IWiley, New York, 1968.
  * [20] P. Flajolet, D. Gardy, and L. Thimonier, “Birthday paradox, coupon collectors, caching algorithms and self-organizing search,” Discrete Applied Mathematics, vol. 39, no. 3, pp. 207–229, 1992.
  * [21] D. J. Newman, “The double dixie cup problem,” The American Mathematical Monthly, vol. 67, no. 1, pp. 58–61, 1960.
  * [22] I. Preuss, M. Rosenberg, Z. Yakhini, and L. Anavy, “Efficient DNA-based data storage using shortmer combinatorial encoding,” bioRxiv, pp. 2021–08, 2021.
  * [23] H. Abraham, R. Gabrys, and E. Yaakobi, “Covering all bases: The next inning in DNA sequencing efficiency,” arXiv preprint, 2024.
  * [24] R. Stanley, Enumerative Combinatorics, vol. 1.  Cambridge University Press, 2nd ed., 2011.

## Appendix A

For the reader’s convenience, we restate results before presenting the
corresponding proofs.

###### Proof of Proposition 2.

See 2 We will need the following (well-known) claim for proving the
proposition.

######  Claim 2.

Let $\mathcal{C}\subseteq\mathbb{F}_{q}^{n}$ be a code of dimension $k$ with
systematic generator matrix $G$. Let $i\in[k]$. There exists a (minimal)
recovery set $R\subseteq[n]$ with $|R|\geq 2$ for the $i$-th encoded strand if
and only if there is a codeword $x\in\mathcal{C}^{\perp}$ with
$i\in\operatorname{supp}(x)$ and $R=\operatorname{supp}(x)\setminus\\{i\\}$.

Let $H$ be a parity-check matrix of $\mathcal{C}$. A set $S\subseteq[n]$ is a
recovery sets (of size $\geq 2$) for the $i$-th encoded strand if and only if
there exists $x\in\mathcal{C}^{\perp}$ with
$i\in\operatorname{supp}(x)=S\cup\\{i\\}$; see Claim 2. Moreover, since $H$
has as columns all the non-zero vectors (up to multiples) of
$\mathbb{F}_{q}^{k}$, $S\subseteq[n]$ is the support of some
$x\in\mathcal{C}^{\perp}$ if and only if the columns of $H$ indexed by $S^{c}$
form a hyperplane of $\mathbb{F}_{q}^{k}$.

In the remainder of the proof, we denote by $\rho(V)$ the set of 1-dimensional
subspaces of a space $V\leq\mathbb{F}_{q}^{k}$ and we let $h_{i}$ be the
$i$-th column of $H$. Note that if $\dim(V)=v$ then
$|\rho(V)|=(q^{v}-1)/(q-1)$. In order to give an explicit formula for
$\widetilde{\beta}_{i}(s,j)$, we count the number of sets of $s$ (distinct)
hyperplanes $\\{\mathcal{H}_{1},\dots,\mathcal{H}_{s}\\}$ with the properties
that $h_{i}\notin\mathcal{H}_{\ell}$ for all $\ell\in[s]$ and
$|\bigcup_{\ell=1}^{s}\rho(\mathcal{H}_{\ell})^{c}|=j$. Using simple set
theory, this is equivalent to asking that
$|\bigcap_{\ell=1}^{s}\rho(\mathcal{H}_{\ell})|=\rho(\mathbb{F}_{q}^{k})-j=(q^{k}-1)/(q-1)-j$.
Note that we have
$\bigcap_{\ell=1}^{s}\rho(\mathcal{H}_{\ell})=\rho\left(\bigcap_{\ell=1}^{s}\mathcal{H}_{\ell}\right)=(q^{v}-1)/(q-1)$
for some integer $v\in[k]$.

In the rest of the proof we use the Möbius inversion formula for the lattice
of subspaces (see e.g. [24, Propositions 3.7.1 and Example 3.10.2]). Let
$\mathcal{P}$ be the collection of hyperplanes of $\mathbb{F}_{q}^{k}$. For a
subspace $V\leq\mathbb{F}_{q}^{k}$ define

$\displaystyle
f(V):=\Bigl{|}\Bigl{\\{}\mathcal{H}=\\{\mathcal{H}_{1},\ldots,\mathcal{H}_{s}\\}\subseteq\mathcal{P}:|\mathcal{H}|=s,$
$\displaystyle h_{i}\notin H_{\ell}\textnormal{ for all
$\ell\in[s]$},\,\bigcap_{\ell=1}^{s}\mathcal{H}_{\ell}=V\Bigr{\\}}\Bigr{|}$

and

$\displaystyle g(V):=\Bigl{|}\Bigl{\\{}$
$\displaystyle\mathcal{H}=\\{\mathcal{H}_{1},\dots,\mathcal{H}_{s}\\}\subseteq\mathcal{P}:|\mathcal{H}|=s,$
$\displaystyle h_{i}\notin\mathcal{H}_{\ell}\textnormal{ for all
$\ell\in[s]$},\,\bigcap_{\ell=1}^{s}\mathcal{H}_{\ell}\geq
V\Bigr{\\}}\Bigr{|}$ $\displaystyle=\Bigl{|}\Bigl{\\{}$
$\displaystyle\\{\mathcal{H}_{1},\dots,\mathcal{H}_{s}\\}\subseteq\mathcal{P}:|\mathcal{H}|=s,$
$\displaystyle h_{i}\notin\mathcal{H}_{\ell}\mbox{ and
}V\leq\mathcal{H}_{\ell}\textnormal{ for all $\ell\in[s]$}\Bigr{\\}}\Bigr{|}.$

We continue by giving an explicit expression for $g(V)$ in terms of
$v=\dim(V)$. If $h_{i}\notin V$ we have that the number of hyperplanes
$\mathcal{H}_{\ell}$ with $h_{i}\notin\mathcal{H}_{\ell}$ and
$V\leq\mathcal{H}_{\ell}$ is

$\displaystyle\left[\begin{matrix}k-v\\\
k-1-v\end{matrix}\right]_{q}-\left[\begin{matrix}k-v-1\\\
k-1-v-1\end{matrix}\right]_{q}.$

Using the well-known identity for $q$-ary binomial coefficients

$\displaystyle\left[\begin{matrix}a\\\
b\end{matrix}\right]_{q}-\left[\begin{matrix}a-1\\\
b-1\end{matrix}\right]_{q}=q^{b}\left[\begin{matrix}a-1\\\
b\end{matrix}\right]_{q}\;\textnormal{for all $a\geq b\geq 1$,}$ (9)

we then have

$\displaystyle g(V)$ $\displaystyle=\sum_{U\geq
V}f(U)=\begin{cases}0\quad&\textnormal{if $h_{i}\in V$,}\\\
\binom{q^{k-v-1}}{s}\quad&\textnormal{if $h_{i}\notin V$.}\end{cases}$

Therefore, by the Möbius inversion formula, we have

$\displaystyle f(V)=$ $\displaystyle\sum_{U\geq
V}g(U)(-1)^{\dim(U)-v}q^{\binom{\dim(U)-v}{2}}$ $\displaystyle=$
$\displaystyle\sum_{\begin{subarray}{c}U\geq V\\\ h_{i}\notin
U\end{subarray}}g(U)(-1)^{\dim(U)-v}q^{\binom{\dim(U)-v}{2}}$ $\displaystyle=$
$\displaystyle\sum_{u=v}^{k-1}\left(\left[\begin{matrix}k-v\\\
u-v\end{matrix}\right]_{q}-\left[\begin{matrix}k-v-1\\\
u-v-1\end{matrix}\right]_{q}\right)\left(\begin{matrix}q^{k-u-1}\\\
s\end{matrix}\right)\cdot$ $\displaystyle\hskip
128.0374pt(-1)^{u-v}q^{\binom{u-v}{2}}.$

This together with (9) again, after summing over all $V\leq\mathbb{F}_{q}^{k}$
with $\dim(V)=v$ and with $h_{i}\notin V$ (there are

$\left[\begin{matrix}k\\\ v\end{matrix}\right]_{q}-\left[\begin{matrix}k-1\\\
v-1\end{matrix}\right]_{q}=q^{v}\left[\begin{matrix}k-1\\\
v\end{matrix}\right]_{q}$

such spaces), shows that $\gamma(s,v)$ counts the number of $s$-sets of
codewords in $\mathcal{C}^{\perp}$ with the property that the union of their
support has cardinality $(q^{k}-q^{v})/(q-1)$ and which all contain $i$ in
their support.

To conclude the proof, note that the only recovery sets we did not consider so
far are those of size 1. For each $i$, distinguishing between the case where
this recovery set is one of the $s$ sets considered in the computation of
$\widetilde{\beta}_{i}(s,j)$ and the case where this is not the case, gives
the formula in the proposition. ∎

###### Proof of Proposition 3.

See 3

A generator matrix of $\mathcal{C}$ has as columns all the non-zero vectors
(up to multiples) in $\mathbb{F}_{q}^{k}$. For $S\subseteq[n]$ we denote by
$G_{S}$ the set of columns of $G$ indexed by $S$, i.e., $G_{S}=\\{g_{j}:j\in
S\\}$. We have

$|\\{S\subseteq[n]\colon|S|=s,\,g_{i}\in\langle G_{S}\rangle\\}|=\\\
\sum_{d=1}^{s}|\\{S\subseteq[n]\colon|S|=s,\,g_{i}\in G_{S},\,\dim\langle
G_{S}\rangle=d\\}|.$

In order to compute $|\\{S\subseteq[n]\colon|S|=s,\,g_{i}\in\langle
G_{S}\rangle,\,\dim\langle G_{S}\rangle=d\\}|$ for $d\in[s]$ we use Möbius
inversion in the lattice of subspaces in $\mathbb{F}_{q}^{k}$. For a subspace
$V\leq\mathbb{F}_{q}^{k}$ we let

$\displaystyle f(V)$ $\displaystyle=|\\{S\subseteq[n]\colon|S|=s,\langle
G_{S}\rangle=V\\}|,$ $\displaystyle g(U)$ $\displaystyle=\sum_{U\leq
V}f(U)=|\\{S\subseteq[n]\colon|S|=s,\langle G_{S}\rangle\leq V\\}|$
$\displaystyle=\binom{\frac{q^{\dim(V)}-1}{q-1}}{s}.$

Using the Möbius inversion formula we obtain

$\displaystyle f(V)$ $\displaystyle=\sum_{U\leq
V}g(U)(-1)^{\dim(V)-\dim(U)}q^{\binom{\dim(V)-\dim(U)}{2}}$
$\displaystyle=\sum_{r=1}^{\dim(V)}\sum_{\begin{subarray}{c}U\leq V,\\\
\dim(U)=r\end{subarray}}\binom{\frac{q^{r}-1}{q-1}}{s}(-1)^{\dim(V)-r}q^{\binom{\dim(V)-r}{2}}$
$\displaystyle=\sum_{r=1}^{\dim(V)}\left[\begin{matrix}\dim(V)\\\
r\end{matrix}\right]_{q}\binom{\frac{q^{r}-1}{q-1}}{s}(-1)^{\dim(V)-r}q^{\binom{\dim(V)-r}{2}}.$

In particular, we have

$\displaystyle|\\{S\subseteq[n]$ $\displaystyle\colon|S|=s,\,g_{i}\in\langle
G_{S}\rangle,\,\dim\langle G_{S}\rangle=d\\}|$
$\displaystyle=\sum_{\begin{subarray}{c}V\leq\mathbb{F}_{q}^{k},\\\
\dim(V)=d,\\\ g_{i}\in V\end{subarray}}f(V)$
$\displaystyle=\left[\begin{matrix}k-1\\\
d-1\end{matrix}\right]_{q}\sum_{r=1}^{d}\left[\begin{matrix}d\\\
r\end{matrix}\right]_{q}\binom{\frac{q^{r}-1}{q-1}}{s}(-1)^{d-r}q^{\binom{d-r}{2}},$

which concludes the proof. ∎