View source for Random allocation

<!--
r0772501.png
$#A+1 = 76 n = 0
$#C+1 = 76 : ~/encyclopedia/old_files/data/R077/R.0707250 Random allocation
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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|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|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 [[#References|[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 [[#References|[1]]], [[#References|[3]]]). Using these theorems, it is possible to calculate the power of the [[Empty-boxes test|empty-boxes test]] (cf. also [[Power of a statistical test|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 [[#References|[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 [[#References|[1]]]) connected with a whole series of combinatorial problems of probability theory (random permutations, random mappings, trees, etc.).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  B.A. Sevast'yanov,   "The empty boxes criterion and its generalizations"  ''Trudy. Inst. Prikl. Mat. Tbilis. Univ.'' , '''2'''  (1969)  pp. 229–233  (In Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  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</TD></TR></table>

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

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N.L. Johnson,   S. Kotz,   "Urn models and their application" , Wiley  (1977)</TD></TR></table>