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)