--- abstract: 'Consider $ m $ copies of an irreducible, aperiodic Markov chain $ Y $ taking values in a finite state space. The asymptotics as $ m $ tends to infinity, of the first time from which on the trajectories of the $ m $ copies differ, have been studied by Szpankowski (1991) in the setting of tries. We use a different approach and model the $ m $ trajectories by a variant of the occupancy scheme, where we consider a nested sequence of boxes. This approach will enable us to extend the result to the case when the transition probabilities are random. We moreover use the same techniques to study the asymptotics as $ m $ tends to infinity of the time up to which we have observed all the possible trajectories of $ Y $ in random and nonrandom scenery.' author: - Silvia Businger bibliography: - 'sample-dmtcs.bib' nocite: '[@*]' title: | Asymptotics of the occupancy scheme\ in a random environment and its applications to tries --- Introduction ============ Let $Y= (Y_k)_{k \in \mathbb{N}} $ be an irreducible, aperiodic Markov chain taking values in a finite state space, say $ \Sigma= \lbrace 1,...,K \rbrace $, denote its transition probabilities by $ (p_{ij}, i,j \in \Sigma) $, and consider $ m $ independent copies of $ Y $. We define $ H_m \in \mathbb{N}$, the first time from which on the trajectories of the $ m $ copies differ and $ G_m \in \mathbb{N} $, the maximal time up to which we have observed all the possible trajectories of $ Y $. A natural question which has generated a lot of interest in the literature concerns the asymptotic behavior of $ H_m $ and $ G_m $ as $ m $ tends to infinity. Typically in information theory one considers the Markov source model (see for example @Ash), that is an infinite data string is modeled by the trajectory of a Markov chain taking values in a finite alphabet $ \Sigma $. We call the first $ n $ letters of the data string a word of length $ n $. If we consider $ m $ independent data strings modeled by a Markov source, then $ H_{m} $ is the minimal length $ n $ such that the $ m $ words with length $ n $ are all distinct. In the same spirit $ G_{m} $ describes up to which length we observe all the possible words. More generally we will consider $ H_{m,j} $ the minimal length such that out of the $ m $ words with length $ n $ at most $ j-1 $ words are non-distinct, and $ G_{m,j} $ describing up to which length we observe all the possible words at least $ j $ times. The length $ H_m $ can be described in terms of a class of combinatorial trees, the so called $ K $-ary tries that can be constructed with an iterative procedure. Consider $ m $ words with letters in the alphabet $ \Sigma $. We start with the root of a tree. We then look at the first letter of the $ m $ words. For each different letter we add a node to the root, in increasing order. If for a letter there is only one word starting with this letter, then the corresponding node will be a leaf of the tree and we store the word in that leaf. We then look at the second letters of the words not yet being stored in a leaf. If there are at least two words starting with the letter $ i \in \Sigma$, we then look at the second letters of all the words starting with $ i $. For each different letter we add a node to the node $ i $ in the same way as in the first step. We then repeat this procedure until all the words are stored in a leaf. For more details see for example @drmota. When the data strings have been generated by a Markov source then the height of this $ K $-ary trie is equal to $ H_m $. The height of tries have been a subject in research for many years, see @Flajolet and @Devroye. The limit law of the height has finally been derived by @Pittel, see also @Pittel2. The Markov source model, was studied by @S. He established that $$H_{m} \sim \frac{2}{-\ln(\rho(2))}\ln(m), \quad a.s.,$$ as $ m $ tends to infinity, where $ \rho(2) $ denotes the maximum modulus eigenvalue of the matrix $ A(2)= (p_{ik}^{2})_{i,k \in \Sigma} $, by analyzing the longest common prefix of each possible pair of two data strings. This result can be extended to the case when each external node is allowed to store up to $ j-1 $ data strings. The tree defined by this modification is called a $ (j-1)$-trie. Szpankowski (see @S and @S2) studied the asymptotics of the height of a $ (j-1) $-trie, he established that $$H_{m,j} \sim \frac{j}{-\ln(\rho(j))}\ln(m), \quad a.s.,$$ as $ m $ tends to infinity, where $ \rho(j) $ denotes the maximum modulus eigenvalue of the matrix given by $ A(j)= (p_{ik}^{j})_{i,k \in \Sigma} $. Our purpose in this work is to investigate a similar problem in random environment. This is a natural model if for instance one wants to take into account transmission errors in the setting of information theory. In order to explain how, in our model, the random environment acts on the trajectories of chains, let us first recall a simple construction of i.i.d. copies of the Markov chain $Y$ with transition matrix $(p_{ik})_{i,k \in \Sigma}$ using the balls-in-bins setting (see, e.g. @Devroye2). For a general introduction to balls-in-bins in deterministic environment and the classical occupancy scheme with finitely many boxes see for example @Kolchin or @Kotz. There is a broad literature on the occupancy scheme in deterministic environment and comparatively few investigations of the occupancy scheme in random environment. An infinite occupancy scheme in a random environment called the Bernoulli sieve has been introduced in @Gnedin and then studied in depth, a survey can be found for example in @Gnedin2. A scheme of a similar type can also be found in @Robert. The set of words with length $n$ in the alphabet $\Sigma$ is $\Sigma^{n}$, with the convention that for $n=0$, $\Sigma^{0}=\{ \emptyset \}$ is the empty word. For the sake of simplicity, we assume that the initial state of the Markov chain $Y$ is always $1$, and construct a nested family of boxes (or bins) indexed by the regular $ K $-ary tree $\mathcal{U}= \bigcup_{n \in\mathbb{Z}_+}\Sigma^{n}$ as follows. At generation $ 0$, there is a single box $b_{\emptyset}$ with unit size and type $1$. At the first generation, we divide the box $b_{\emptyset}$ into $(b_i: i\in \Sigma)$ where $b_i$ has type $i$ and size $\vert b_i \vert=p_{1i}$. We iterate for the next generations in an obvious way. For each word ${u}=(i_1, \ldots, i_n)\in \Sigma^n$, the box $b_{{u}}$ has type $i_n$ and is split at the next generation into sub-boxes $(b_{{u} k}: k\in \Sigma)$, where $b_{{u} k}$ has type $k$ and size $|b_{{u} k}|=|b_{{u}}|p_{i_nk} $. Now imagine that we throw a ball into the initial box, distribute it uniformly at random to the next generation of boxes, and observe the sequence of the types of the sub-boxes it passes through, generation after generation. We then clearly obtain a version of the Markov chain $Y$, and more generally, throwing $m$ balls independently yields the trajectories of $m$ i.i.d. copies of $Y$. In this setting, the height $ H_{m,j} $ of a $(j-1)$-trie corresponds to the first generation at which all boxes contain strictly less than $j$ balls. For $ j \geq 1 $ the first generation when there is a box containing strictly less than $ j $ balls when $ m $ balls have been thrown corresponds to $ G_{m,j} $, and is referred to as saturation level. The random environment that we shall consider corresponds to splitting boxes randomly rather than deterministically, in a Markovian manner. More precisely, we now consider for each word ${u}=(i_1, \ldots, i_n)\in \Sigma^n$, an independent copy $A_{u}=(p_{ik}(u))_{i,k \in\Sigma}$ of a <span>*random*</span> transition matrix $A=(p_{ik})_{i,k \in\Sigma}$. The box $b_{{u}}$ with type $i_n$ is split at the next generation into $(b_{{u} k}: k\in \Sigma)$, where $b_{{u} k}$ has type $k$ and size $|b_{{u} k}|=|b_{{u}}|p_{i_nk}(u)$. Then throwing $ m $ balls uniformly at random yields the $m$ data strings in random environment that we are interested in. Note that knowing the family of box sizes, the trajectory of a ball through boxes is not described by a Markov chain. It is thus not possible to reduce the study to applying the results due to Szpankowski by conditioning on the environment. In order to investigate the behavior of the heights $H_{m,j}$ and saturation levels $G_{m,j}$ as $m$ tends to infinity, we shall first show how the results by Szpankowski in deterministic environment can be recovered using an occupancy scheme analysis. Even though the main result has already been established by different arguments, we shall provide a detailed account as the same approach can then be adapted to the random environment setting. Specifically, we shall investigate the distribution of the sizes of the boxes at a large generation $n$, being especially interested in large deviation type estimates. We will moreover use the same techniques to study the asymptotics of the height $ H_{m,j} $ when $ j $ depends on $ m $, more precisely $ j=j(m)=m^{\alpha} $ for $ \alpha \in (0,1) $. We shall then show that this approach can be adapted in the random environment setting. In this direction, we shall first observe that taking the logarithm of the sizes of boxes yields a multitype branching random walk, which then enables us to apply large deviations estimates due to @biggins. We will see that different from the nonrandom case there is a phase transition in the asymptotic behavior of $ H_{m,j} $ as $ m $ tends to infinity and that $$H_{m,j} \sim C(j) \cdot \ln(m) \quad a.s.$$ where $ C(j) $ is a constant depending on $ j $ for $ j $ smaller than a critical parameter and $ C(j)=\zeta^* $ is a constant arising in the limit behavior of the largest box for $ j $ larger than the critical parameter. The study of the limiting behavior of the saturation level is closely related to the coupon collector's problem. (See for example @coupon). We will consider each box of generation $ n $ as a coupon, each of a different sort and suppose that a collector wants to have at least one of each sort. We say that a collector buys a certain coupon if a ball lands in the corresponding box. Then $ G_{m,j} $ is the first generation $ n $ when the collector fails to have at least $ j $ coupons of each sort. We will see that: $$G_{m,j} \sim \zeta_* \cdot \ln(m) \quad a.s.$$ where $ \zeta_* $ is a constant appearing in the limit behavior of the smallest box. Some of our arguments are inspired by the works by @Jean and @Joseph, who used the fundamental results of @biggins2 on the asymptotic behaviors of branching random walks to investigate limits of occupancy scheme in the setting of random multiplicative (monotype) cascades. Large deviation behavior of the box sizes ----------------------------------------- In this section we give some results on the asymptotic behavior of the box sizes as the generation $ n $ tends to infinity. We will for simplicity assume that we start from a box of type $ 1 $. Recall that $( p_{ij} $, $ i,j \in \Sigma )$ denotes the transition probabilities of the irreducible, aperiodic Markov chain $ Y $. For each $ \theta \in \mathbb{R} $ we define the $ K\times K $-matrix $ A(\theta):= (p_{ij}^{\theta})_{i,j \in \Sigma} $, with the convention that if $ p_{ij}=0$, then $ p_{ij}^{\theta}=0$, even for $ \theta \leq 0$. The matrix $ A(\theta) $ is connected to the box sizes in the following way: Let $ (l_{i,k}^{(n)})_k $ denote the sequence of the sizes of boxes with type $ i $ at generation $ n $, lexicographically ordered. Let us further introduce the point measure $$Z_j^{(n)}=\sum_k \delta_{-\ln \left(l_{j,k}^{(n)} \right)},$$ and the Laplace transform of $ Z_j^{(n)} $, that is: $$\mathcal{L}_j^{(n)}(\theta) = \sum_k \left(l_{j,k}^{(n)} \right)^{\theta}.$$ A simple iteration argument then shows, that $$\label{matrix} (\mathcal{L}_1^{(n)}(\theta),...,\mathcal{L}_K^{(n)}(\theta)) = (1,0,...,0)(A(\theta))^n.$$ Recall that we call an eigenvalue $ \rho $ of a matrix $ A $ a maximum modulus eigenvalue, if it is a simple root of the characteristic polynomial and its modulus is strictly larger than the modulus of the other roots. Note that since $ Y_n $ is aperiodic and irreducible, $ A(\theta) $ is positive regular (that is its entries are finite and there exists some positive integer $ r $ such that all entries of the matrix $ A(\theta)^r $ are strictly positive.) Recall that we then have from the Perron-Frobenius theorem: 1. $A(\theta) $ possesses a unique maximum modulus eigenvalue $ \rho(\theta) \in \mathbb{R} $, 2. there exists a strictly positive left-eigenvector $ w(\theta)=(w_1(\theta),...,w_K(\theta)) $ and a strictly positive right-eigenvector $ v(\theta)=(v_1(\theta),...,v_K(\theta)) $ with eigenvalue $ \rho(\theta) $, normalized such that we have $ (w(\theta))^tv(\theta)=1 $, 3. $ \min_i \sum_j A(\theta)_{ij} \leq \rho(\theta) \leq \max_i \sum_j A(\theta)_{ij} $. We moreover have that: \[ @biggins3\] The maximum modulus eigenvalue $ \rho(\theta) $ is analytic in $ \theta$. We deduce: \[asymptotics\] For each $ \theta \in \mathbb{R} $ we have: $$\lim_{n \rightarrow \infty} \mathcal{L}_i^{(n)}(\theta)\rho(\theta)^{-n}= v_1(\theta)w_i(\theta) .$$ We shall also need the following: \[ @kingman\] The logarithm of the maximum modulus eigenvalue $ \ln(\rho(\theta)) $ is a convex function of $ \theta $. Note that this also entails the convexity of $ \rho(\theta) $. Now, introduce the constants $$C_*:=\lim_{\theta \rightarrow -\infty } \frac{\rho(\theta)}{-\rho^{\prime}(\theta)} \quad \textnormal{and} \quad C^*:= \lim_{\theta \rightarrow \infty} \frac{\rho(\theta)}{-\rho^{\prime}(\theta)},$$ that will play a crucial role in the asymptotic behavior of the smallest and largest box. We have $ 0< C_* \leq C^* < \infty $. First note that the fact that $ \ln(\rho(\theta)) $ is convex entails that $ \frac{\rho(\theta)}{-\rho^{\prime}(\theta)} $ is an increasing function. Assume first $ \theta >0 $ and let $ p_*:=\inf_{(i,j) \in S} p_{ij} $, where $ S:=\lbrace (i,j) : p_{ij}> 0 \rbrace $. We then have $$0 < p_*^\theta \leq \min_i \sum_{j} p_{ij}^\theta \leq \rho(\theta).$$ Now, let $ r $ be such that the matrix $ A^r $ has only positive entries and define the supremum of its entries $p^*:=\sup_{(i,j)} A^r_{i,j} $. Note that $ p^* < 1 $, that $ A(\theta)^ r $ has only positive entries, and that its maximum modulus eigenvalue is $ \rho(\theta)^r $. Let $ (l_{ij,k}^{(r)})_k $ denote the sequence of the sizes of boxes with type $ j $ at generation $ r $ when the first box was of type $ i $. Then: $$\rho(\theta)^r \leq \max_i \sum_j A(\theta)^r_{ij} = \max_i \sum_j \sum_k \left(l_{ij,k}^{(r)} \right)^{\theta} \leq K \cdot K^r (p^*)^\theta.$$ Similarly if $ \theta < 0 $ we have $ \rho(\theta) \leq K \cdot p_*^\theta $ and $ \rho(\theta)^r \geq (p^*)^\theta $, and thus: $$- \infty < \ln(p_*)\leq \lim_{\theta \rightarrow \pm \infty} \frac{\ln(\rho(\theta))}{\theta} \leq \frac{\ln(p^*)}{r}< 0.$$ We get by l'Hôpitals rule that $-\infty < -\frac{1}{C_*} < 0 $ and $-\infty < -\frac{1}{C^*} < 0 $. Now, let us define the size-biased pick of a box of generation $ n $. That is define a random variable $ L_n $ by $ \mathbb{P}(L_n= l_{i,k}^{(n)}) = l_{i,k}^{(n)} $. (Recall that $\sum_{i=1}^K \sum_k l_{i,k}^{(n)}=1. $) We then have: \[large deviations\] Let $ \theta \in \mathbb{R} $, $ z_n(\theta):= e^{n\frac{\rho^{\prime}(\theta)}{\rho(\theta)}} $ and $ \phi(\theta):= \ln(\rho(\theta))-(\theta-1) \frac{\rho^{\prime}(\theta)}{\rho(\theta)} $, then $ -\infty < \phi(\theta) \leq 0 $ for all $ \theta \in \mathbb{R} $, and: $$\lim_{\varepsilon \downarrow 0} \lim_{n \rightarrow \infty} \frac{1}{n}\ln \left(\mathbb{P} \left( L_n \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right)\right) = \phi(\theta).$$ First note that $\phi(1)=0 $, and $ \phi^\prime(\theta) = (1-\theta) \ln(\rho(\theta))^{\prime\prime} $, thus $ \phi(\theta) $ is decreasing for $ \theta > 1 $ and increasing for $ \theta < 1 $. We then have $ \phi(\theta) \leq 0 $, and the fact that $ -\infty < \phi(\theta) $ follows from the fact that $ \rho $ is analytic. Now, let $ X_n:=\frac{1}{n}\ln(L_n) $. We want to apply the Gärtner-Ellis theorem (see for example @ofer, Theorem 2.3.6), to the random variable $ X_n $. Let $ \lambda \in \mathbb{R} $ and define $ \Lambda_n(\lambda) := \ln \mathbb{E}[e^{\lambda X_n}] $. We first need to check that the limit $$\Lambda(\lambda):= \lim_{n \rightarrow \infty} \frac{1}{n} \Lambda_n(n \lambda)$$ exists as an extended real number. Recall that by Lemma 1 we have $$\frac{K}{2} v(\lambda)(w(\lambda))^t \rho(\lambda)^n \leq \sum_{i=1}^K \mathcal{L}_i^{(n)}(\lambda) \leq 2 K v(\lambda)w^t(\lambda) \rho(\lambda)^n,$$ for sufficiently large $ n $, and thus $$\begin{aligned} \lim_{n \rightarrow \infty} \frac{1}{n} \Lambda_n(n \lambda) &=& \lim_{n \rightarrow \infty} \frac{1}{n} \ln \left(\sum_{i=1}^K \sum_k (l_{i,k}^{(n)})^{(\lambda + 1)} \right) \\&=& \lim_{n \rightarrow \infty} \frac{1}{n} \ln \left(\sum_{i=1}^K \mathcal{L}_i^{(n)}(\lambda + 1) \right) \\&=& \ln(\rho(\lambda + 1)) \\ &=& \Lambda(\lambda) .\end{aligned}$$ We further need to check that $ \Lambda $ is lower semicontinuous and essentially smooth, that is for $$\mathcal{D}_{\Lambda}:= \lbrace \lambda \in \mathbb{R} : \Lambda(\lambda) < \infty \rbrace = \mathbb{R},$$ the interior $ \mathcal{D}^o_\Lambda $ is non empty, $ \Lambda $ is differentiable on $ \mathcal{D}^o_\Lambda $, and $ \lim_{n \rightarrow \infty} \vert \Lambda^\prime(\lambda_n) \vert = \infty $ for every sequence in $ \mathcal{D}^o_\Lambda $ converging to a boundary point of $ \mathcal{D}^o_\Lambda $. The essential smothness and lower semicontinuity then follow readily from the fact that $ \Lambda $ is differentiable on $ \mathbb{R} $. Thus, by the Gärtner-Ellis theorem the large deviation principle holds with good rate function $$\Lambda^*(z)=\sup_{\mu \in \mathbb{R}}( \mu z- \ln(\rho(\mu + 1))).$$ Note that $\Lambda^*(z) \geq 0 $ as $ \rho(1)=1 $. For $ \varepsilon >0 $ let $ B_{\varepsilon}(\theta) := \left(\frac{\rho^{\prime}(\theta)}{\rho(\theta)} -\varepsilon, \frac{\rho^{\prime}(\theta)}{\rho(\theta)} + \varepsilon \right) $ and let $ \overline{B}_{\varepsilon}(\theta) $ denote its closure. By the large deviation principle: $$\liminf_{n \rightarrow \infty} \frac{1}{n} \ln( \mathbb{P}(X_n \in B_{\varepsilon}(\theta))) \geq -\inf_{x \in B_{\varepsilon}(\theta) } \Lambda^*(x)$$ and $$\limsup_{n \rightarrow \infty} \frac{1}{n} \ln( \mathbb{P}(X_n \in B_{\varepsilon}(\theta))) \leq -\inf_{x \in \overline{B}_{\varepsilon}(\theta)} \Lambda^*(x).$$ Now, note that $ -\Lambda^*\left(\frac{\rho^{\prime}(\theta)}{\rho(\theta)} \right) = \phi(\theta) $ and thus: $$\begin{aligned} \phi(\theta) & \leq & \liminf_{\varepsilon \downarrow 0} \liminf_{n \rightarrow \infty} \frac{1}{n} \ln( \mathbb{P}(X_n \in B_{\varepsilon}(\theta))) \\ & \leq & \limsup_{\varepsilon \downarrow 0} \limsup_{n \rightarrow \infty} \frac{1}{n} \ln( \mathbb{P}(X_n \in B_{\varepsilon}(\theta))) \leq \phi( \theta).\end{aligned}$$ This proves our claim. We next provide another approach to the previous lemma. Imagine that we follow the trajectory of a ball through the nested sequence of boxes and recall that the sequence of types of the boxes the ball passes through corresponds to a trajectory of the Markov chain $ Y $. Now, let $ T_n $ denote the type of the box of the $ n$-th generation the ball is passed through and note that $ L_n $ defined in the previous Lemma corresponds to its size. Then $ (T_n) $ is an irreducible Markov chain with transition probabilities $ p_{ij} $ and $ (T_n,T_{n+1}) $ is an irreducible Markov chain with state space $ \lbrace (i,j) \in \Sigma \times \Sigma : p_{ij} \neq 0 \rbrace $ and transition probabilities $ \Pi((i,j),(j,k))=p_{ij} $ and $ \Pi((i,j),(m,k))=0 $ if $ m \neq j $. Further we have that $$L_n= \prod_{k=0}^{n-1} p_{T_k,T_{k+1}}.$$ We prove again Lemma \[large deviations\] now using the large deviation principle for additive functionals of Markov chains. Define the deterministic function $$f: \Sigma \times \Sigma \rightarrow \mathbb{R}, \quad (i,j) \mapsto p_{ij},$$ and the empirical means $$X_n:= \frac{1}{n} \sum_{k=0}^{n-1} f(T_k,T_{k+1}) = \frac{1}{n} \sum_{k=0}^{n-1} \ln(p_{T_k,T_{k+1}})=\frac{1}{n}\ln(L_n).$$ By Theorem 3.1.2 in @ofer, $ X_n $ fulfills the large deviation principle with good rate function $$\Lambda^*(z)=\sup_{\mu \in \mathbb{R}}( \mu z- \ln(\rho(\mu + 1))).$$ The claim then follows in the same spirit as before. Let us define a function that will play a crucial role in our analysis: $$\begin{aligned} \psi(\theta):= \ln(\rho(\theta)) - \frac{\rho^{\prime}(\theta)}{\rho(\theta)}\theta\end{aligned}$$ We then have: \[numerous\] Let $ \theta \in \mathbb{R} $ and define $ z_n(\theta):= e^{n\frac{\rho^{\prime}(\theta)}{\rho(\theta)}} $. We then have: $$\lim_{\epsilon \downarrow 0} \lim_{n \rightarrow \infty} \frac{1}{n} \ln \left( \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right\rbrace} \right)= \psi (\theta).$$ First note that $$\mathbb{P} \left( L_n \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right)= \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right\rbrace} l_{i,k}^{(n)}.$$ Thus $$\begin{aligned} \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right\rbrace} e^{-n\epsilon} & \leq & z_n(\theta)^{-1} \cdot \mathbb{P} \left( L_n \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right) \\ & \leq & \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right\rbrace} e^{n\epsilon}. \end{aligned}$$ By Lemma \[large deviations\] we derive that $$\limsup_{n \rightarrow \infty} \frac{1}{n} \ln \left( \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right\rbrace} \right) \leq \psi(\theta) + \epsilon,$$ and $$\liminf_{n \rightarrow \infty} \frac{1}{n} \ln \left( \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(z_n(\theta) e^{-n\epsilon}, z_n(\theta) e^{n\epsilon} \right) \right\rbrace} \right) \geq \psi(\theta) - \epsilon$$ and we easily conclude. We moreover have that: We have that $ \psi(\theta) > 0 $ for all $ \theta \in \mathbb{R} $. First note that Corollary 1 implies that $ \psi(\theta) \geq 0 $ for all $\theta \in \mathbb{R} $. Further we have that $ \psi(0) > 0$ since $ \rho(0) > 1$. Moreover $ \psi^{\prime}(\theta)=-\theta \cdot \ln(\rho(\theta))^{\prime \prime} $ and thus, by convexity of $ \ln(\rho(\theta)) $, we have that $ \psi $ is increasing on the interval $ (-\infty,0) $ and decreasing on the interval $ (0, \infty) $. Together with the fact that $ \psi $ is analytic and thus cannot be zero on any interval, we arrive at $ \psi(\theta) >0 $ for all $ \theta \in \mathbb{R} $. We can use the previous results to gain information about the asymptotic behavior of the sizes of the smallest box and the largest box. Let $ \underline{l}^{(n)} $ denote the size of the smallest box at generation $ n $. We then have: $$\lim_{n \rightarrow \infty} \frac{\ln (\underline{l}^{(n)})}{n}= -\frac{1}{C_*}$$ Let $ \theta < 0 $ . By Lemma 1 there exists a $ n_0 $, such that for all $ n \geq n_0 $: $$(\underline{l}^{(n)})^{\theta} \leq \mathcal{L}_i^{(n)}(\theta) \leq 2 v_1(\theta)(w_i(\theta))^t \rho(\theta)^n.$$ By some rearrangement we thus get: $$\liminf_{n \rightarrow \infty} \frac{\ln (\underline{l}^{(n)})}{n}\geq \frac{\ln(\rho(\theta))}{\theta},$$ and we conclude by letting $ \theta $ tend to $ -\infty $. Now let $ \varepsilon > 0 $. By Lemma \[large deviations\] there exists a natural number $ n_0(\varepsilon) $ such that $ \underline{l}^{(n)} \leq e^{n\frac{\rho^{\prime}(\theta) } {\rho(\theta)}}e^{\varepsilon n} $ for all $ n \geq n_0(\varepsilon) $, thus $$\limsup_{n \rightarrow \infty} \frac{\ln(\underline{l}^{(n)})}{n}\leq \frac{\rho^{\prime}(\theta) } {\rho(\theta)} + \varepsilon,$$ and the result follows by letting $ \varepsilon $ tend to zero. In the same way one shows for the largest box that: Let $ \overline{l}^{(n)} $ denote the size of the largest box at generation $ n $. We then have: $$\lim_{n \rightarrow \infty} \frac{\ln (\overline{l}^{(n)})}{n}= -\frac{1}{C^*}$$ Height and saturation level of Markovian tries ============================================== Height of Markovian tries {#Upper Bound} ------------------------- Recall that $ H_{m,j}$ for $ j \geq 2 $, denotes the first generation of boxes at which all the boxes contain strictly less than $ j $ balls when $ m $ balls have been thrown independently. We shall show how the large deviation estimates of the preceding section enable us to recover the following result. \[ @S\] For every $ j \geq 2 $ we have $$\lim_{m \rightarrow \infty} \frac{1}{\ln(m)} H_{m,j} = \frac{j}{-\ln(\rho(j))} \qquad a.s.$$ Note that we now continue to successively throw balls forever, and that the randomness is coming from the way we distribute the balls into the boxes. We will first tackle the upper bound. Let $ N^{(n)}_{m,j} $ denote the number of boxes at generation $ n $ containing $ j $ or more balls when $ m $ balls have been thrown. Note that $ H_{m,j} < n $ when $ N^{(n)}_{m,j}=0 $. The idea will be to analyze the asymptotic behavior of $ N_{m,j}^{(n)} $ as $ n $ and $ m $ tend to infinity. We will show that $$H_{m,j} \leq \frac{j}{-\ln(\rho(j))} \ln(m) +\textit{O}\left( \ln \ln(m) \right) \quad a.s.,$$ as $ m $ tends to infinity. Let $ a>\frac{1}{j} $ and define the sequence $$x_n:=\rho(j)^{-\frac{n}{j}}n^{-a}.$$ We then have: \[poissonboxes\] For almost all $ \omega $, there exists a natural number $ n_0(\omega) $ s.t for all $ n \geq n_0(\omega) $, $ N^{(n)}_{ \lfloor x_n \rfloor,j} =0 $. Let $B(m, p)$ denote a generic Binomial variable with parameter $ p \in [0,1] $ and $ m \in \mathbb{N} $ and note that $$\begin{aligned} \label{Binomial} \mathbb{P}(B(m, p) \geq j) \leq \left(\begin{matrix} m \\j \end{matrix} \right) p^j \leq m^j p^j. \end{aligned}$$ Further note that the number of balls in a box of size $ l $ when $ m $ balls have been thrown is $ B(m,l) $ distributed. We thus have $$\begin{aligned} \mathbb{E}[ N^{(n)}_{ \lfloor x_n \rfloor,j} ] &=& \sum_{i=1}^K \sum_k \mathbb{P} \left( B \left(\lfloor x_n \rfloor, l_{i,k}^{(n)} \right) \geq j \right) \\ & \leq & \sum_{i=1}^K \sum_k \left( \lfloor x_n \rfloor l_{i,k}^{(n)} \right)^j \\ & \leq & \sum_{i=1}^K x_n^j \mathcal{L}_i^n(j). \end{aligned}$$ By Lemma \[asymptotics\] there exists a natural number $ n_1 $ such that for all $ n \geq n_1 $ $$\mathcal{L}_i^{(n)}(j)\rho(j)^{-n} \leq 2v_1(j)w_i(j)^t.$$ Taking $ c_1(j):=2v_1(j)w_i(j)^t $ we get that $$\begin{aligned} \mathbb{E}[ N^{(n)}_{ \lfloor x_n \rfloor,j} ] \leq \sum_{i=1}^K c_1(j) x_n^j \rho(j)^n \leq \sum_{i=1}^K c_1(j) n^{-aj},\end{aligned}$$ for all $ n \geq n_1$. We finally arrive at $$\begin{aligned} \mathbb{E} \left[ \sum_{ n \geq n_1} 1_{ \lbrace N^{(n)}_{ \lfloor x_n \rfloor,j} \geq 1 \rbrace} \right] \leq \mathbb{E} \left[\sum_{ n \geq n_1} N^{(n)}_{ \lfloor x_n \rfloor,j} \right] \leq \sum_{ n \geq n_1} c_1(j) n^{-aj} < \infty ,\end{aligned}$$ and we conclude by the Borel-Cantelli lemma. This lemma will be enough to show that: \[upper bound\] For every integer $ j \geq 2 $ we have $$\begin{aligned} \frac{1}{\ln(m)} H_{m,j} \leq \frac{j}{-\ln(\rho(j))} +\textit{O}\left( \frac{\ln \ln(m)}{\ln(m)} \right)\qquad a.s. \end{aligned}$$ as $ m $ tends to infinity. First note that there exists a natural number $ n_1 $ such that $ \forall n \geq n_1 $ we have $ n^{-a} \geq \exp(-n \frac{-\ln(\rho(j))}{2j}) $ and there exists a natural number $ n_2 $ such that for all $ n \geq n_2 $ the sequence $ x_n $ is increasing. Then using Lemma \[poissonboxes\] choose an $ \omega \in \Omega $ for which there exists a natural number $ n_0(\omega) $ such that for all $ n \geq n_0(\omega) $ we have $ N^{(n)}_{ \lfloor x_n \rfloor,j} =0 $. Let $ n_3 \geq \max(n_0(\omega), n_1+1, n_2+1) $ and note that for each $ m \geq x_{n_3} $ there exists an unique $ n \geq n_3 $ such that $ x_{n-1} \leq m < x_n $. From $ m \leq \lfloor x_n \rfloor$ we have $ H_{m,j} \leq n $. Moreover taking logarithm on both sides of the inequality $ x_{n-1} \leq m $, we derive that $$n \leq \frac{j}{- \ln(\rho(j))}\ln(m)+ \frac{j}{- \ln(\rho(j))} a \ln(n-1)+1.$$ Since $ n \geq n_1+1 $, we have that $$m \geq x_{n-1} = \exp \left((n-1) \frac{-\ln(\rho(j))}{j} \right) (n-1)^{-a} \geq \exp \left((n-1) \frac{-\ln(\rho(j))}{2j} \right) .$$ Taking logarithm, we derive that $$(n-1) \leq \frac{2j}{-\ln(\rho(j))}\ln(m)$$ and finally arrive at: $$H_{m,j} \leq n \leq \frac{j}{- \ln(\rho(j))}\ln(m)+ \frac{j}{- \ln ( \rho(j))} a \ln \left( 2\frac{j}{-\ln(\rho(j))}\ln(m) \right)+1,$$ and we easily conclude. One could also have derived Proposition \[upper bound\], by applying Theorem 6.B in @Barbour. We now turn to the proof of the lower bound. Recall that $ H_{m,j} \geq n $, if at generation $ n $ there is at least one box containing $ j $ or more balls. We thus have that $ H_{m,j} > n $ if $ N_{m,j}^{(n)} \geq 1 $. As in the proof of the upper bound we want to analyze the asymptotic behavior of $ N_{m,j}^{(n)} $ as $ n $ and $ m $ tend to infinity. We want to take $ n= \frac{j}{-\ln(\rho(j))} \ln(m) +\textit{o}\left( \ln(m) \right) $. Recall that $ \psi(\theta)= \ln(\rho(\theta)) - \frac{\rho^{\prime}(\theta)}{\rho(\theta)}\theta $ and that $ \psi(\theta)>0 $. Let $ \psi(j) > \varepsilon^{\prime} >0$ and define the sequence: $$x_n:= \rho(j)^{\frac{-n}{j}}e^{n \varepsilon^{\prime}}.$$ In this section we make use of the classical Poissonization trick. Instead of throwing $ x_n $ balls initially we will throw the random number of balls $ \Poisson(x_n) $. The advantage of this procedure is that if we consider two different boxes $ b $ and $ \tilde{b} $ with size $ l $ respectively $ \tilde{l} $, then the number of balls in $ b $ and $ \tilde{b} $ are independent Poisson random variables with parameter $ x_nl $ respectively $ x_n\tilde{l} $. \[tuttituu\] For almost all $ \omega $ there exists a natural number $ n_0(\omega) $, such that there exists at least one box at generation $ n $ containing $ j $ or more balls when $ \Poisson(x_n) $ balls have been thrown. From Corollary \[numerous\], we know that for all $ \varepsilon > 0 $ there exists a natural number $ n_1(\varepsilon) $ such that $$\label{schwubedibummm} \frac{1}{n} \ln \left( \sum_{i=1}^K \sum_k 1_{ \left\lbrace l^{(n)}_{i,k} \in \left(e^{n\frac{\rho^{\prime}(j)}{\rho(j)}} e^{-n\varepsilon}, e^{n\frac{\rho^{\prime}(j)}{\rho(j)}} e^{n\varepsilon} \right) \right\rbrace} \right) \geq \psi(j) - \varepsilon ,$$ for all $ n \geq n_1(\varepsilon) $. Now, let $ \varepsilon < \frac{j}{j+1} \varepsilon^{\prime} $ and let $ M_n $ denote the set containing all the boxes with size larger than $ z_n:= e^{n \left( \frac{\rho^{\prime}(j)}{\rho(j)}-\varepsilon \right)} $ at generation $ n $. From (\[schwubedibummm\]) we deduce that $$\vert M_n \vert \geq v_n(j) := e^{n( \psi(j)- \varepsilon)},$$ for all $ n \geq n_1(\varepsilon) $. For $ n $ large enough we can thus consider the first $ v_n $ boxes in $ M_n $, say $ b_1(n),...,b_{v_n(j)}(n) $ and denote their size with $ l_1(n),...,l_{v_n(j)}(n) $. We then place an imaginary box $ \textbf{b}_i(n) $ in $ b_i(n) $ for $ 1\leq i \leq v_n(j) $, each of size exactly $ z_n $. When a ball falls into the box $ b_i(n) $ it arrives in the imaginary box $ \textbf{b}_i(n) $ with probability $ \frac{z_n}{ l_i} $. We want to show that there exists a natural number $ n_0 $ such that for all $ n \geq n_0 $ at least one of the boxes $\textbf{b}_i(n) $, $ 1\leq i \leq v_n(j) $ contains more than $ j $ balls when Poisson($ x_n $) balls have been thrown. Let $ A_n $ denote the event that all boxes $\textbf{b}_i(n) $, $ 1\leq i \leq v_n(j) $ contain strictly less then $ j $ balls when $ \Poisson(x_n) $ balls have been thrown. Since the number of balls in each box are independent Poisson random variables with parameter $ x_nz_n $, we have: $$\mathbb{P}(A_n) \leq \mathbb{P}(\Poisson(x_nz_n) < j)^{v_n(j)}$$ and thus $$\ln(\mathbb{P}(A_n)) \leq v_n(j) \cdot \ln(\mathbb{P}(\Poisson(x_nz_n) < j)).$$ Note that since $ \psi(j) > 0 $, the sequence $ x_nz_n $ tends to zero as $ n $ tends to infinity and that $ \ln(1+x) \sim x $ for small $ x $. We get that for $ n $ large enough $$\ln(\mathbb{P}(\Poisson(x_nz_n) < j)) \sim -\frac{(x_nz_n)^j}{j!},$$ and thus for large enough $ n $ there exists a constant $ c $ such that: $$\ln(\mathbb{P}(A_n)) \leq -cv_n(j)x_n^jz_n^j= -ce^{n(j \varepsilon^{\prime}-(j+1)\varepsilon)},$$ and we finally arrive at $$\mathbb{P}(A_n) \leq e^{ -ce^{n(j \varepsilon^{\prime}-(j+1)\varepsilon)}}.$$ Applying the Borel-Cantelli lemma, we get the result. This lemma will be enough to show the following proposition: \[propediprop\] For every integer $ j \geq 2 $ we have $$\begin{aligned} \liminf_{m\rightarrow \infty} \frac{1}{\ln(m)} H_{m,j} \geq \frac{j}{-\ln(\rho(j))} \quad a.s. \end{aligned}$$ Define the sequence $ y_n= \rho(j)^{- \frac{n}{j}}e^{n \varepsilon} $ with $ \varepsilon > \varepsilon^{\prime} $ and notice that the sequence $ \frac{y_{n-1}}{x_n} $ tends to infinity. Thus there exists a natural number $ n_1 $ such that, for all $ n \geq n_1 $, $ \frac{y_{n-1}}{x_n}>3 $. We have: $$\begin{aligned} \mathbb{P}(\Poisson(x_n) \geq \lceil y_{n-1} \rceil) &\leq & \mathbb{P}(\Poisson(x_n)\geq 3x_n) \\ &=& \mathbb{P}(\Poisson(x_n)-x_n \geq 2x_n) \\ & \leq & \mathbb{P}(\vert \Poisson(x_n)-x_n \vert \geq 2x_n) \leq\frac{1}{4x_n}\end{aligned}$$ by Chebyshev's inequality. By Borel-Cantelli's lemma we thus derive that for almost all $ \omega $ there exists a natural number $ n_2(\omega) $ such that for all $ n \geq n_2(\omega) $ we have that $ \Poisson(x_n) < \lceil y_{n-1} \rceil $. Now by Lemma \[tuttituu\] we derive that for almost all $ \omega $ there exists a natural number $ n_3(\omega) $ such that for all $ n \geq n_3(\omega) $, we have: $$N_{ \lceil y_{n-1} \rceil, j } \geq 1.$$ Now fix such an $ \omega $. Note that there exists a natural number $ n_4 $ such that $ \forall n \geq n_4 $ the sequence $ y_n $ is increasing. Let $ n_5 \geq \max(n_3(\omega), n_4+1) $ and note that for each $ m \geq y_{n_4} $ there exists a unique $ n \geq n_4 $ such that $ y_{n-1} < m <y_n $. Now, since $ \lceil y_{n-1} \rceil \leq m $, we have $ H_{m , j} >n $. Further since $ m < y_n $, taking logarithm on both sides, we have that: $$\ln(m) < \left(\frac{- \ln(\rho(j))}{j} +\varepsilon \right) n.$$ We thus have that: $$\left(\frac{- \ln(\rho(j))}{j} +\varepsilon \right)^{-1} \ln(m) < n < H_{m,j},$$ and $$\frac{1}{m} H_{m,j} \geq \left(\frac{- \ln(\rho(j))}{j} +\varepsilon \right).$$ We conclude by letting $ \varepsilon $ tend to zero. Power regimes ------------- In this section we study the case when $ j=j(m)=m^{\alpha} $ for $ \alpha \in (0,1) $. In the setting of $ K $-ary tries this corresponds to the case when not only the number of words that have to be stored, but also the storage capacity of the nodes tends to infinity. We aim to show that: We have: $$\begin{aligned} \lim_{m \rightarrow \infty} \frac{1}{\ln(m)} H_{m,j} = (1-\alpha) C^* \qquad a.s. \end{aligned}$$ We first establish the upper bound. Let $ \theta > 0 $, $ a>\frac{1}{\theta(1-\alpha)} $, and define the sequence $$x_n:=\rho(\theta)^{-\frac{1}{1-\alpha}\frac{n}{\theta}}n^{-a}.$$ In the notation of the last section, we then have: \[sdftewerg\] For almost all $ \omega $, there exists a natural number $ n_0(\omega) $ s.t for all $ n \geq n_0(\omega) $ we have $ N^{(n)}_{ \lfloor x_n \rfloor,x_{n-1}^{\alpha}} =0 $. Let $k \in \mathbb{N} $ and let $ j \geq 2(k+1) $. A straight forward computation shows that then: $$\mathbb{P}(B(m,p) \geq j) \leq 2^{k} \cdot \left(\frac{mp}{j}\right)^k.$$ Thus for $ n $ large enough such that $ x_{n-1}^{\alpha} \geq 2 (\lceil \theta \rceil +1) $, we hav8b7c:f320:99b9:690f:4595:cd17:293a:c069 $$\begin{aligned} \mathbb{E}[ N^{(n)}_{ \lfloor x_n \rfloor,x_{n-1}^{\alpha}} ] & \leq & \sum_{i=1}^K \sum_k \mathbb{P} \left( B \left(\lfloor x_n \rfloor, l_{i,k}^{(n)} \right) \geq \lceil \theta \rceil \right) \\ & \leq & 2^{\lceil \theta \rceil} \sum_{i=1}^K \sum_k \left( \frac{\lfloor x_n \rfloor l_{i,k}^{(n)}}{x_{n-1}^{\alpha}} \right)^{\theta}. \end{aligned}$$ Let $ c_1(\theta)= 2^{\lceil \theta \rceil} \cdot 2v_1(\theta)(w_i(\theta))^t $. By Lemma \[asymptotics\] there exists a natural number $ n_1 $ such that for all $ n \geq n_1 $: $$\mathbb{E}[ N^{(n)}_{ \lfloor x_n \rfloor,x_{n-1}^{\alpha}} ] \leq \sum_{i=1}^K c_1(\theta) \left( \frac{x_n}{x_{n-1}^{\alpha}} \right)^{\theta} \rho(\theta)^n \leq \sum_{i=1}^K c_2(\theta) n^{-a \theta (1-\alpha)},$$ where $ c_2(\theta)=c_1(\theta)\rho(\theta)^{-\frac{\alpha}{1-\alpha}} $, and we conclude by Borel-Cantelli's lemma. The upper bound then follows in the same way as Proposition \[upper bound\]. We now turn to the proof of the lower bound. Let $ \varepsilon^{\prime} >0 $ and define the sequence: $$y_n:= \exp\left( n \left( \frac{1}{C^*}\frac{1}{(1-\alpha)} + \varepsilon^{\prime} \right)\right).$$ We then have: \[Lemma6\] For almost all $ \omega \in \Omega $ there exists a natural number $ n_0(\omega) $, s.t. $ N_{\lceil y_{n-1} \rceil ,y_n^{\alpha}} \geq 1 $ for all $ n \geq n_0(\omega) $. Let $ \varepsilon < (1 - \alpha) \varepsilon^{\prime} $. Define $ A_n $, the event that the largest box at generation $ n $ contains strictly less than $ y_n^{\alpha} $ balls when $ \lceil y_{n-1} \rceil $ balls have been thrown and recall that the largest box at generation $ n $ has size larger or equal to $ z_n:= e^{n (-\frac{1}{C^*} - \varepsilon )} $. We then have: $$\begin{aligned} \mathbb{P}(A_n) & \leq & \mathbb{P}((B(\lceil y_{n-1} \rceil, z_n ) > y_n^{\alpha}) \\ & \leq & \mathbb{P}((B(\lceil y_{n-1} \rceil, z_n )+1)^{-1} \leq y_n^{- \alpha}). \end{aligned}$$ A straight forward computation shows that: $$\mathbb{E}[(B(m,p)+1)^{-1}]=\frac{1-(1-p)^{m+1}}{(m+1)p} \leq \frac{1}{mp},$$ and by Markov's inequality we thus get that $$\begin{aligned} \mathbb{P}((B(\lceil y_{n -1} \rceil, z_n )+1)^{-1} \leq y_n^{- \alpha}) &\leq & y_n^{\alpha} \cdot \mathbb{E}[(B(\lceil y_{n -1} \rceil, z_n )+1)^{-1}] \\ &\leq & \frac{y_n^{\alpha}}{\lceil y_{n-1} \rceil \cdot z_n }.\end{aligned}$$ Taking $ c(\alpha):=y_1^{\alpha}$ we arrive at: $$\mathbb{P}(A_n ) \leq c(\alpha) \cdot e^{(n-1) (\varepsilon + (\alpha -1) \varepsilon^{\prime})}.$$ and we conclude by Borel-Cantelli's Lemma. The lower bound follows by the usual computations. Saturation level of Markovian tries ----------------------------------- Let $ j\geq 1 $ and recall that $ G_{m,j} $ denotes the first generation at which there exists a box containing strictly less than $ j $ balls, when $ m $ balls have been thrown initially. We aim to show that: Let $ j\geq 1 $, and recall that $ C_*=\lim_{\substack{\theta \rightarrow -\infty }} \frac{\rho(\theta)}{-\rho^{\prime}(\theta)} $. We then have $$\lim_{m \rightarrow \infty} \frac{1}{\ln(m)} G_{m,j} = C_* \qquad a.s.$$ We will first study the asymptotic behavior of $ G_{m,1} $ and then extend this to the asymptotic behavior of $ G_{m,j} $. We will shorthand write $ G_m $ for $ G_{m,1} $. In order to establish an upper and a lower bound for $ G_m $ it will be useful to study the asymptotic behavior of the number of balls $ T_n $, one needs to throw initially to observe at least one ball in each box of generation $ n $. As already mentioned in the introduction, this can be interpreted in terms of the coupon collector's problem. We will see each box of generation $ n $ as a different sort of coupon, $ T_n $ then corresponds to the number of coupons one has to buy to get at least one of each coupon and the probability to buy a sort of coupon is given by the size of the corresponding box. It will sometimes be convenient to use a Poissonization technique to model $ T_n $. Suppose that the collector continues to buy coupons forever (rather than stopping when having a full collection). Moreover suppose that the coupons are bought at times distributed as the arrival times of a Poisson process with rate $ 1 $. The times a coupon of sort $ i $ is bought are then the arrival times of independent Poisson processes with rate $ p_i $. Let $ \textbf{T}_n $ denote the waiting time until the collector has completed his collection. We then have $$\textbf{T}_n= \max_{k \leq K^n} \textbf{exp}(l_k^{(n)}),$$ where $\textbf{exp}(l_k^{(n)})$ denote independent exponential random variables with parameter $ l_k^{(n)} $, that is to say $ \mathbb{E}[\textbf{exp}(l_k^{(n)})]=\frac{1}{l_k^{(n)}} $. The connection between $ \textbf{T}_n $ and $ T_n $ is then given by $$\textbf{T}_n= \sum_{k=1}^{T_n} \textbf{exp}_k(1),$$ where $\textbf{exp}_k(1) $ are i.i.d. exponential random variables with parameter $ 1 $, independent of $ T_n $. In the same spirit, let $ T_n^j $ denote the number of balls one needs to throw initially to observe at least $ j $ ball in each box of generation $ n $. Let $ \textbf{T}_n^j $ denote the waiting time until the collector has completed $ j $ copies of his collection. We then have $$\textbf{T}^j_n= \max_{k \leq K^n} \Gamma(j,l_k^{(n)}),$$ where $\Gamma(j,l_k^{(n)})$ denote independent Gamma random variables with parameter $ l_k^{(n)} $ and $ j $. As in the case $ j=1 $ we then have $$\textbf{T}_n^j= \sum_{k=1}^{T_n^j} \textbf{exp}_k(1),$$ where $\textbf{exp}_k(1) $ are i.i.d. exponential random variables with parameter $ 1 $, independent of $ T_n^j $. For the lower bound, we want to find an upper bound for the waiting time $ \textbf{T}_n $ until the collector has completed his collection. \[markov\] Let $ \theta < 0 $ and define $ x_n:=e^{n\frac{\ln((\rho(\theta))}{-\theta}}n^{\mu} $ , $ \mu >2 $. For almost all $ \omega $ there exists a natural number $ n_0(\omega) $, such that for all $ n \geq n_0(\omega) $ : $$\textbf{T}_n(\omega) < x_n.$$ We use the Poissonization technique explained in the previous section. We have: $$\mathbb{P}(\textbf{T}_n \geq x_n) = \mathbb{P}(\max_{k \leq K^n} \textbf{exp}(l_k^{(n)}) \geq x_n) \leq \mathbb{P}( \max_{k \leq K^n} \textbf{exp}_k(1) \geq \underline{l}^{(n)}x_n),$$ where $ \textbf{exp}_k(1) $ are i.i.d exponential r.v. with parameter $ 1 $. Now, for $ \theta < 0 $ we have: $$\left( \underline{l}^{(n)} \right)^{\theta} \leq \sum_k \left(l_{j,k}^{(n)} \right)^{\theta} = \mathcal{L}^{(n)}_j(\theta).$$ By Lemma 1 there exists a $ n_0 $, such that for all $ n \geq n_0 $: $$(\underline{l}^{(n)})^{\theta} \leq \mathcal{L}_j^{(n)}(\theta) \leq 2 v_1(\theta)(w_i(\theta))^t \rho(\theta)^n.$$ Let $ c_1(\theta):=\frac{1}{\theta}2\ln(v_1(\theta)(w_i(\theta))^t $, by taking logarithm on both sides and some rearrangement, we get that there exists a natural number $ n_1 $ such that for all $ n \geq n_1 $: $$\frac{n \ln(\rho(\theta))}{\theta} + c_1(\theta) \leq \ln (\underline{l}^{(n)}),$$ and thus $$e^{n\frac{\ln(\rho(\theta))}{\theta} + c_1(\theta)} \leq \underline{l}^{(n)},$$ for all $ n \geq n_1 $. Let $ c_2(\theta) = e^{c_1(\theta)} $, we deduce that for $ n $ large enough: $$\mathbb{P}(\textbf{T}_n \geq x_n) \leq \mathbb{P}( \max_{k \leq K^n} \textbf{exp}_k(1) \geq c_2(\theta)n^{\mu}).$$ Now, recall that $$\max_{k \leq K^n} \textbf{exp}_k(1) - n\ln(K)$$ converges in distribution to the standard Gumbel distribution $ \textbf{G}(1) $ as $ n $ tends to infinity. Thus for large enough $ n $, we have: $$\begin{aligned} \mathbb{P}(\textbf{T}_n \geq x_n) & \leq & 2 \cdot \mathbb{P}\left(\textbf{G}(1) \geq c_2(\theta)n^{\mu}-n\ln(K)\right) \\ &=& 2 \cdot \left( 1-\exp\left(-e^{-(c_2(\theta)n^{\mu}-n\ln(K))}\right) \right) \\ & \leq & 2 \cdot e^{-(c_2(\theta)n^{\mu}-n\ln(K))}.\end{aligned}$$ We then conclude by Borel-Cantelli's lemma. Since the times at which a ball is thrown are the arrival times of independent Poisson processes with rate $ 1 $, the number of balls thrown up to time $ x_n $ is Poisson distributed with parameter $ x_n $. Applying Lemma \[markov\], we thus get, that: \[zero boxes\] For almost all $ \omega $ it exists an integer number $ n_0(\omega) $ such that $ \forall n \geq n_0(\omega)$ there exists no box at generation $ n $ containing no balls when $ \Poisson(x_n) $ balls have been thrown. We then arrive at: \[Upper Bound saturation\] We have: $$\frac{1}{\ln(m)} G_{m,j} \geq C_*+ \textit{O}\left(\frac{\ln\ln(m)}{\ln(m)}\right) \quad a.s.$$ as $ m $ tends to infinity. Note that $T_n^j \leq T_n^{(1)}+...+T_n^{(j)}$ a.s., where $T_n^{(1)},...,T_n^{(j)} $ denote independent copies of $ T_n $. Further we have $ G_{\lfloor \frac{m}{j} \rfloor } \geq n$ a.s. which implies that $ \lfloor \frac{m}{j} \rfloor > T_n $ a.s. and thus $ T_n^j \leq m $ a.s. But then $ G_{m,j} \geq n $ a.s. and we conclude that $ G_{m,j} \geq G_{\lfloor \frac{m}{j} \rfloor} $ a.s. It will be thus enough to show the statement for $ G_m $. \[of Proposition \[Upper Bound saturation\]\] Define the sequence $ y_n= e^{n\frac{\ln((\rho(\theta))}{-\theta}}n^{\mu^{\prime}} $ with $ \mu^{\prime} < \mu$ and note that the sequence $ \frac{y_{n}}{x_n} $ tends to zero. Thus there exists a natural number $ n_0$ such that for all $ n \geq n_0 $, we have $ \frac{y_{n}}{x_n}< \frac{1}{2} $. Thus:$$\begin{aligned} \mathbb{P}(\Poisson(x_n) \leq \lfloor y_{n} \rfloor) &\leq & \mathbb{P}(\Poisson(x_n)\leq \frac{x_n}{2}) \\ &= & \mathbb{P}(\Poisson(x_n)-x_n \leq - \frac{x_n}{2}) \\ & \leq & \mathbb{P}(\vert \Poisson(x_n)-x_n \vert \geq \frac{x_n}{2}) \leq\frac{4}{x_n}\end{aligned}$$ by Chebyshev's inequality. By Borel-Cantelli's lemma we thus derive that for almost all $ \omega $ there exists a natural number $ n_1(\omega) $ such that for all $ n \geq n_1(\omega) $ we have that $ \Poisson(x_n) > \lceil y_{n-1} \rceil $. Now, let $ M_{m}^{(n)} $ denote the number of boxes at generation $ n $ containing zero balls when $ m $ balls have been thrown. By Corollary \[zero boxes\] we deduce that for almost all $ \omega $ there exists a natural number $ n_2(\omega) $, such that for all $ n \geq n_2(\omega) $, we have $M_{y_{n-1}}^{(n)} = 0 $. Fix such an $ \omega $ and note that since the sequence $ (y_n) $ is increasing, for each $ m \geq y_{n_2(\omega)} $ there exists a unique $ n \geq n_2(\omega) $ such that $ y_{n-1} < m \leq x_{n} $. Since $ \lceil y_{n-1} \rceil \leq m $ we have $ G_m > n-1 $. Now, by taking logarithm on both sides of the inequality $ m \leq x_{n} $ and some rearrangement, we get that: $$n \geq \frac{-\theta}{\ln(\rho(\theta))}\ln(m)-\mu\ln(n).$$ From the inequality $ m > x_{n-1} \geq e^{(n-1)\frac{\ln(\rho(\theta))}{-\theta} }$, we get that $ \frac{\theta}{\ln(\rho(\theta))}\ln(m) \geq n $ and thus: $$\begin{aligned} \label{Boiler} G_m > n -1 \geq \frac{-\theta }{\ln(\rho(\theta))}\ln(m)-\mu\ln\left(\frac{-\theta }{\ln(\rho(\theta))}\ln(m)\right)-1, \end{aligned}$$ and we are left to show that: $$\lim_{\substack{\theta \rightarrow -\infty }} \frac{ -\theta}{\ln(\rho(\theta))} = C_*.$$ Indeed by l'Hôpital's rule, we have that: $$\lim_{\substack{\theta \rightarrow -\infty }}\frac{ -\theta}{\ln(\rho(\theta))}= \lim_{\substack{\theta \rightarrow -\infty }} \frac{\rho(\theta)}{-\rho^{\prime}(\theta)} =C_*,$$ and we conclude. We could have gained the same result by applying Theorem 6.E in @Barbour. For the proof of the upper bound, we want to find an lower bound for the number of balls $ T_n $ one needs to throw initially to observe at least one ball in each box of generation $ n $. \[markov2\] Let $ \theta < 1 $ and define $ x_n:=e^{n\left(\frac{-\rho^{\prime}(\theta)}{\rho(\theta)}-\varepsilon^{\prime}\right)} $ , $ \varepsilon^{\prime} > 0 $. For almost all $ \omega $ there exists a natural number $ n_0(\omega) $, such that for all $ n \geq n_0(\omega) $ : $$\textbf{T}_n(\omega) > x_n.$$ We use the Poissonization technique explained in the last section. We have: $$\mathbb{P}(\textbf{T}_n \leq x_n) = \mathbb{P}(\max_{k \leq K^n} \textbf{exp}(l_k^{(n)}) \leq x_n) \leq \mathbb{P}(\textbf{exp}(1)\leq \underline{l}^{(n)}x_n).$$ Now, by Lemma \[large deviations\] there exists for each $ \varepsilon > 0 $ a natural number $ n_0(\varepsilon) $ such that $ \underline{l}^{(n)} \leq e^{n \left( \frac{\rho^{\prime}(\theta) } {\rho(\theta)} + \varepsilon \right)} $ for all $ n \geq n_0(\varepsilon) $. Let $ \varepsilon < \varepsilon^{\prime} $. We then have for each $ n \geq n_0(\varepsilon) $: $$\mathbb{P}(\textbf{T}_n \leq x_n) \leq \mathbb{P}(\textbf{exp}(1)\leq 2e^{-n\varepsilon})=1-\exp(-e^{-n(\varepsilon^{\prime}-\varepsilon)} ) \leq e^{-n(\varepsilon^{\prime} - \varepsilon)} .$$ We conclude by Borel-Cantelli's lemma. Since the times at which a ball is thrown are the arrival times of independent Poisson processes with rate $ 1 $, the number of balls thrown up to time $ x_n $ is Poisson distributed with parameter $ x_n $. Applying Lemma \[markov2\], we thus get that: \[zero boxes2\] For almost all $ \omega $ it exists a natural number $ n_0(\omega) $ such that $ \forall n \geq n_0(\omega)$ there is at least one box at generation $ n $ containing zero balls when $ \Poisson(x_n) $ balls have been thrown. We now tackle the proof of the main result in this section. \[Lower Bound saturation\] We have: $$\limsup_{m \rightarrow \infty} \frac{1}{\ln(m)} G_m \leq C_* \quad a.s.$$ Define the sequence $ y_n= e^{n \left(\frac{-\rho^{\prime}(\theta)}{\rho(\theta)}-\varepsilon \right)} $ with $ \varepsilon^{\prime} > \varepsilon $ and notice that the sequence $ \frac{y_{n}}{x_n} $ tends to infinity. Thus there exists a natural number $ n_1 $ such that for all $ n \geq n_1 $ $ \frac{y_{n}}{x_n}> 3 $. We have: $$\begin{aligned} \mathbb{P}(\Poisson(x_n) \geq \lfloor y_{n} \rfloor) &\leq & \mathbb{P}(\Poisson(x_n) \geq 3x_n) \\ &= & \mathbb{P}(\Poisson(x_n)-x_n \geq 2x_n) \\ & \leq & \mathbb{P}(\vert \Poisson(x_n)-x_n \vert \geq 2x_n) \leq \frac{1}{4x_n},\end{aligned}$$ by Chebyshev's inequality. By Borel-Cantelli we thus derive that for almost all $ \omega $ there exists a natural number $ n_2(\omega) $ such that for all $ n \geq n_2(\omega) $ we have that $ \Poisson(x_n) < \lfloor y_{n} \rfloor$. Now by Corollary \[zero boxes2\] we derive that for almost all $ \omega $ there exists a natural number $ n_3(\omega) $ such that for all $ n \geq n_3(\omega) $, we have: $$M_{ \lfloor y_{n} \rfloor, j } =0.$$ Now fix such an $ \omega $. Note that there exists a natural number $ n_4 $ such that $ \forall n \geq n_4 $ the sequence $ y_n $ is increasing. Let $ n_5 \geq \max(n_3(\omega), n_4) $ and note that for each $ m \geq y_{n_4} $ there exists a unique $ n \geq n_4 $ such that $ y_{n} < m <y_{n+1} $. Now, since $ \lfloor y_{n-1} \rfloor \leq m $, we have $G_m < n $. Further since $ y_n <m $, taking logarithm on both sides, we have that: $$\frac{1}{(\frac{-\rho^{\prime}(\theta)}{\rho(\theta)} - \varepsilon^{\prime} )}\ln(m) \geq n > G_m.$$ We thus derive that $$\limsup_{m \rightarrow \infty} \frac{1}{\ln(m)} G_m \leq \frac{1}{\frac{-\rho^{\prime}(\theta)}{\rho(\theta)} -\varepsilon},$$ and we conclude by letting $ \varepsilon $ tend to zero and $ \theta $ tend to $ -\infty $. Now, let $ j \geq 2 $ and note that the first generation when there exists a box containing no ball when $ m $ balls have been thrown is larger then the first generation at which there exists a box containing less than $ j $ balls when $ m $ balls have been thrown. That is $ G_{m,j} \leq G_m $ and we derive that: Let $ j \geq 1 $. We have: $$\liminf_{m \rightarrow \infty} \frac{1}{\ln(m)} G_{m,j} \leq C_* \quad a.s.$$ Occupancy scheme in random environment ====================================== Random probability cascades --------------------------- Consider a random transition matrix $ A=(p_{ij}) $. To the box with label $ u $, of type $ i $, we will associate an independent copy of $A_u=(p_{ij}(u)) $ of $A $. The length of the box $ u = (i_1,...,i_{n}) $ is then given by some multiplicative cascade, that is: $$\label{multiplicative cascade} l^{(n)}_u= p_{i_1i_2}(i_1) \times ... \times p_{i_{n-1}i_{n}}((i_1,i_2,...i_{n-1})).$$ Let $ \left(l^{(n)}_{ij,k}\right)_k $ denote the sequence of length of the boxes of type $ j $ at generation $ n $, when the first box was of type $ i $. The process $ (Z_i^{n})_n=(Z_{i1}^n,...,Z_{iK}^n) $, with $$Z_{ij}^n= \sum_k \delta_{-\ln(l_{ij,k}^{(n)})},$$ is then a multitype branching random walk. Let $ \vert Z_{ij} \vert := \int_{\mathbb{R}} Z_{ij}(dx)
{'source': 'arXiv_out/1609'}