Random allocation
A probability scheme in which particles are randomly distributed over
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
. Let
be the number of cells in which, after distribution, there are exactly
particles, and let
.
The generating function
![]() |
![]() |
has the following form:
![]() | (1) |
![]() |
The generating function (1) allows one to compute the moments of the and to study the asymptotic properties of their distribution as
. These asymptotic properties are to a large extent determined by the behaviour of the parameter
— the average number of particles in a cell. If
and
, then for fixed
and
,
![]() | (2) |
where ,
![]() |
and is the Kronecker delta. One can identify five domains with different types of asymptotic behaviour of
as
.
The central domain corresponds to . The domain for which
![]() |
is called the right -domain, and the right intermediate
-domain is that for which
![]() |
For , the left
-domain corresponds to the case where
![]() |
The left intermediate -domain is that for which
![]() |
The left and right intermediate -domains for
are identified with the corresponding
-domains.
In the case of an equi-probable scheme, has asymptotically a Poisson distribution in the right
-domains. The same is true in the left
-domains when
, and when
or
,
and
have Poisson distributions in the limit. In the left and right intermediate
-domains the
have asymptotically a normal distribution. In the central domain there is a multi-dimensional asymptotic normality theorem for
; the parameters of the limiting normal distribution are defined by the asymptotic formulas (2) (see [1]).
An allocation in which particles are distributed over
cells independently of each other in such a way that the probability of each of the particles falling into the
-th cell is equal to
,
, 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
be independent random variables each having a continuous distribution function
(hypothesis
). The alternative hypothesis
corresponds to another distribution function
. The points
are chosen in such a way that
,
. The empty-boxes test is based on the statistic
, equal to the number of intervals
containing none of the
. The empty-boxes test is determined by the critical region
, where
is rejected. Since under
,
has a probability distribution defined by a uniform allocation, whereas under
it has a distribution defined by a polynomial allocation, it is possible to use limit theorems for
to calculate the power
of this test (see [2]).
In another scheme the particles are grouped in blocks of size and it is assumed that they are put in the
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
positions of each block are equi-probable and the number of blocks
, then for bounded or weakly increasing
, the
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) |
Random allocation. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Random_allocation&oldid=48420