Namespaces
Variants
Actions

Difference between revisions of "Random allocation"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (fixing subscripts)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A probability scheme in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772501.png" /> particles are randomly distributed over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772502.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772503.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772504.png" /> be the number of cells in which, after distribution, there are exactly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772505.png" /> particles, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772506.png" />.
+
<!--
 +
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
 
The generating function
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772507.png" /></td> </tr></table>
+
$$
 +
\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
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772508.png" /></td> </tr></table>
+
$$
 +
\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:
 
has the following form:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r0772509.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \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} .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725010.png" /></td> </tr></table>
+
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 $,
  
The generating function (1) allows one to compute the moments of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725011.png" /> and to study the asymptotic properties of their distribution as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725012.png" />. These asymptotic properties are to a large extent determined by the behaviour of the parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725013.png" /> — the average number of particles in a cell. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725015.png" />, then for fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725017.png" />,
+
$$ \tag{2 }
 +
{\mathsf E} \mu _ {r}  \sim  N {p _ {r} } ( \alpha ) ,\ \
 +
\mathop{\rm Cov} ( \mu _ {r} ,\
 +
\mu _ {t} )  \sim  N \sigma _ {rt} ( \alpha ) ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
where  $  p _ {r} ( \alpha ) = \alpha  ^ {r} e ^ {- \alpha } / r ! $,
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725019.png" />,
+
$$
 +
\sigma _ {rt} ( \alpha )  = p _ {r} ( \alpha )
 +
\left [ \delta _ {rt} - p _ {t} ( \alpha )
 +
- p _ {t} ( \alpha )
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725020.png" /></td> </tr></table>
+
\frac{( \alpha - r ) ( \alpha - t ) } \alpha
 +
\right ] ,
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725021.png" /> is the Kronecker delta. One can identify five domains with different types of asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725022.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725023.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725024.png" />. The domain for which
+
The central domain corresponds to $  \alpha = n / N \ord 1 $.  
 +
The domain for which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725025.png" /></td> </tr></table>
+
$$
 +
\alpha  \rightarrow  \infty ,\ \
 +
{\mathsf E} \mu _ {r}  \rightarrow  \lambda ,\ \
 +
0 < \lambda  < \infty
 +
$$
  
is called the right <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725027.png" />-domain, and the right intermediate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725029.png" />-domain is that for which
+
is called the right r $-
 +
domain, and the right intermediate r $-
 +
domain is that for which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725030.png" /></td> </tr></table>
+
$$
 +
\alpha  \rightarrow  \infty ,\ \
 +
{\mathsf E} \mu _ {r}  \rightarrow  \infty .
 +
$$
  
For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725031.png" />, the left <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725033.png" />-domain corresponds to the case where
+
For r \geq  2 $,  
 +
the left r $-domain corresponds to the case where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725034.png" /></td> </tr></table>
+
$$
 +
\alpha  \rightarrow  0 ,\ \
 +
{\mathsf E} \mu _ {r}  \rightarrow  \lambda ,\ \
 +
< \lambda  < \infty .
 +
$$
  
The left intermediate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725036.png" />-domain is that for which
+
The left intermediate r $-domain is that for which
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725037.png" /></td> </tr></table>
+
$$
 +
\alpha  \rightarrow  0 ,\ \
 +
{\mathsf E} \mu _ {r}  \rightarrow  \infty .
 +
$$
  
The left and right intermediate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725038.png" />-domains for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725039.png" /> are identified with the corresponding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725040.png" />-domains.
+
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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725041.png" /> has asymptotically a [[Poisson distribution|Poisson distribution]] in the right <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725042.png" />-domains. The same is true in the left <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725043.png" />-domains when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725044.png" />, and when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725045.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725046.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725048.png" /> have Poisson distributions in the limit. In the left and right intermediate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725049.png" />-domains the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725050.png" /> have asymptotically a [[Normal distribution|normal distribution]]. In the central domain there is a multi-dimensional asymptotic normality theorem for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725051.png" />; the parameters of the limiting normal distribution are defined by the asymptotic formulas (2) (see [[#References|[1]]]).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725052.png" /> particles are distributed over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725053.png" /> cells independently of each other in such a way that the probability of each of the particles falling into the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725054.png" />-th cell is equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725056.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725057.png" /> be independent random variables each having a continuous distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725058.png" /> (hypothesis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725059.png" />). The alternative hypothesis <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725060.png" /> corresponds to another distribution function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725061.png" />. The points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725062.png" /> are chosen in such a way that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725064.png" />. The empty-boxes test is based on the statistic <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725065.png" />, equal to the number of intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725066.png" /> containing none of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725067.png" />. The empty-boxes test is determined by the critical region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725068.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725069.png" /> is rejected. Since under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725071.png" /> has a probability distribution defined by a uniform allocation, whereas under <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725072.png" /> it has a distribution defined by a polynomial allocation, it is possible to use limit theorems for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725073.png" /> to calculate the power <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725074.png" /> of this test (see [[#References|[2]]]).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725075.png" /> and it is assumed that they are put in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725076.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725077.png" /> positions of each block are equi-probable and the number of blocks <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725078.png" />, then for bounded or weakly increasing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725079.png" />, the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/r/r077/r077250/r07725080.png" /> again have asymptotically a normal or Poisson distribution.
+
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.).
 
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.).
Line 51: Line 163:
 
====References====
 
====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>
 
<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====
 
====Comments====

Latest revision as of 16:23, 4 March 2022


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)
How to Cite This Entry:
Random allocation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Random_allocation&oldid=14763
This article was adapted from an original article by B.A. Sevast'yanov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article