Random allocation

A probability scheme in which $n$ particles are randomly distributed over $N$ cells. In the simplest scheme, the particles are distributed equi-probably and independently of one another, so that each can fall into any fixed cell with a probability of $1 / N$. Let $\mu _ {r} = \mu _ {r} ( n , N )$ be the number of cells in which, after distribution, there are exactly $r$ particles, and let $0 \leq r _ {1} < \dots < r _ {s}$.

The generating function

$$\Phi ( z ; x _ {1} \dots x _ {s} ) = \ \sum _ { n= } 0 ^ \infty \sum _ {k _ {1} \dots k _ {s} = 0 } ^ \infty \frac{N ^ {n} z ^ {n} }{n!} \times$$

$$\times {\mathsf P} \{ \mu _ {r _ {1} } = k _ {1} \dots \mu _ {r _ {s} } = k _ {s} \} x _ {1} ^ {k _ {1} } \dots x _ {s} ^ {k _ {s} }$$

has the following form:

$$\tag{1 } \Phi ( z ; x _ {1} \dots x _ {s} ) =$$

$$= \ \left [ e ^ {z} + \frac{z ^ {r _ {1} } }{r _ {1} ! } ( x _ {1} - 1 ) + \dots + \frac{z ^ {r _ {s} } }{ r _ {s} ! } ( x _ {s} - 1 ) \right ] ^ {N} .$$

The generating function (1) allows one to compute the moments of the $\mu _ {r}$ and to study the asymptotic properties of their distribution as $n , N \rightarrow \infty$. These asymptotic properties are to a large extent determined by the behaviour of the parameter $\alpha = n / N$— the average number of particles in a cell. If $n , N \rightarrow \infty$ and $\alpha = o ( N)$, then for fixed $r$ and $t$,

$$\tag{2 } {\mathsf E} \mu _ {r} \sim N {p _ {r} } ( \alpha ) ,\ \ \mathop{\rm Cov} ( \mu _ {r} ,\ \mu _ {t} ) \sim N \sigma _ {rt} ( \alpha ) ,$$

where $p _ {r} ( \alpha ) = \alpha ^ {r} e ^ {- \alpha } / r !$,

$$\sigma _ {rt} ( \alpha ) = p _ {r} ( \alpha ) \left [ \delta _ {rt} - p _ {t} ( \alpha ) - p _ {t} ( \alpha ) \frac{( \alpha - r ) ( \alpha - t ) } \alpha \right ] ,$$

and $\delta _ {rt}$ is the Kronecker delta. One can identify five domains with different types of asymptotic behaviour of $\mu _ {r}$ as $N , n \rightarrow \infty$.

The central domain corresponds to $\alpha = n / N \ord 1$. The domain for which

$$\alpha \rightarrow \infty ,\ \ {\mathsf E} \mu _ {r} \rightarrow \lambda ,\ \ 0 < \lambda < \infty$$

is called the right $r$- domain, and the right intermediate $r$- domain is that for which

$$\alpha \rightarrow \infty ,\ \ {\mathsf E} \mu _ {r} \rightarrow \infty .$$

For $r \geq 2$, the left $r$- domain corresponds to the case where

$$\alpha \rightarrow 0 ,\ \ {\mathsf E} \mu _ {r} \rightarrow \lambda ,\ \ 0 < \lambda < \infty .$$

The left intermediate $r$- domain is that for which

$$\alpha \rightarrow 0 ,\ \ {\mathsf E} \mu _ {r} \rightarrow \infty .$$

The left and right intermediate $r$- domains for $r = 0 , 1$ are identified with the corresponding $2$- domains.

In the case of an equi-probable scheme, $\mu _ {r}$ has asymptotically a Poisson distribution in the right $r$- domains. The same is true in the left $r$- domains when $r \geq 2$, and when $r = 0$ or $r = 1$, $\mu _ {0} - N + n$ and $( n - \mu _ {1} ) / 2$ have Poisson distributions in the limit. In the left and right intermediate $r$- domains the $\mu _ {r}$ have asymptotically a normal distribution. In the central domain there is a multi-dimensional asymptotic normality theorem for $\mu _ {r _ {1} } \dots \mu _ {r _ {s} }$; the parameters of the limiting normal distribution are defined by the asymptotic formulas (2) (see [1]).

An allocation in which $n$ particles are distributed over $N$ cells independently of each other in such a way that the probability of each of the particles falling into the $j$- th cell is equal to $a _ {j}$, $\sum _ {j=} 1 ^ {N} a _ {j} = 1$, is called polynomial. For a polynomial allocation one can also introduce central, right and left domains, and limiting normal and Poisson theorems hold (see [1], [3]). Using these theorems, it is possible to calculate the power of the empty-boxes test (cf. also Power of a statistical test). Let $\xi _ {1} \dots \xi _ {n}$ be independent random variables each having a continuous distribution function $F ( x)$( hypothesis $H _ {0}$). The alternative hypothesis $H _ {1}$ corresponds to another distribution function $F _ {1} ( x)$. The points $z _ {0} = - \infty < z _ {1} < \dots < z _ {N-} 1 < z _ {N} = \infty$ are chosen in such a way that $F ( z _ {k} ) - F ( z _ {k-} 1 ) = 1 / N$, $k = 1 \dots N$. The empty-boxes test is based on the statistic $\mu _ {0}$, equal to the number of intervals $( z _ {k-} 1 , z _ {k} ]$ containing none of the $\xi _ {i}$. The empty-boxes test is determined by the critical region $\mu _ {0} > C$, where $H _ {0}$ is rejected. Since under $H _ {0}$, $\mu _ {0}$ has a probability distribution defined by a uniform allocation, whereas under $H _ {1}$ it has a distribution defined by a polynomial allocation, it is possible to use limit theorems for $\mu _ {0}$ to calculate the power ${\mathsf P} \{ \mu _ {0} > C \mid H _ {1} \}$ of this test (see [2]).

In another scheme the particles are grouped in blocks of size $m$ and it is assumed that they are put in the $N$ cells in such a way that no two particles from one block fall into the same cell, the positions of the different blocks being independent. If all $( {} _ {m} ^ {N} )$ positions of each block are equi-probable and the number of blocks $n \rightarrow \infty$, then for bounded or weakly increasing $m$, the $\mu _ {r}$ again have asymptotically a normal or Poisson distribution.

There are various possible generalizations of allocation schemes (see [1]) connected with a whole series of combinatorial problems of probability theory (random permutations, random mappings, trees, etc.).

References

[1]	V.F. [V.F. Kolchin] Kolčin, B.A. [B.A. Sevast'yanov] Sevast'janov, V.P. [V.P. Chistyakov] Čistyakov, "Random allocations" , Winston (1978) (Translated from Russian)
[2]	B.A. Sevast'yanov, "The empty boxes criterion and its generalizations" Trudy. Inst. Prikl. Mat. Tbilis. Univ. , 2 (1969) pp. 229–233 (In Russian)
[3]	V.G. Mikhailov, "The central limit theorem for a scheme for independent allocation of particles in cells" Proc. Steklov Inst. Math. , 157 (1981) pp. 147–164 Trudy Mat. Inst. Steklov. , 157 (1981) pp. 138–152

Comments

The problems involved are often referred to as occupancy problems; they are equivalent to urn problems (see [a1] and Urn model).

References

[a1]	N.L. Johnson, S. Kotz, "Urn models and their application" , Wiley (1977)