Two-Stage Allocations and the Double $Q$-Function

Sergey Agievich

Abstract


Let $m+n$ particles be thrown randomly, independently of each other into $N$ cells, using the following two-stage procedure.

1. The first $m$ particles are allocated equiprobably, that is, the probability of a particle falling into any particular cell is $1/N$. Let the $i$th cell contain $m_i$ particles on completion. Then associate with this cell the probability $a_i=m_i/m$ and withdraw the particles.
2. The other $n$ particles are then allocated polynomially, that is, the probability of a particle falling into the $i$th cell is $a_i$.

Let $\nu=\nu(m,N)$ be the number of the first particle that falls into a non-empty cell during the second stage. We give exact and asymptotic expressions for the expectation ${\bf E}\nu$.


Full Text: PDF