The Bernoulli sieve revisited (Q835075)

Consider \(n\) balls to be put into \(n\) of infinitely many boxes indexed \(1,2,\dots\)\ . Let \(\xi_1,\xi_2,\dots\) be i.i.d. random variables with values in \((0,1)\). At the first step, given the \(\xi_i\), the balls are put into box 1, independently, with probability \(\xi_1\). At the second step the remaining balls are placed into box 2 with probability \(\xi_2\), etc. until every ball is in some box. The probability that a particular ball lands in box \(j\) is \((1-\xi_1)\cdots(1- \xi_{j-1})\xi_j\). This recursive allocation is called the Bernoulli sieve. It may be constructed as follows. Let \(S_0= 0,S_1,S_2,\dots\) be a random walk with steps distributed as \(-\log(1-\xi_1)\) and \(E_1,\dots, E_n\) a random sample from the standard exponential distribution. Take the event \(S_{k-1}< E_j< S_k\) as ball \(j\) landing in box \(k\). Put \(K_n=\) number of occupied boxes, \(K^*_n=\) largest index of occupied boxes, \(K(n,0)=\) number of empty boxes with index \(\leq K^*_n\), \(W_n=\) index of first empty box, \(Z_n=\) number of balls in last occupied box. Also \(\mu= E(-\log(1- \xi_1)\), \(v= E(-\log\xi_1)\), \(\sigma^2= \text{Var}\{-\log(1- \xi_1)\}\), \(N_t= \text{inf}\{k> 0: S_k\geq t\}\). The paper proves limit theorems for \(n\to\infty\): Theorem 2.1: \((K^*_n- b_n)/a_n\) converges in distribution iff \(-\log(1-\xi_1)\) is attracted to a stable law or \(P(-\log(1 -\xi_1)> x)\) varies slowly as \(x\to\infty\). When \(\sigma^2<\infty\) the limit distribution is standard normal for \(b_n= \mu^{-1}\log n\) and \(a_n= (\mu^{-3}\sigma^2\log n)^{1/2}\). When \(\sigma^2= \infty\) several cases of regular variation of \(P(1-\xi_1\leq x)\) as \(x\to 0\) give limit theorems. The theorem is derived from renewal theory by proving that \((K^*_n- b_n)/a_n\to X\) iff \((N(\log n)- b_n)/a_n\to X\). A delicate result is Theorem 2.2. When \(\nu<\infty\) then \(K(n,0)@>d>> U\), a finite random variable with \(EU= \nu/\mu\). When \(E\xi^{-\delta}_1<\infty\) and \(E(1-\xi_1)^{-\delta}<\infty\) for some \(\delta> 0\) we have \(EK(n,0)\to EU\). The proof first puts \(E_1,E_2,\dots\) at the points of a standard Poisson process \(\pi\) and considers \(K(\pi(t) ,0)\). Theorem 2.3: When \(\nu<\infty\) the assertions for \(K^*_n\) in Theorem 2.1 hold for \(K_n\), \(W_n\) and the number of boxes with at least two balls. Finally there is \(Z_n\). When \(\mu<\infty\) we have \(Z_n@>d>> Z\) with \(P(Z= k)= E\xi^k_1/\mu k\). When \(\mu= \infty\) there is convergence for scaled \(Z_n\) under regular variation conditions.