Expected Recovery Time in DNA-based Distributed Storage Systems Adi Levy, Roni Con, Eitan Yaakobi, Han Mao Kiah Abstract We initiate the study of DNA-based distributed storage systems , where information is encoded across multiple DNA data storage containers to achieve robustness against container failures. In this setting, data are distributed over M M containers, and the objective is to guarantee that the contents of any failed container can be reliably reconstructed from the surviving ones. Unlike classical distributed storage systems, DNA data storage containers are fundamentally constrained by sequencing technology, since each read operation yields the content of a uniformly random sampled strand from the container. Within this framework, we consider several erasure-correcting codes and analyze the expected recovery time of the data stored in a failed container. Our results are obtained by analyzing generalized versions of the classical Coupon Collector’s Problem, which may be of independent interest. † † A.L., R.C., and E.Y. are supported by the European Union (DiDAX, 101115134). Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. 1 Introduction Recent advances in DNA-based data storage technologies have positioned DNA as a compelling substrate for long-term digital archiving, offering density, durability, and longevity far beyond the capabilities of conventional media. As global data generation accelerates at an unprecedented pace, existing storage technologies such as magnetic disks, solid-state drives, and tapes struggle to meet the demands of scalability, reliability, and archival lifetime. DNA, by contrast, provides an ultra-dense and chemically stable medium whose information can persist for thousands of years under modest conditions. These features position DNA-based storage as a promising solution for the growing archival storage crisis [ CGK12 , GBC+13 , YKGR+16 , OAC+18 ] . A conventional DNA-based data storage system is composed of three main elements: DNA synthesis, storage containers, and DNA sequencing. First, artificial DNA strands, called oligos, are produced to encode the user’s data. These strands are then stored in an unordered manner within a storage container, with each strand present in millions of copies. Finally, DNA sequencing is used to read the stored strands and transform them into digital sequences, known as reads, which are then decoded to reconstruct the original user information. In each of these three components, errors might occur, and thus, much attention was given to designing error-correcting codes for DNA-based storage systems. We refer the reader to the following survey [ SKSY24 ] that presents the coding challenges in such systems. In this work, we initiate the study of coding for DNA-based distributed storage systems . We consider a setting with M DNA storage containers, and our objective is to encode data across these M containers so that, even if one or more containers fail, the lost information can still be reconstructed from the remaining containers. The formulation of this problem matches that of standard distributed storage systems. However, there are a few important differences between our notion of repair and the one adopted in the classical storage setting. In a classical distributed storage system, a file is divided into k data fragments and then encoded using an erasure-correcting code, producing M>k fragments in total, with each fragment stored on a different one of the M nodes. Since an erasure code is used, repairing a failed node reduces to decoding a single erasure of a codeword. A central performance metric in traditional distributed storage systems is the repair bandwidth , which denotes the amount of information downloaded from the remaining nodes to recover the failed one. The problem of minimizing the repair bandwidth was introduced in the seminal work of Dimakis et al. [ DGW+10 ] and has since attracted extensive attention, leading to ingenious constructions that achieve optimal tradeoffs (for a detailed overview, the reader is referred to the survey [ RBS+22 ] ). We emphasize that in this model, nodes are allowed to perform arbitrary computations on their stored data and transmit the resulting outputs. In DNA-based distributed storage, the process of downloading information from containers is fundamentally different. First, no computation can be performed within a container. Second, reading is carried out by a sequencer, which we assume samples a strand uniformly at random from the container in each read. Because each of the n strands is present in the tube in about a million identical copies, all in equal numbers, drawing a strand uniformly at random from the container is effectively the same as choosing one of the n distinct strands uniformly at random. It was observed in [ BLSGY24 ] , that this sampling model is deeply connected with the classical coupon collector’s problem (CCP, for short). In the CCP, there are n distinct coupons, and at each point of time, the collector picks a coupon uniformly at random from the n coupons, and then returns it. The task of the collector is to see all the n distinct coupons, and the question is how many rounds it takes. This problem has been extensively investigated in combinatorics and probability theory; see, for instance, [ ER61 , BH97 , AR01 , KJV07 , AD21 ] . However, the classical problem received many new twists with the new connection to DNA-based storage systems [ BLSGY24 , AGY24 , GBLRY24 , GMZ24 , BEG+25 ] . In this paper, we introduce a DNA-based distributed storage system model. We establish a connection between this model and a generalized coupon collector’s problem involving multiple independent collectors, each with its own set of coupons to be collected. To the best of our knowledge, this generalized setting has not been studied previously and may be of independent interest. 1.1 Distributed DNA Storage and Coupon Collector’s Problem For a positive integer n , let [n]\triangleq\{1,\ldots,n\} . We consider a distributed storage system with M containers, each storing n distinct strands. Each container is equipped with its own sequencer, and reads are performed in parallel: at each time step, one strand is sampled uniformly at random from each functioning container. When one container fails, our goal is to reconstruct its data from the remaining M-1 containers, and we study the expected time required for this recovery. There could be several reasons for a container to become unavailable. These include physical degradation or loss of DNA molecules due to chemical decay or handling errors [ CGK12 , GBC+13 , YKGR+16 ] , as well as failures in the sequencing or library preparation pipeline that render the contents of a container unreadable despite the DNA remaining intact [ OAC+18 , SKSY24 ] . At scale, additional failure modes include contamination or mislabeling events that prevent reliable identification of a container’s data [ YKGR+16 , OAC+18 ] . From a coding-theoretic perspective, such events are naturally modeled as container-level erasures, in direct analogy to node failures in classical distributed storage systems [ DGW+10 , RBS+22 ] . Remark 1 . We emphasize that, in practice, each strand is stored in millions of identical copies. For simplicity, and as an approximation of this setting, we assume that at any time, each container contains exactly n distinct strands, from which one strand is sampled uniformly at random, read, and returned. Figure 1: An illustration of a DNA-DSS We begin by formally defining a DNA-based distributed storage system, and then introduce the main parameter of interest, namely the expected recovery time of a container. Definition 1 ( (n,M,k,|\Sigma|) DNA-based distributed storage system (DNA-DSS)) . Let n,M , and k be positive integers and let \Sigma be an alphabet. An (n,M,k,|\Sigma|) DNA-based distributed storage system (DNA-DSS) is defined by an injective encoder \mathcal{E}:\Sigma^{k}\to\Sigma^{n\times M} such that, for every {\boldsymbol{v}}\in\Sigma^{k} and every j\in[M] , the following condition is satisfied: The j -th column of S\triangleq\mathcal{E}({\boldsymbol{v}}) can be reconstructed from the collection of columns of S indexed by [M]\setminus\{j\} . Note that this definition is purely mathematical and does not yet refer to DNA-based storage systems. The relation to DNA-based storage is as follows. Suppose {\boldsymbol{v}}\in\Sigma^{k} represents the data we wish to store and set S=\mathcal{E}(v) . For each j\in[M] , the j -th container stores the n entries of the j -th column of S . Thus, every container holds n values, corresponding to the n strands within that container. The requirement in Definition 1 can be rephrased as follows: the data in the failed j -th container can be reconstructed by reading all the data from the remaining M-1 containers. Definition 2 (The expected recovery time of a container) . For every j\in[M] , we define T_{j} as the random variable representing the time required to recover the j -th container under this model. The expected recovery time of the j -th container will be denoted by \mathbb{E}[T_{j}] . In this paper, we design DNA-DSS using MDS (maximum distance separable) codes and analyze the expected recovery time of a failed container. An MDS code of length M and redundancy r is an injective encoder \mathcal{E}:\Sigma^{M-r}\to\Sigma^{M} such that any \mathbf{v}\in\Sigma^{M-r} can be uniquely recovered from any M-r entries of the codeword \mathcal{E}(\mathbf{v}) . Before presenting our main results, we briefly revisit the classical coupon collector problem. We shall see that several of our results can be viewed as generalizations of this problem. The Coupon Collector’s Problem. We give a formal definition of the classical coupon collector distribution, as well as of the distribution corresponding to the version with \ell copies. Definition 3 (Coupon Collector’s distribution) . Consider n distinct coupon types, and draw one coupon at each trial independently and uniformly from these n types. Let X^{(n)} be the number of draws needed to obtain at least one of each type, and let X^{(n,\ell)} be the number of draws needed to obtain at least \ell of each type. We write X^{(n)}\sim\text{CCP}(n) and X^{(n,\ell)}\sim\text{CCP}(n,\ell) . It is a well-known fact that \mathbb{E}[X^{(n)}]=n(\ln n+\gamma)+O(1) , where \gamma=0.577\ldots is the Euler–Mascheroni constant. (e.g., [ MU05 , Section 2.4.1] ). In [ New60 , Theorem 2] , it was shown that when \ell is fixed, we have \mathbb{E}\left[X^{(n,\ell)}\right]=n\ln n+(\ell-1)n\ln\ln n+n\cdot C_{\ell}+o(n) , and later, in [ ER61 ] , it was shown that C_{\ell}=\gamma-\ln((\ell-1)!) . 2 Our Results MDS codes have the best known rate-erasure correcting tradeoff and are therefore widely studied in classical distributed storage systems. We likewise study the performance of MDS codes in the DNA-DSS setting. Our results follow the classical split: first, we consider scalar MDS codes , and then array regenerating MDS codes . We note, however, that MDS and regenerating codes may not be optimal for minimizing the expected container recovery time, and we leave this question for future work. Throughout this paper, we work under the assumption that the number of containers, denoted by M , is fixed, while the number of distinct strands n tends to infinity. In addition, whenever we use the notation o(1) , it represents a term that goes to 0 as n goes to infinity. Finally, for numbers a,b and c , we will denote by a\pm b the interval [a-b,a+b] and c(a\pm b)=ca\pm cb . 2.1 The Scalar MDS Code Case We design an (n,M,n(M-r),q) DNA-DSS based on an MDS code of length M and redundancy r as follows. Let S^{\prime}\in\Sigma^{n\times(M-r)} denote the information to be stored (in the notation of Definition 1 , this corresponds to |\Sigma|=q and k=n(M-r) ). Each row vector of S^{\prime} is encoded using the encoder of the MDS code into a row vector {\boldsymbol{v}} of length M . Let S\in\Sigma^{n\times M} denote the matrix whose rows are these encoded vectors, and store each column of S in a distinct container. Once a container fails, the MDS property guarantees that to recover its content, it is enough to know any M-r symbols from each row of S . We therefore inquire for the expected time it takes to read this data from the functional containers. We will formulate this question, and obtain its answer, in terms of the following random process. Theorem 1 . Let A^{(0)}={\boldsymbol{0}}^{n\times(m+\rho)},A^{(1)},A^{(2)},\ldots be a sequence of matrices constructed as follows: for each t\in\mathbb{N} , we draw (v_{1},\ldots,v_{m+\rho})\sim\mathrm{Unif}([n]^{m+\rho}) and set A^{(t)}=A^{(t-1)}+\left[{\boldsymbol{e}}_{v_{1}},\ldots,{\boldsymbol{e}}_{v_{m+\rho}}\right]\;, where {\boldsymbol{e}}_{a} denotes the column vector with a 1 in the a -th position and 0 in all other entries. Define T_{n,m,\rho} as the random variable that corresponds to the smallest t such that every row of A^{(t)} contains at least m nonzero entries. Then, \mathbb{E}\left[T_{n,m,\rho}\right]=\frac{n}{\rho+1}\left(\ln n+\ln\binom{m+\rho}{m-1}+\gamma\pm o(1)\right). The next corollary states the associated DNA-DSS, derived from Theorem 1 by instantiating it with a standard MDS code having redundancy r=\rho+1 and length M=m+\rho+1 . As concrete choices, one may use a doubly extended Reed–Solomon code over an alphabet of prime-power size [ Rot06 , Section 5, Problem 5.2] , or, in the special case where a single container acts as the redundancy container, a simple parity code suffices. Corollary 1 . Let n,M,r\in\mathbb{N} . If r=1 , choose any positive integer q\geq 2 . If r\geq 2 , choose q to be a prime power satisfying q\geq M-1 . Then there exists an (n,M,n(M-r),q) DNA-DSS such that the expected recovery time, T_{j} , of every container j\in[M] is \mathbb{E}[T_{j}]=\frac{n}{r}\ln n+\frac{n}{r}\ln\binom{M-1}{r}+\frac{\gamma n}{r}\pm o(n)\;. A direct theorem for r=1 . We observe that Theorem 1 and Corollary 1 already handle the situation in which exactly one container stores redundant data. Nonetheless, to build intuition for the proof of Theorem 1 , we present here and prove in Section 4 a simpler statement, which can be viewed as a straightforward extension of the classical coupon collector problem. In the special case r=1 , whenever a container fails, recovering it necessitates reading all strands from each of the remaining containers. This is equivalent to asking for the expected time until m independent coupon collectors (each with its own set of n coupons) collect all their coupons. Formally, we show the following. Theorem 2 . Let n\in\mathbb{N} and let m be a constant positive integer with respect to n . Let X^{(n)}_{1},\ldots,X^{(n)}_{m} be i.i.d. random variables with X^{(n)}_{j}\sim\text{CCP}(n) . Then, \mathbb{E}\left[\max_{j\in[m]}X^{(n)}_{j}\right]=n\left(\ln(mn)+\gamma\pm o(1)\right)\;. In practice, each strand is stored in many identical copies, so sequencing typically yields multiple reads of the same strand. When errors are present, having several corrupted versions of each strand can enhance the tradeoff between rate and reliability. In this work, however, we do not address errors. Instead, we generalize Theorem 2 to the setting where \ell copies of each coupon are required, laying the groundwork for future extensions that incorporate also storage errors. Theorem 3 . Let m and \ell be constant positive integers. Let X^{(n,\ell)}_{1},\ldots,X^{(n,\ell)}_{m} be i.i.d. random variables with X^{(n,\ell)}_{j}\sim\text{CCP}(n,\ell) . Then, \mathbb{E}\left[\max_{j\in[m]}X^{(n,\ell)}_{j}\right]=n\left(\ln\left(nm\right)+\left(\ell-1\right)\ln\ln n+C_{\ell}\pm o(1)\right) where C_{\ell}=\gamma-\ln((\ell-1)!) . 2.2 The MDS Array Code Case Our next result can be viewed as a generalization of Theorem 1 , motivated by insights from the theory of regenerating codes in classical distributed storage. Let S^{\prime}\in\Sigma^{n\times(M-r)} represent the information to be stored. In the DNA-DSS given in Corollary 1 , we encoded each row of S^{\prime} independently to obtain the encoded matrix S . Consequently, to reconstruct any column of S , it was necessary to read at least a fixed number of symbols from every row of S . We now proceed with a more general construction. Partition S^{\prime} into n/b consecutive submatrices S^{\prime}_{1},\ldots,S^{\prime}_{n/b} , each of dimension b\times(M-r) . Concretely, the first submatrix is formed by the top b rows, the second by the next b rows, and so forth. Each submatrix S^{\prime}_{i} is then encoded into a new submatrix S_{i} of size b\times M using an encoder \mathcal{E}:\Sigma^{b\times(M-r)}\to\Sigma^{b\times M} of an MDS array code. The resulting matrix is obtained by stacking S_{1},\ldots,S_{n/b} vertically. Note that here, the MDS property states that knowing the values of any M-r columns of S suffice to recover S . Assume now that the p -th container has failed and needs to be reconstructed, and focus, for the moment, only on the first block S_{1} . Let M_{p}\triangleq[M]\setminus\{p\} denote the set of all remaining operational containers. The encoding function \mathcal{E} , together with the failed index p , defines a bad blocks configurations family \mathcal{B}_{p}\subseteq\mathcal{P}([b]\times M_{p}) (here, \mathcal{P} denotes the power set) consisting of all index sets that cannot be used to reconstruct the p -th column. Namely, B\in\mathcal{B}_{p} if and only if the p -th column of S_{1} cannot be reconstructed from the collection of symbols \{(S_{1})_{i,j}\mid(i,j)\in B\} . Formally, Definition 4 . (Bad blocks configuration with respect to \mathcal{E} and p ) Let \mathcal{E}:\Sigma^{b\times(M-r)}\to\Sigma^{b\times M} and fix an index p\in[M] . Define M_{p}\triangleq[M]\setminus\{p\} and let \mathcal{B}_{p}\subseteq\mathcal{P}([b]\times M_{p}) be a collection of subsets with the following property: a set B belongs to \mathcal{B}_{p} if and only if there exist two distinct encoded matrices S,S^{\prime}\in\mathcal{E}(\Sigma^{b\times(M-r)}) such that S_{i,j}=S^{\prime}_{i,j} for every (i,j)\in B , while the p -th column of S is not equal to the p -th column of S^{\prime} . Equivalently, even after observing all entries S_{i,j} with (i,j)\in B , one still cannot uniquely determine the p -th column of S . Moreover, define \displaystyle\alpha^{*}_{p} \displaystyle\triangleq(M-1)b-\max_{B\in\mathcal{B}_{p}}|B|\;,\quad\text{and} \displaystyle\beta^{*}_{p} \displaystyle\triangleq|\{B^{\prime}\in\mathcal{B}_{p}\mid|B^{\prime}|=\max_{B\in\mathcal{B}_{p}}|B|\}|\;. Namely, \alpha^{*}_{p} is the smallest number of missing entries of S for which the p -th column cannot be recovered and \beta^{*}_{p} is the be number of bad recovering sets of maximal size in \mathcal{B}_{p} . Note that since the same encoder \mathcal{E} is applied to every block, the family \mathcal{B}_{p} is the same for all matrices S_{1},\ldots,S_{n/b} . Thus, the question we consider is the expected time until, for each block, we have gathered a set of indices that does not belong to \mathcal{B}_{p} . Similarly to Theorem 1 , the next theorem defines the random process and the stopping criterion that characterize recovery, given a bad blocks configuration. Theorem 4 . Let A^{(0)}={\boldsymbol{0}}^{n\times m},A^{(1)},A^{(2)},\ldots be a sequence of matrices constructed as follows: for each t\in\mathbb{N} , we draw (v_{1},\ldots,v_{m})\sim\mathrm{Unif}([n]^{m}) and set A^{(t)}=A^{(t-1)}+\left[{\boldsymbol{e}}_{v_{1}},\ldots,{\boldsymbol{e}}_{v_{m}}\right]\;. Let b\in\mathbb{N} that divides n and let \mathcal{B}\subseteq\mathcal{P}([b]\times[m]) . As Definition 4 , define \alpha^{*}\triangleq mb-\max_{B\in\mathcal{B}}|B|\qquad\beta^{*}\triangleq|\{B^{\prime}\in\mathcal{B}\mid|B^{\prime}|=\max_{B\in\mathcal{B}}|B|\}| Define T as the random variable that corresponds to the minimal t such that for all a\in[n/b] , we have that \left\{(i,j)\in[b]\times[m]\mid A^{(t)}_{i+(a-1)b,j}\neq 0\right\}\notin\mathcal{B}\;. Then, \mathbb{E}[T]\leq\frac{n}{\alpha^{*}}\ln n+\frac{\beta^{*}}{b\alpha^{*}}\cdot n+o(n)\;, Theorem 4 , combined with Definition 4 , yields a framework for establishing an upper bound on the expected recovery time of each container in a DNA-DSS. Corollary 2 . Let M,b,r,n\in\mathbb{N} where b divides n . An injective encoding function \mathcal{E}:\Sigma^{b\times(M-r)}\times\Sigma^{b\times M} yields an (n,M,n(M-r),|\Sigma|) DNA-DSS code such that for every p\in[M] , we have \mathbb{E}[T_{p}]\leq\frac{n}{\alpha^{*}_{p}}\ln n+\frac{\beta^{*}_{p}}{b\alpha^{*}_{p}}n+o(n)\;, where \beta^{*}_{p} and \alpha^{*}_{p} are defined in Definition 4 . Example 1 . We specialize this framework to one of the simplest examples of an MDS regenerating code [ TWB13 , Fig. 1] , defined over \mathbb{F}_{3} . Let n be an even number. Consider the (n,4,2n,3) DNA-DSS defined by the encoding function \mathcal{E}:\mathbb{F}_{3}^{2\times 2}\to\mathbb{F}_{3}^{2\times 4} defined by \mathcal{E}\left(\begin{pmatrix}a&b\\ c&d\end{pmatrix}\right)=\begin{pmatrix}a&b&a+b&a+2d\\ c&d&c+d&c+b\end{pmatrix}\;, where arithmetic oprations are done over \mathbb{F}_{3} . Assume that p=1 and observe that there are exactly two sets of size 3 that recover the first column: \{(1,2),(1,3),(2,4)\} and \{(2,2),(2,3),(1,4)\} . Further, there are only two sets of size 4 that do not recover the first column: \{(1,2),(1,3),(1,4),(2,2)\} and \{(1,2),(2,2),(2,3),(2,4)\} . Thus, \delta 0 1 2 3 4 5 6 b_{\delta} 1 6 \binom{6}{2}=15 \binom{6}{3}-2=18 2 0 0 where b_{\delta}=|\{B\in\mathcal{B}_{1}\mid|B|=\delta\}| . Since M=4 and b=2 , we get, \alpha^{*}_{1}=3\cdot 2-4=2 and \beta^{*}_{1}=2 . In total, we get \mathbb{E}[T_{1}]\leq\frac{n}{2}\ln n+\frac{n}{2}+o(n)\;. Note that, setting M=4 and r=2 in the scalar MDS DNA-DSS construction of Corollary 1 , we obtain \mathbb{E}[T_{1}]\approx\frac{n}{2}\ln n+0.838n\pm o(n) , which shows that the regenerating code provides an improvement of at least 0.338n . 3 Preliminaries We shall use the following limit theorem about the coupon collector distribution. Theorem 5 (Theorem 5.13 [ MU05 ] ) . Let X\sim\text{CCP}(n) . Then, for any constant c , \lim_{n\to\infty}\Pr\left[X>n\ln n+cn\right]=1-e^{-e^{-c}} This limit theorem is exactly a special case of the Gumbel distribution whose definition is given next. Definition 5 (Gumbel distribution) . The cumulative distribution function of Gumbel distribution with parameters \mu,\beta is F(x;\mu,\beta)=e^{-e^{\frac{-(x-\mu)}{\beta}}}. If X is a random variable with Gumbel distribution with parameters \mu,\beta , we denote X\sim\text{Gumbel}(\mu,\beta) . Definition 6 (Convergence in distribution) . A sequence \mathcal{X}=X^{(1)},X^{(2)},\dots of real-valued random variables with cumulative distribution functions F_{1},F_{2},\dots is said to converge in distribution to a random variable X with cumulative distribution function F if \lim_{n\to\infty}F_{n}(x)=F(x) , for every x\in\mathbb{R} at which F is continuous. We denote convergence in distribution by \mathcal{X}\overset{\mathcal{D}}{\to}X . Lemma 1 . Let \mathcal{X}_{1},\ldots,\mathcal{X}_{m} be m sequences of random variables such that for every n\in\mathbb{N} , X_{1}^{(n)},X_{2}^{(n)},\ldots,X_{m}^{(n)} are i.i.d. and for all j\in[m] , we have \mathcal{X}_{j}\overset{\mathcal{D}}{\to}\text{Gumbel}(\mu,\beta) . For every n\in\mathbb{N} , denote X_{\max}^{(n)}\triangleq\max_{j}X_{j}^{(n)} and let \mathcal{X}_{\max}\triangleq X_{\max}^{(1)},X_{\max}^{(2)},\ldots . It holds that \displaystyle\mathcal{X}_{\max}\overset{\mathcal{D}}{\to}\mathrm{Gumbel}(\beta\ln(m)+\mu,\beta). Proof. By the definition of convergence in distribution ( Definition 6 ) and the Gumbel distribution ( Definition 5 ), for every t and j\in[m] , \lim_{n\to\infty}\Pr\left[X_{j}^{(n)}\leq t\right]=e^{-e^{-\frac{(t-\mu)}{\beta}}}. For every fixed n\in\mathbb{N} , since X_{1}^{(n)},\ldots,X_{m}^{(n)} are i.i.d., for every fixed t and m , we have \Pr\left[X_{\max}^{(n)}\leq t\right]=\Pr\left[\forall j\in[m],X_{j}^{(n)}\leq t\right]=\Pr\left[X_{1}^{(n)}\leq t\right]^{m}. Therefore, for any fixed t,m , \lim_{n\to\infty}\Pr\left[X_{\max}^{(n)}\leq t\right]=\lim_{n\to\infty}\Pr\left[X_{1}^{(n)}\leq t\right]^{m}=\exp\left(-e^{-\frac{(t-\mu)}{\beta}}\right)^{m}=\exp\left(-e^{-\frac{(t-(\mu+\beta\ln(m))}{\beta}}\right). By Definition 5 and Definition 6 , we conclude that \mathcal{X}_{\max}\overset{\mathcal{D}}{\to}\text{Gumbel}(\beta\ln(m)+\mu,\beta) as required. ∎ For the following definition we shall need the following notation of an indicator. Let E be any event. Then, define \mathds{1}_{E}=\begin{cases}1&\text{if }E\text{ occurs}\\ 0&\text{otherwise}\end{cases} Definition 7 (Uniformly integrable, Definition 4.1 [ Gut12 ] ) . A sequence \mathcal{X}=X^{(1)},X^{(2)},\ldots of random variables with finite expectation is called uniformly integrable if for any n\in\mathbb{N} , it holds that \mathbb{E}[|X^{(n)}|\cdot\mathds{1}_{|X^{(n)}|>K}]\to 0\text{ as }K\to\infty , uniformly in n . For a sequence of uniformly integrable variables, we have the following. Theorem 6 (Theorem 3.5, [ Bil13 ] ) . Let \mathcal{X}=X^{(1)},X^{(2)},\dots be a uniformly integrable sequence such that \mathcal{X}\overset{\mathcal{D}}{\to}X to some random variable X . Then X has finite expectation and \lim_{n\to\infty}\mathbb{E}[X^{(n)}]=\mathbb{E}[X] . Throughout the paper, we shall want to prove that a sequence of random variables is uniformly integrable. The following lemma gives a sufficient condition for that. Lemma 2 . Let \mathcal{X}=X^{(1)},X^{(2)},\dots be a sequence of random variables and assume there exist C,c>0 such that for every t\geq 0 and any n\in\mathbb{N} , it holds that \Pr[|X^{(n)}|>t]\leq Ce^{-ct} . Then, \mathcal{X} is uniformly integrable. Proof. We will verify that the two conditions specified in Definition 7 hold. 1. For every n\in\mathbb{N} , we have that \displaystyle\mathbb{E}[|X^{(n)}|] \displaystyle=\int_{0}^{\infty}\Pr\left[|X^{(n)}|>t\right]dt \displaystyle\leq C\int_{0}^{\infty}e^{-ct}dt=\frac{C}{c}<\infty\;. Thus, X^{(n)} has finite expectation. 2. For any n\in\mathbb{N} and positive K , \displaystyle 0\leq\mathbb{E}[|X^{(n)}|\cdot\mathds{1}_{|X^{(n)}|\geq K}] \displaystyle=\int_{K}^{\infty}\Pr\left[|X^{(n)}|>t\right]dt \displaystyle\leq C\int_{K}^{\infty}e^{-ct}dt=\frac{C}{c}e^{-cK}\;. Since \lim_{K\to\infty}\frac{C}{c}e^{-cK}=0 and is independent of n , \lim_{K\to\infty}\mathbb{E}[|X^{(n)}|\cdot\mathds{1}_{|X^{(n)}|\geq K}]=0 uniformly in n . We conclude that \mathcal{X} is uniformly integrable. ∎ 4 Warmup: Proof of Theorem 2 We start by introducing the notations of this section. Let m be a constant positive integer. For all j\in[m] , let \mathcal{X}_{j}=\{X_{j}^{(n)}\}_{n\geq 2} be a sequence of random variables where X_{j}^{(n)}\sim\text{CCP}(n) . Furthermore, we assume that for every fixed n\in\mathbb{N} , the variables X_{1}^{(n)},\ldots,X_{m}^{(n)} are i.i.d. For every n\in\mathbb{N} , let X_{\max}^{(n)}\triangleq\max_{j\in[m]}X_{j}^{(n)} . We will be interested in the following normalized versions of \mathcal{X}_{1},\ldots,\mathcal{X}_{m} . For every j\in[m] and n\in\mathbb{N} , define Y_{j}^{(n)}\triangleq\frac{X_{j}^{(n)}}{n}-\ln n and Y_{\max}^{(n)}\triangleq\max_{j\in[m]}Y_{j}^{(n)} . Finally, for every j\in[m] , we set \mathcal{Y}_{j}\triangleq\{Y_{j}^{(n)}\}_{n\geq 2} and \mathcal{Y}_{\max}\triangleq\{Y_{\max}^{(n)}\}_{n\geq 2} . The proof of Theorem 2 consists of the following steps. First, in 1 , we show that \mathcal{Y}_{\max} converges in distribution to the Gumbel distribution with \mu=\ln m and \beta=1 . Then, in 2 , we bound the tails of Y_{\max}^{(n)} which is needed to show in Corollary 3 , that \mathcal{Y}_{\max} is uniformly integrable. Finally, to prove Theorem 2 we will apply Theorem 6 . Claim 1 . It holds that \displaystyle\mathcal{Y}_{\max}\overset{\mathcal{D}}{\to}\mathrm{Gumbel}(\ln(m),1). Proof. Note that for all n\in\mathbb{N} , and every j\in[m] we have that nY_{j}^{(n)}+n\ln n\sim\text{CCP}(n) . By Theorem 5 , \lim_{n\to\infty}\Pr\left[nY_{j}^{(n)}+n\ln n>n\ln n+cn\right]=1-{e^{-e}}^{-c}\;, which implies that \lim_{n\to\infty}\Pr[Y_{j}^{(n)}\leq c]={e^{-e}}^{-c}\;, and thus, by Definition 6 , the sequence \mathcal{Y}_{j}=Y_{j}^{(1)},Y_{j}^{(2)},\ldots converges in distribution to \mathrm{Gumbel}(0,1) . Applying Lemma 1 with \mathcal{Y}_{1},\ldots,\mathcal{Y}_{m} proves the claim. ∎ Claim 2 . For any n\geq 2 and any x\geq 0 , \Pr\left[\left|Y_{\max}^{(n)}\right|>x\right]\leq(2+m)\cdot e^{-x}. Proof. We first show that \Pr[Y_{\max}^{(n)}>x]\leq m\cdot e^{-x} . Indeed, By the definition of Y_{\max}^{(n)} , we have \displaystyle\Pr\left[Y_{\max}^{(n)}>x\right] \displaystyle=\Pr\left[X_{\max}^{(n)}>n(\ln n+x)\right] \displaystyle=\Pr\left[\text{some coupon was {not} collected at time }n(\ln n+x)\right] \displaystyle\leq nm\left(1-\frac{1}{n}\right)^{n(\ln n+x)} \displaystyle\leq me^{-x}\;, where the first inequality is by a union bound. Now, we show that \Pr[Y_{\max}^{(n)}<-x]\leq 2e^{-x} . First observe that \Pr\left[Y_{\max}^{(n)}<-x\right]\leq\Pr\left[Y_{\max}^{(n)}\leq-x\right]=\Pr\left[Y_{1}^{(n)}\leq-x\right]^{m}=\Pr\left[X_{1}^{(n)}\leq n(\ln n-x)\right]^{m}\;. Next, we shall bound \Pr[X_{1}^{(n)}x\right] can be exponentially bounded and that the bound does not depend on n . Claim 3 . There exists C_{0}=C_{0}(\ell,m) , such that for any x\geq 0 , \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}>x\right]\leq C_{0}e^{-\frac{x}{2}}. Proof. Denote t\triangleq n(\ln n+(\ell-1)\ln\ln n+x) . We have that \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}>x\right] \displaystyle=\Pr\left[X_{\max}^{(n,\ell)}>t\right] \displaystyle=\Pr\left[\text{some coupon was collected {less} than $\ell$ times at time }t\right] \displaystyle\leq nm\cdot\Pr\left[\text{a specific coupon was collected {less} than $\ell$ times at time }t\right] \displaystyle=nm\cdot\Pr\left[\text{Bin}\left(t,\frac{1}{n}\right)\leq\ell-1\right] \displaystyle=nm\cdot\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n}\right)^{r}\left(1-\frac{1}{n}\right)^{t-r} \displaystyle=nm\left(1-\frac{1}{n}\right)^{t}\cdot\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n}\right)^{r}\left(1-\frac{1}{n}\right)^{-r} \displaystyle=nm\left(1-\frac{1}{n}\right)^{t}\cdot\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r} \displaystyle\leq nm\left(1-\frac{1}{n}\right)^{t}\cdot\sum_{r=0}^{\ell-1}\left(\frac{t}{n-1}\right)^{r} \displaystyle\leq 2^{\ell}m\ell\cdot ne^{-\frac{t}{n}}\left(\frac{t}{n}\right)^{\ell-1}\;, where the first inequality is obtained via a union bound, the second inequality applies the bound \binom{a}{b}x_{0}(\ell) , x^{\ell-1}\leq e^{\frac{x}{2}} . Hence, for any x>x_{0}(\ell) , \displaystyle ne^{-\frac{t}{n}}\left(\frac{t}{n}\right)^{\ell-1}=e^{-x}\left(\frac{t}{n\ln n}\right)^{\ell-1}\leq e^{-x}\left(\ell+2x\right)^{\ell-1}\leq 3^{\ell-1}e^{-\frac{x}{2}}, where the first inequality holds since \frac{t}{n\ln n}=1+\frac{(\ell-1)\ln\ln n}{\ln n}+\frac{x}{\ln n}<\ell+2x , and the second inequality holds by the requirements on x_{0}(\ell) . Put it all together, \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}>x\right]\leq 2^{\ell}m\ell\cdot ne^{-\frac{t}{n}}\left(\frac{t}{n}\right)^{\ell-1}\leq 2^{\ell}3^{\ell-1}m\ell e^{-\frac{x}{2}}. In addition, for any 0\leq x\leq x_{0}(\ell) , \Pr[Y_{\max}^{(n,\ell)}>x]\leq 1\leq e^{x_{0}(\ell)}e^{-\frac{x}{2}} . Denote C_{0}(\ell,m)\triangleq\max\left\{e^{x_{0}(\ell)},3^{2\ell-1}m\ell\right\} . Then, \Pr[Y_{\max}^{(n,\ell)}>x]\leq C_{0}(\ell,m)e^{-\frac{x}{2}} for any x\geq 0 as required. ∎ To bound the left tail, namely, to bound \Pr\left[Y_{\max}^{(n,\ell)}<-x\right] , we will need the notion of negatively associated random variables. Definition 8 (Negative association) . A collection X_{1},X_{2},\dots,X_{n} of random variables is called negatively associated (NA) if for every two disjoint index sets, I,J\subseteq[n] , and every f:\mathbb{R}^{|I|}\to\mathbb{R} and g:\mathbb{R}^{|J|}\to\mathbb{R} that are both non-decreasing or both non-increasing, we have \mathbb{E}\left[f\left(X_{i},i\in I\right)g\left(X_{j},j\in J\right)\right]\leq\mathbb{E}\left[f\left(X_{i},i\in I\right)\right]\mathbb{E}\left[g\left(X_{j},j\in J\right)\right]\;. Equivalently, \mathrm{Cov}(f(X_{i},i\in I),g(X_{j},j\in J))\leq 0 . Theorem 8 (Theorem 13, [ DR96 ] ) . Suppose we throw m balls into n bins independently at random. For i\in[n] , let B_{i} be the random variable denoting the number of balls in the i th bin. Then, the variables B_{1},\ldots,B_{n} are NA. Claim 4 . There exists C_{1}=C_{1}(\ell) , such that for any x\geq 0 , \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}\leq-x\right]\leq C_{1}e^{-\frac{x}{2}}. Proof. Similarly to the proof of 2 , \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}\leq-x\right]=\Pr\left[Y_{1}^{(n,\ell)}\leq-x\right]^{m}\leq\Pr\left[Y_{1}^{(n,\ell)}\leq-x\right]=\Pr\left[X_{1}^{(n,\ell)}\leq n\left(\ln n+\left(\ell-1\right)\ln\ln n-x\right)\right]. Fix x , and define t\triangleq n(\ln n+(\ell-1)\ln\ln n-x) . If x>\ln n+(\ell-1)\ln\ln n-\ell , then t0 . Therefore, for the rest of the proof, we assume that 0\leq x\leq\ln n+(\ell-1)\ln\ln n-\ell . Let B_{j}^{(t)} be the number of copies of coupon j after the first t draws of one collector, and define I^{(t)}_{j}\triangleq\mathds{1}_{B_{j}^{(t)}<\ell} . Then I^{(t)}_{j} is the indicator that coupon j has less than \ell copies after the first t draws, and W^{(t)}\triangleq\sum_{j=1}^{n}I^{(t)}_{j} is the number of such coupons. Hence, \displaystyle\Pr\left[X_{1}^{(n,\ell)}\leq n\left(\ln n+(\ell-1)\ln\ln n-x\right)\right]=\Pr\left[X_{1}^{(n,\ell)}\leq t\right]=\Pr\left[W^{(t)}=0\right]. Analogously to the proof of 2 , we now derive bounds on the expectation and variance of W^{(t)} in order to obtain an upper bound on \Pr[W^{(t)}=0] . Note that the variables B_{1}^{(t)},\ldots,B_{n}^{(t)} correspond exactly to the balls and bins paradigm (with t balls and n bins), and thus, they are NA according to Theorem 8 . Moreover, observe that the indicator function f(B)=\mathds{1}_{B<\ell} is non-increasing, thus for any i\neq j , \mathrm{Cov}(I^{(t)}_{i},I^{(t)}_{j})\leq 0 . Therefore, \displaystyle\mathrm{Var}\left(W^{(t)}\right) \displaystyle=\sum_{j\in[n]}\mathrm{Var}\left(I_{j}^{(t)}\right)+2\sum_{1\leq j0. Hence, by the Chebyshev inequality, \displaystyle\Pr\left[W^{(t)}=0\right]\leq\Pr\left[\left|W^{(t)}-\mathbb{E}\left[W^{(t)}\right]\right|\geq\mathbb{E}\left[W^{(t)}\right]\right]\leq\frac{\mathrm{Var}\left(W^{(t)}\right)}{\mathbb{E}\left[W^{(t)}\right]^{2}}\leq\frac{1}{\mathbb{E}\left[W^{(t)}\right]}. In addition, \displaystyle\mathbb{E}\left[W^{(t)}\right] \displaystyle=n\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n}\right)^{r}\left(1-\frac{1}{n}\right)^{t-r} \displaystyle=n\left(1-\frac{1}{n}\right)^{t}\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r} \displaystyle\geq ne^{-\frac{t}{n-1}}\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r}. Divide into cases: 1. 2(\ell-1)\ln\ln n\leq x : \displaystyle ne^{-\frac{t}{n-1}}\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r} \displaystyle\geq ne^{-\frac{t}{n-1}}=n^{-\frac{1}{n-1}}e^{\frac{n}{n-1}(x-(\ell-1)\ln\ln n)}\geq\frac{1}{2}e^{\frac{n}{n-1}\frac{x}{2}}\geq\frac{1}{2}e^{\frac{x}{2}}, where the second inequality holds by the requirements on x and the monotonicity of n^{-1/(n-1)} . 2. 0\leq x\leq 2(\ell-1)\ln\ln n : Let n_{1}=n_{1}(\ell) be such that for any n>n_{1} : (a) \ln n\geq 2(\ell-1)\ln\ln n (b) \left(\ln n\right)^{-\frac{\ell-1}{n-1}}>\frac{1}{2} In this case, we have \displaystyle\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r} \displaystyle\geq\binom{t}{\ell-1}\left(\frac{1}{n-1}\right)^{\ell-1} \displaystyle\geq\frac{1}{(\ell-1)^{\ell-1}}\left(\frac{t}{n-1}\right)^{\ell-1} \displaystyle=\frac{1}{(\ell-1)^{\ell-1}}\left(\frac{n(\ln n+(\ell-1)\ln\ln n-x)}{n-1}\right)^{\ell-1} \displaystyle\geq\frac{1}{(\ell-1)^{\ell-1}}\left(\ln n-(\ell-1)\ln\ln n\right)^{\ell-1} \displaystyle\geq\frac{1}{(\ell-1)^{\ell-1}2^{\ell-1}}\left(\ln n\right)^{\ell-1}\;, where the first inequality just considers the last summand, the second inequality applies the bound \binom{a}{b}\geq a^{a}/b^{b} , and the last inequality is due to our assumption 2a on n . Thus, \displaystyle ne^{-\frac{t}{n-1}}\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r} \displaystyle\geq ne^{-\frac{t}{n-1}}\frac{1}{(\ell-1)^{\ell-1}2^{\ell-1}}\left(\ln n\right)^{\ell-1} \displaystyle=n^{-\frac{1}{n-1}}e^{-\frac{n}{n-1}((\ell-1)\ln\ln n-x)}\frac{1}{(\ell-1)^{\ell-1}2^{\ell-1}}\left(\ln n\right)^{\ell-1} \displaystyle\geq\frac{1}{(\ell-1)^{\ell-1}2^{\ell}}e^{x}\left(\ln n\right)^{-\frac{\ell-1}{n-1}} \displaystyle\geq\frac{1}{(\ell-1)^{\ell-1}2^{\ell+1}}e^{x}, where the last inequality holds due to assumption 2b on n . Therefore, for the cases where either n>n_{1} or n\leq n_{1} and 2(\ell-1)\ln\ln n\leq x , \displaystyle\mathbb{E}\left[W^{(t)}\right] \displaystyle\geq ne^{-\frac{t}{n-1}}\sum_{r=0}^{\ell-1}\binom{t}{r}\left(\frac{1}{n-1}\right)^{r} \displaystyle\geq\min\left\{\frac{1}{2}e^{\frac{x}{2}},\frac{1}{(\ell-1)^{\ell-1}2^{\ell+1}}e^{x}\right\} \displaystyle\geq\frac{1}{(\ell-1)^{\ell-1}2^{\ell+1}}e^{\frac{x}{2}}\;, and therefore, \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}\leq-x\right] \displaystyle\leq\Pr\left[W^{(t)}=0\right] \displaystyle\leq\frac{1}{\mathbb{E}\left[W^{(t)}\right]} \displaystyle\leq(\ell-1)^{\ell-1}2^{\ell+1}e^{-\frac{x}{2}}. Lastly, for the case where x\leq 2(\ell-1)\ln\ln n and 2\leq n\leq n_{1} , it holds that x\leq 2(\ell-1)\ln\ln n\leq 2(\ell-1)\ln\ln n_{1} , and \displaystyle\Pr\left[Y_{\max}^{(n,\ell)}\leq-x\right]\leq 1=\left(\ln n_{1}\right)^{(\ell-1)}e^{-(\ell-1)\ln\ln n_{1}}\leq\left(\ln n_{1}\right)^{(\ell-1)}e^{-\frac{x}{2}}. We conclude the proof of the lemma by noting that for C_{1}(\ell)\triangleq\max\{(\ell-1)^{\ell-1}2^{\ell+1},(\ln n_{1})^{(\ell-1)}\} and any x\geq 0,n\geq 2 , it holds that \Pr\left[Y_{\max}^{(n,\ell)}<-x\right]\leq C_{1}(\ell)e^{-\frac{x}{2}} as required. ∎ Corollary 5 . The sequence \left\{Y_{\max}^{(n,\ell)}\right\}_{n\geq 2} is uniformly integrable. Proof. By 3 and 4 , we have that, \displaystyle\Pr\left[\left|Y_{\max}^{(n,\ell)}\right|>x\right]\leq\Pr\left[Y_{\max}^{(n,\ell)}>x\right]+\Pr\left[Y_{\max}^{(n,\ell)}\leq-x\right]\leq\left(C_{0}+C_{1}\right)e^{-\frac{x}{2}}\;. The claim follows according to Lemma 2 . ∎ Now we will prove Theorem 3 which is restated for convenience. See 3 Proof. By Corollary 4 and Corollary 5 , \mathcal{Y}_{\max}=\left\{Y_{\max}^{(n,\ell)}\right\}_{n\geq 2} is uniformly integrable and converges in distribution to \text{Gumbel}\left(\ln\left(\frac{m}{(\ell-1)!}\right),1\right) . Therefore, by Theorem 6 , \displaystyle\lim_{n\to\infty}\mathbb{E}\left[Y_{\max}^{(n,\ell)}\right]=\mathbb{E}\left[\text{Gumbel}\left(\ln\left(\frac{m}{(\ell-1)!}\right),1\right)\right]=\ln\left(\frac{m}{(\ell-1)!}\right)+\gamma. We note that X_{\max}^{(n,\ell)}=n\ln n+n(\ell-1)\ln\ln n+nY_{\max}^{(n,\ell)} . Hence, \displaystyle\mathbb{E}[X_{\max}^{(n,\ell)}] \displaystyle=n\ln n+n(\ell-1)\ln\ln n+n\mathbb{E}\left[Y_{\max}^{(n,\ell)}\right] \displaystyle=n\left(\ln\left(nm\right)+\left(\ell-1\right)\ln\ln n+C_{\ell}\pm o(1)\right) where C_{\ell}=\gamma-\ln((\ell-1)!) . ∎ 6 Proof of Theorem 1 The proof of Theorem 1 is based on the same general framework as the proofs of Theorem 2 and Theorem 3 , namely, analyzing normalized versions of the relevant random variables and establishing their convergence in distribution and uniform integrability. Having said that, unlike the previous theorems, there is no well known normalization related to the problem. Consequently we had to find it and prove its limiting distribution. Throughout this section, we adopt the following notation. Let A^{(0)}={\boldsymbol{0}}^{n\times(m+\rho)},A^{(1)},A^{(2)},\ldots be a sequence of matrices constructed as follows: for each t\in\mathbb{N} , we draw (v_{1},\ldots,v_{m+\rho})\sim\mathrm{Unif}([n]^{m+\rho}) and set A^{(t)}=A^{(t-1)}+\left[{\boldsymbol{e}}_{v_{1}},\ldots,{\boldsymbol{e}}_{v_{m+\rho}}\right]\;, where {\boldsymbol{e}}_{a} denotes the column vector with a 1 in the a -th position and 0 in all other entries. Define T_{n,m,\rho} as the random variable that corresponds to the smallest t such that every row of A^{(t)} contains at least m nonzero entries. For each row i\in[n] and time t\geq 0 , let X_{i}(t) denote the number of nonzero entries in row i of A^{(t)} , and by E_{i}(t) the event that row i has less than m nonzero entries at time t , i.e., E_{i}(t)=\{(X_{1}(t),\ldots,X_{n}(t))\in([m+\rho]\cup\{0\})^{n}\mid X_{i}(t)k(\rho+1) , then ( 3 ) is o(n^{-k}) . As k,m , and \rho are constants and the number of total configurations is 2^{k(m+\rho)} , we get that \Pr\left[\boldsymbol{\xi}\text{ is valid and }\sum_{j=1}^{m+\rho}|\xi_{j}|>k(\rho+1)\right]\leq 2^{k(m+\rho)}\cdot o(n^{-k})=o(n^{-k})\;. Thus, since we cannot have a valid configuration \boldsymbol{\xi} with \sum_{j=1}^{m+\rho}|\xi_{j}|x]\leq 2^{m+\rho}e^{-x} Proof. Fix x\in\mathbb{R} and set u=\ln n+x , so that \Pr[Z_{n,m,\rho}>x]=\Pr[T_{n,m,\rho}>\frac{n}{\rho+1}u] . Recall that we define the random variable X_{i}(t) to represent the number of columns that were collected in the i -th row by time t . We have that X_{i}(t)\sim\textup{Bin}(m+\rho,p_{t}) where p_{t}=1-\left(1-\frac{1}{n}\right)^{t} is the probability that a specific column draws a specific row by time t . \displaystyle\Pr[X_{i}(t)x]=\Pr\left[T_{n,m,\rho}>\frac{n}{\rho+1}u\right]\leq 2^{m+\rho}e^{-x}\;. ∎ For the proof of the left tail, we recall some properties of NA random variables, Proposition 1 (Property P 6 , [ JDP83 ] ) . Non-decreasing functions defined on disjoint subsets of a set of NA random variables are NA. Proposition 2 (Property P 7 , [ JDP83 ] ) . The union of independent sets of NA random variables is NA. Claim 6 . For any x\geq 0 and 2\leq n\in\mathbb{N} : \displaystyle\Pr[Z_{n,m,\rho}\leq-x]\leq\frac{1}{C_{2}(m,\rho)}e^{-x} where C_{2}(m,\rho)=\frac{1}{2}\binom{m+\rho}{m-1}(1-e^{-\frac{m}{m+\rho}})^{m-1} . Proof. Fix x,n , and set t=\frac{n}{\rho+1}(\ln n-x) . If x>\ln n-\frac{(\rho+1)m}{m+\rho} then t=\frac{n}{\rho+1}(\ln n-x)<\frac{nm}{m+\rho} , which is the minimal number of rounds in order to have at least m nonzero entries in each row, and in particular \Pr[Z_{n,m,\rho}\leq-x]=\Pr[T_{n,m,\rho}\leq t]=0\leq Ce^{-x} for any C>0 . Assume that 0\leq x\leq\ln n-\frac{(\rho+1)m}{m+\rho} and let W^{(t)} be the number of rows with less than m nonzero entries in A^{(t)} : W^{(t)}=\sum_{i=1}^{n}I_{i}^{(t)} where I_{i}^{(t)} is the indicator that row i of A^{(t)} has less than m nonzero entries. We have that \displaystyle\Pr[Z_{n,m,\rho}\leq-x]=\Pr[T_{n,m,\rho}\leq t]=\Pr[W^{(t)}=0]. For every i_{1}\neq i_{2} , \mathrm{Cov}(I_{i_{1}}^{(t)},I_{i_{2}}^{(t)})\leq 0 : Similarly to the proof of 4 , for any fixed j , by Theorem 8 the set of entries \{A_{i,j}^{(t)}\}_{i\in[n]} is NA. For any j_{1}\neq j_{2} the sets are independent, hence, by Proposition 2 the entire set \{A_{i,j}^{(t)}\}_{i\in[n],j\in[m+\rho]} is NA. For any i\in[n],j\in[m+\rho] let I_{i,j}^{(t)} be the indicator that A_{i,j}^{(t)} is nonzero. Since these are non-decreasing functions defined on disjoint subsets of a set of NA random variables, the set \{I_{i,j}\}_{i\in[n],j\in[m+\rho]} is NA. Note that X_{i}(t)=\sum_{j=1}^{m+\rho}I_{i,j}^{(t)} , therefore by Proposition 1 \left\{X_{i}(t)\right\}_{i\in[n]} are NA. Finally, since the indicator function f(X)=\mathds{1}_{X0. Thus, \displaystyle\mathbb{E}[W^{(t)}]\geq n\binom{m+\rho}{m-1}p_{t}^{m-1}(1-p_{t})^{\rho+1}\geq\frac{1}{2}\binom{m+\rho}{m-1}(1-e^{-\frac{m}{m+\rho}})^{m-1}e^{x}. Therefore, for C_{2}(m,\rho)\triangleq\frac{1}{2}\binom{m+\rho}{m-1}(1-e^{-\frac{m}{m+\rho}})^{m-1} we obtain that \displaystyle\Pr[Z_{n,m,\rho}\leq-x] \displaystyle=\Pr[W^{(t)}=0] \displaystyle\leq\Pr\left[|W^{(t)}-\mathbb{E}[W^{(t)}]|\geq\mathbb{E}[W^{(t)}]\right] \displaystyle\leq\frac{\mathrm{Var}(W^{(t)})}{\mathbb{E}[W^{(t)}]^{2}} \displaystyle\leq\frac{1}{\mathbb{E}[W^{(t)}]} \displaystyle\leq\frac{1}{C_{2}(m,\rho)}e^{-x}. as claimed. ∎ Corollary 6 . The sequence \left\{Z_{n,m,\rho}\right\}_{n\geq 2} is uniformly integrable. Proof. By 5 and 6 , for every x\in\mathbb{R},n\geq 2 we have that, \displaystyle\Pr\left[\left|Z_{n,m,\rho}\right|>x\right]\leq\Pr\left[Z_{n,m,\rho}>x\right]+\Pr\left[Z_{n,m,\rho}\leq-x\right]\leq\left(2^{m+\rho}+\frac{1}{C_{2}(m,\rho)}\right)e^{-x}\;. The corollary follows according to Lemma 2 . ∎ We can now complete the proof of Theorem 1 , restated below for clarity. See 1 Proof. According to Corollary 6 , and Theorem 9 , the sequence \left\{Z_{n,m,\rho}\right\}_{n\geq 2} is uniformly integrable and converges in distribution to \mathrm{Gumbel}(\ln\binom{m+\rho}{m-1},1) . Therefore, by Theorem 6 , we have that \displaystyle\lim_{n\to\infty}\mathbb{E}\left[Z_{n,m,\rho}\right]=\ln\binom{m+\rho}{m-1}+\gamma. Recall that T_{n,m,\rho}=\frac{n}{\rho+1}\left(Z_{n,m,\rho}+\ln n\right) , hence, \displaystyle\mathbb{E}\left[T_{n,m,\rho}\right]=\frac{n}{\rho+1}\ln n+\frac{n}{\rho+1}\ln\binom{m+\rho}{m-1}+\frac{n}{\rho+1}\gamma\pm o(n). ∎ 7 Proof of Theorem 4 We start by recalling the statement of the theorem. See 4 We will first prove the following upper bound Claim 7 . For every positive x , we have \Pr\left[T\geq\frac{n}{\alpha^{*}}\cdot(\ln n+x)\right]\leq\frac{\beta^{*}}{b}\cdot e^{-x}\left(1+(mb)^{2}n^{-\frac{1}{\alpha^{*}}}\right)\;. Proof. Define t\triangleq\frac{n}{\alpha^{*}}(\ln n+x) . We begin by focusing only on the first block, i.e., the case a=1 . Our goal is to upper bound the probability that, at time t , the collection of all nonzero entries is still a bad set, that is, lies in \mathcal{B} . This will ensure that the block is not yet in a recovering state. More precisely, we will prove that \Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}\neq 0\right\}\in\mathcal{B}\right]\leq\beta^{*}\cdot n^{-1}e^{-x}\left(1+(mb)^{2}n^{-\frac{1}{\alpha^{*}}}\right)\;. Then, the claim will follow from taking a union bound over all the n/b blocks. It holds that \Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}\neq 0\right\}\in\mathcal{B}\right]=\sum_{B\in\mathcal{B}}\Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}\neq 0\right\}=B\right]\;. Fix B\in\mathcal{B} and denote by \overline{B} its complement in the block, i.e., B\cup\overline{B}=[b]\times[m] and B\cap\overline{B}=\emptyset . We have \Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}\neq 0\right\}=B\right]=\Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}=0\right\}=\overline{B}\right]\;, and if we denote s_{j}\triangleq|\{i\in[b]\mid(i,j)\in\overline{B}\}| , then, \Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}=0\right\}=\overline{B}\right]=\prod_{j=1}^{m}\left(1-\frac{s_{j}}{n}\right)^{t}\leq\prod_{j=1}^{m}\left(1-\frac{1}{n}\right)^{s_{j}t}=\left(1-\frac{1}{n}\right)^{(mb-|B|)\cdot t}\;. Now, observe that this upper bound depends only on the size of B . Thus, \Pr\left[\left\{(i,j)\in\left[b\right]\times[m]\mid A_{i,j}^{(t)}\neq 0\right\}\in\mathcal{B}\right]\leq\sum_{B\in\mathcal{B}}\left(1-\frac{1}{n}\right)^{(mb-|B|)\cdot t}\leq\sum_{B\in\mathcal{B}}e^{-\frac{(mb-|B|)(\ln n+x)}{\alpha^{*}}}\;. Note that mb-|B|\geq\alpha^{*} . For all s\in[0,mb] , denote by \beta_{s}\triangleq|\{B\in\mathcal{B}\mid|B|=s\}| , i.e., the number of the sets in \mathcal{B} of size exactly s . Furthermore, set s^{*}\triangleq mb-\alpha^{*} . Then, \displaystyle\sum_{B\in\mathcal{B}}e^{-\frac{(mb-|B|)(\ln n+x)}{\alpha^{*}}} \displaystyle=\sum_{s=s^{*}}^{mb}\beta_{s}\cdot e^{-\frac{(mb-s)(\ln n+x)}{\alpha^{*}}} \displaystyle\leq\beta_{s^{*}}\cdot n^{-1}e^{-x}+\sum_{s=s^{*}+1}^{mb}\beta_{s}\cdot e^{-\frac{\alpha^{*}+1}{\alpha^{*}}\cdot(\ln n+x)} \displaystyle\leq\beta_{s^{*}}\cdot n^{-1}e^{-x}\left(1+(mb)^{2}n^{-\frac{1}{\alpha^{*}}}\right)\;. The claim follows by a union bound over all a\in[n/b] . ∎ With this bound, we can prove Theorem 4 . Proof of Theorem 4 . Define t_{0}=(n\ln n)/\alpha^{*} . It holds that \mathbb{E}[T]=\sum_{t\geq 1}\Pr[T\geq t]=\sum_{t=1}^{t_{0}-1}\Pr[T\geq t]+\sum_{t=t_{0}}^{\infty}\Pr[T\geq t]\;. The first sum can be bounded trivially by t_{0} (every term in the sum is at most 1 ). We focus on the second sum. \displaystyle\sum_{t=t_{0}}^{\infty}\Pr[T\geq t] \displaystyle=\sum_{k=0}^{\infty}\Pr\left[T\geq\frac{n\ln n}{\alpha^{*}}+k\right] \displaystyle\leq\sum_{k=0}^{\infty}\Pr\left[T\geq\frac{n}{\alpha^{*}}\left(\ln n+k\cdot\frac{\alpha^{*}}{n}\right)\right] \displaystyle\leq\frac{\beta_{s^{*}}}{b}\cdot\left(1+(mb)^{2}n^{-\frac{1}{\alpha^{*}}}\right)\cdot\sum_{k=0}^{\infty}e^{-k\cdot\frac{\alpha^{*}}{n}} \displaystyle\leq\frac{\beta_{s^{*}}}{b}\cdot\left(1+(mb)^{2}n^{-\frac{1}{\alpha^{*}}}\right)\cdot\frac{1}{1-e^{-\frac{\alpha^{*}}{n}}}\;. Now, by Taylor expansion, 1-e^{-x}=x-x^{2}/2+O(x^{3}) , we conclude that \mathbb{E}[T]\leq\frac{n}{\alpha^{*}}\ln n+\frac{\beta_{s^{*}}}{b\alpha^{*}}\cdot n\cdot(1+m^{2}bn^{-\frac{1}{\alpha^{*}}})(1+o(1))\;, and the result follows by recalling that m and b are constant with respect to n . ∎