Lobachevskii Journal of Mathematics

http://ljm.ksu.ru
ISSN 1818-9962

Vol. 25, 2007, 3–7 \begin{matrix}c \\ ◯ \end{matrix} F. G. Avkhadiev, A. N. Chuprunov

F. G. Avkhadiev, A. N. Chuprunov

THE PROBABILITY OF A SUCCESSFUL ALLOCATION OF BALL GROUPS BY BOXES

Abstract. Let p = p_{Nn} be the probability of a successful allocation of n groups of distinguishable balls in N boxes in equiprobable scheme for group allocation of balls with the following assumption: each group contains m balls and each box contains not more than q balls from a same group. If q = 1, then we easily calculate p and observe that p → e^{− \frac{m(m−1)}{2} α_{0}} as n, N → ∞ such that α = \frac{n}{N} → α_{0} < ∞. In the case 2 ≤ q we also find an explicit formula for the probability and prove that p → 1 as n, N → ∞ such that α = \frac{n}{N} ≤ α′ < ∞.

1. Introduction

Many papers are devoted with problems of the allocation theory (see, for instance, Weiss (1958), Bekéssy (1963, 1964), the monograph by Kolchin, Sevast’yanov, Chistyakov (1978) and references therein, Vatutin and Mikhajlov (1982)). In this paper we intend to study some open problems related to known results by A.N.Timashev. Namely, in the paper by Timashev (2000) the allocation theory with a restriction for the number of balls in boxes is developed. We will study a more general case when there is a restriction for balls from a same group.

More precisely, we consider the following situation. Let n be the number of ball groups and let N be the number of boxes in equiprobable scheme for group allocation of distinguishable balls. We suppose that each ball group contains m balls. Denote by B_{q}(n, N, m) the following event: each box contains not more than q balls from a same ball group, 1 ≤ q ≤ m. The aim of this paper is to find the probability p of the event B_{q}(n, N, m) and its asymptotic behavior as n, N → ∞ such that α = \frac{n}{N} → α_{0}. We will obtain some explicit formulas for the probability and prove that

Key words and phrases. equiprobable scheme for group allocation of particles, generating function, Cauchy integral.

1 − p ≤ \frac{α}{N^{q−1}} C,

where C is a constant dependent on m and q only.

2. The main results

The number of allocations of the i-th group is equal to N^{m}. The number of allocations of the i-th group such that each box contains not more than q balls equals

M_{m}(N, q) = ∑ ; \begin{matrix}l_{1} + ⋯ + l_{N} = m \\ 0 ≤ l_{1}, …, l_{N} ≤ q \end{matrix} \frac{m!}{l_{1}! … l_{N}!}.

Therefore the probability of the event such that for the allocation of i-th group in each box it appears not more than q balls

p_{i} = \frac{M_{m}(N, q)}{N^{m}} and p = ∏_{i=1}^{n} p_{i} = (\frac{M_{m}(N, q)}{N^{m}})^{n} .

If q ≥ m then it is clear that M_{m}(N, q) = N^{m} and, consequently, p = 1. In particular, if m = 1 or m = q = 2, then p = 1.

Therefore, we only have to consider the case when m ≥ 2 and q ≤ m−1.

Theorem 1. If m ≥ 2 and 1 ≤ q ≤ m − 1, then

p = (1 − \frac{A}{q!N} )^{n} ,  (1)

where

A = ∑_{ν=q}^{m−1} \frac{1}{N^{ν−1}} \frac{d^{ν}(z^{q}(1 + \frac{z}{1!} + … \frac{z^{q}}{q!} )^{N−1})}{dz^{ν}} |_{z=0} .

Moreover

1 − p ≤ \frac{α}{N^{q−1}} C,  (2)

where

C = \frac{1}{q!} ∑_{ν=q}^{m−1} \frac{ν!}{(ν − q)!}.

Proof. We will use the representation of M_{m}(N, q) as a Cauchy integral (see Timashev (2000), formula (4)):

M_{m}(N, q) = \frac{m!}{2πi} ∮_{C} \frac{(1 + \frac{z}{1!} + … \frac{z^{q}}{q!} )^{N}}{z^{m+1}} dz,

where C is a positively oriented circle with center at the point z = 0. Therefore, we obtain

p = (\frac{m!}{2πi} ∮_{C} \frac{[f(z)]^{N}}{N^{m}z^{m+1}} dz)^{n} ,

where

f(z) = 1 + \frac{z}{1!} + … \frac{z^{q}}{q!} .

Denote

a(m, N, q) = \frac{d^{m}f^{N}(z)}{dz^{m}} |_{z=0} .

It is clear that

p = (\frac{a(m, N, q)}{N^{m}})^{Nα} .

Since

f′(z) = f(z) − \frac{z^{q}}{q!} ,

by mathematical induction on m, we obtain

a(m, N, q) = N \frac{d^{m−1}(f^{N−1}(z)f′(z))}{dz^{m−1}} |_{z=0} =

= N \frac{d^{m−1}f^{N}(z)}{dz^{m−1}} |_{z=0} − \frac{N}{q!} \frac{d^{m−1}(z^{q}f^{N−1}(z))}{dz^{m−1}} |_{z=0} =

= N^{m} − \frac{1}{q!} ∑_{ν=q}^{m−1} N^{m−ν} \frac{d^{ν}(z^{q}f^{N−1}(z))}{dz^{ν}} |_{z=0} .

Denoting

A = ∑_{ν=q}^{m−1} \frac{1}{N^{ν−1}} \frac{d^{ν}(z^{q}f^{N−1}(z))}{dz^{ν}} |_{z=0}

we have (1).

Obviously, A ≥ 0. Moreover, for all N, ν, q ∈ N, ν ≥ q we obtain

\frac{d^{ν}(z^{q}f^{N−1}(z))}{dz^{ν}} |_{z=0} ≤ \frac{d^{ν}(z^{q}e^{(N−1)z})}{dz^{ν}} |_{z=0} = \frac{(N − 1)^{ν−q}ν!}{(ν − q)!}.

From this it follows that

0 ≤ A ≤ ∑_{ν=q}^{m−1} \frac{ν!}{(ν − q)!} \frac{(N − 1)^{ν−q}}{N^{ν−1}} < \frac{1}{N^{q−1}} ∑_{ν=q}^{m−1} \frac{ν!}{(ν − q)!}.

Consequently,

1 − p = 1 − (1 − \frac{A}{q!N} )^{Nα} ≤ \frac{A}{q!N} Nα ≤ \frac{α}{N^{q−1}} C.

This completes the proof of Theorem 1.

Theorem 2. Suppose that m ≥ 2 and 1 ≤ q ≤ m − 1.

(i) If q = 1, then

p = (1 − \frac{1}{N} )^{n} (1 − \frac{2}{N} )^{n} … (1 − \frac{m − 1}{N})^{n}

and

p → e^{− \frac{m(m−1)}{2} α_{0}} as n, N → ∞ such that \frac{n}{N} → α_{0}.

(ii) If 2 ≤ q ≤ m − 1, then

p → 1 as n, N → ∞ such that α = \frac{n}{N} ≤ α′ < ∞.

Proof. (i) We easily have M_{m}(N, 1) = N(N − 1) … (N − m + 1) and

p = (\frac{N}{N} \frac{N − 1}{N} … \frac{N − m + 1}{N})^{n} =

(1 − \frac{1}{N} )^{n} (1 − \frac{2}{N} )^{n} … (1 − \frac{m − 1}{N})^{n} .

Therefore, if n, N → ∞ such that \frac{n}{N} → α_{0}, then one has

p → e^{−(1+2+···+m−1)α_{0}} = e^{− \frac{m(m−1)}{2} α_{0}}.

In the case 2 ≤ q ≤ m − 1 we have \frac{α}{N^{q−1}} C → 0 as n, N → ∞ such that α ≤ α′. By (2) this implies (ii).

The proof of Theorem 2 is complete.

3. Some remarks

Let q = 3 and n_{k}, N_{k}, k ∈ N be natural numbers with the properties: N_{k} < N_{k+1}, k ∈ N, and n_{k}, N_{k} → ∞ as k → ∞ such that α_{N_{k}} = \frac{n_{k}}{N_{k}} ≤ α′ < ∞. Suppose that the events B_{3}(n_{k}, N_{k}) are defined on the

SUCCESSFUL ALLOCATION OF BALL GROUPS 7

same probability space (Ω, A, P). Using (2) with q = 3, from (1) with p = p_{N_{k}n_{k}} we obtain

∑_{k=1}^{∞}(1 − p_{N_{k}n_{k}}) = ∑_{k=1}^{∞} (1 − (1 − \frac{A_{N_{k}}}{3!N_{k}} )^{N_{k}α_{N_{k}}} ) ≤ ∑_{k=1}^{∞} \frac{A_{N_{k}}}{3!N_{k}} N_{k}α_{N_{k}} ≤

\frac{α′}{6} ∑_{k=1}^{∞} A_{N_{k}} ≤ \frac{α′}{6} (∑_{ν=3}^{m−1} \frac{ν!}{(ν − 3)!}) ∑_{k=1}^{∞} \frac{1}{N_{k}^{2}} < ∞.

Therefore for almost all sequences of allocations into N_{k} boxes of n_{k} groups containing m balls there exists k_{0} ∈ N dependent on ω ∈ Ω such that for all k > k_{0} and for each allocation each box contains not more than 3 balls from a same group.

In the case q = 1 this is not true. The case q = 2 presents an open problem.

Acknowledgement The authors thank the Russian fund of basic research for financial

support by the grant 05-01-00523 for F.G. Avkhadiev.

References

[1] Békéssy, A., On classical occupancy problems. I, Magy. Tud. Akad. Mat. Kutató Int. Kozl. 8(1-2) (1963), 59-71.

[2] Békéssy, A., On classical occupancy problems. II, Magy. Tud. Akad. Mat. Kutató Int. Kozl. 9(1-2) (1964), 133-141.

[3] Kolchin, V.F., Sevast’ynov, B.A., and Chistiakov, V.P., Random allocations, W. H. Winston & Sons, Washington D.C.(1978).

[4] Vatutin, V.A., Mikhajlov, V.G. Limit theorems for the number of empty cells in an equiprobable scheme of group allocation of particles, Theory Probab. Appl. 27(34) (1982), 734-743.

[5] Timashev, A.N. On the large-deviation asymptotics in an allocation scheme of particles into distinguishable cells with restrictions on the size of the cells, Theory Probab. Appl. 45(3) (2000), 494-506.

[6] Weiss, I. Limiting distributions in some occupancy problems, Ann. Math. Statist., 29(3) (1958), 878-884.

Kazan State University, Chebotarev Institute of Mathematics and Mechanics Universitetskaya str. 17, Kazan, 420008, Russia E-mail address: favhadiev@ksu.ru E-mail address: achuprunov@mail.ru

Received January 24, 2007