Inequalities and limit theorems for random allocations

Preparing to load PDF file. please wait...

0 of 0
100%
Inequalities and limit theorems for random allocations

Transcript Of Inequalities and limit theorems for random allocations

doi: 10.2478/v10062-011-0006-5
ANNALES
UNIVERSITATIS MARIAE CURIE-SKŁODOWSKA LUBLIN – POLONIA

VOL. LXV, NO. 1, 2011

SECTIO A

69–85

ISTVA´ N FAZEKAS1 2, ALEXEY CHUPRUNOV and JÓZSEF TU´ RI
Inequalities and limit theorems for random allocations
Abstract. Random allocations of balls into boxes are considered. Properties of the number of boxes containing a fixed number of balls are studied. A moment inequality is obtained. A merge theorem with Poissonian accompanying laws is proved. It implies an almost sure limit theorem with a mixture of Poissonian laws as limiting distribution. Almost sure versions of the central limit theorem are obtained when the parameters are in the central domain.
1. Introduction. Let n balls be placed successively and independently into N boxes. Let µr(n, N ) denote the number of boxes containing r balls. There are several theorems concerning the limit laws of µr(n, N ) when the parameters belong to certain domains (see e.g. Weiss [16], R´enyi [14], B´ek´essy [2], and the monograph Kolchin–Sevast’yanov–Chistyakov [12]). It is known that if n, N → ∞ in the central domain, then the limit of the standardized µr(n, N ) is standard normal. In the left-hand and in the right-hand r-domains the limit of µr(n, N ) is Poisson distribution. Strong laws of large numbers are obtained for µr(n, N ) in Chuprunov–Fazekas [5]. Concerning the generalized allocation scheme see Kolchin [11].
1Corresponding author. 2Supported by the Hungarian Foundation of Scientific Researches under Grant No. OTKA T-079128. 2000 Mathematics Subject Classification. 60F05, 60F15, 60C05. Key words and phrases. Random allocation, moment inequality, merge theorem, almost sure limit theorem.

70

I. Fazekas, A. Chuprunov, J. Tu´ri

In this paper the most general result is the inequality in Theorem 2.1. It gives an upper bound for the L2-distance of µr(n, N ) and its conditional expectation given the last n − k allocations.
Then asymptotic results are considered. The most interesting case is the Poisson-type limiting distribution. In that case we do not have one single limiting distribution. Instead of a limit theorem we can prove a merge theorem, i.e. we can give a family of accompanying Poissonian laws being close to the original distributions (Theorem 2.2).
Then we obtain almost sure (a.s.) versions of the limit theorems for µr(n, N ). The general form of the a.s. limit theorem is the following. Let
Yn, n ∈ N be a sequence of random elements defined on the probability space (Ω, A, P). A.s. limit theorems state that

(1.1)

1n Dn dkδYk(ω) ⇒ ν ,
k=1

as n → ∞, for almost every ω ∈ Ω, where δx is the unit mass at point x and ⇒ ν denotes weak convergence to the probab√ility measure ν. In the simplest form of the a.s. CLT Yk = (X1 + · · · + Xk)/ k, where X1, X2, . . . , are i.i.d. real random variables with mean 0 and variance 1, dk = 1/k, Dn = log n, and ν is the standard normal law N (0, 1); see Berkes [3] for an overview. Recently, several papers are devoted to the background, the general forms and certain special cases of the a.s. limit theorem, see e.g. Berkes–Cs´aki [4], Fazekas and Rychlik [8], Matuła [13], H¨ormann [10], Orzóg–Rychlik [15].
The present paper can be considered as an extension of some results in the paper of Fazekas–Chuprunov [6], where a.s. limit theorems were obtained for the number of empty boxes (see also Becker–Kern [1]). In Section 2, we consider an appropriate representation of µr(n, N ) in terms of independent, uniformly distributed random variables in order to handle the dependence structure inside the array µr(n, N ), n, N = 1, 2, . . . . As µr(n, N ) depends on two parameters, we consider a.s. limit theorems of the form

(1.2)

1

Dn

dkK δYkK (ω) ⇒ ν ,

(k,K )∈Tn

as n, N → ∞, for almost every ω ∈ Ω, where Tn denotes a two-dimensional domain. To prove the above type theorems, we apply a general a.s. limit theorem, i.e. Theorem 2.1 of Fazekas–Chuprunov [6]. We quote it in Theorem 4.1. This result is an extension of known general a.s. limit theorems (see e.g. Fazekas and Rychlik [8]). We remark that multiindex versions of a.s. limit theorems were obtained in Fazekas–Rychlik [9]. However, as the weights there are of product type, we can not apply those results for
domains like {(k, i) : α1(k) ≤ i ≤ α2(k), k ∈ N}.
In this paper we use the general theorem to obtain Theorems 2.3, 2.4, 2.5, and 2.6. Among them Theorems 2.5, 2.6 concern the central domain

Inequalities and limit theorems for random allocations

71

(i.e. when 0 < α1 ≤ n/N ≤ α2 < ∞) and the limiting distribution is standard normal. In Theorem 2.4 the parameters can vary in a domain not included in the central domain but the limiting distribution is again standard normal. The most interesting case is the Poisson-type limiting distribution (Theorem 2.3). The limiting distribution in the almost sure limit theorem (i.e. in Theorem 2.3) will be a mixture of the accompanying laws in the usual limit theorem (i.e. in Theorem 2.2). In almost sure limit theory the above situation is well-known (see Fazekas–Chuprunov [7] for semistable laws, see also Theorems 2.10, 2,11, 2.12 in Fazekas–Chuprunov [6] for random allocations).

2. Main results.

Random allocations. Let ξ, ξj, j ∈ N, be independent random variables

uniformly distributed on [0, 1]. Let N ∈ N. Consider the subdivision of the

interval

[0,

1)

into

the

subintervals

∆i

=

∆N i

=

[ i−N1 ,

i N

),

1



i



N.

We consider the intervals ∆i, i = 1, . . . , N , as a row of boxes. Random

variables ξj, j = 1, 2, . . . , are realizations of ξ. Each realization of ξ we

treat as a random allocation of one ball into the N boxes. The event ξj ∈

∆i means that the jth ball falls into the ith box. Let n ∈ N, A(0) =

{1, 2, . . . , n}.

(2.1)

N

µr(n, N ) =

I{ξj ∈∆i}

I{ξj ∈/∆i}

i=1 |A|=r, j∈A A⊂A(0)

j∈A(0)\A

is

the

number

of

boxes

containing

r

balls

and

N Cnr

1 Nr

1 − N1

n−r is its ex-

pectation. Here Cnr =

n r

is the binomial coefficient and IB is the indicator

of the event B.

For

n, N

∈N

we

will

use

the

notation

α=

n N

and

pr(α) = (αr/r!)e−α.

It

is known (see Kolchin et al. [12], Ch. 2, Sec. 1, Theorem 1) that the following

limit relations (2.2) and (2.3) hold for any fixed r, t and if n, N → ∞ such

that α = o(N ). For the expectation we have

(2.2)

Eµr(n, N ) = N pr(α) + pr(α) r − α/2 − Cr2/α + O (1/N )

and for the covariances we have

(2.3)

cov(µr(n, N ), µt(n, N )) ∼ N σrt(α),

where

σrr(α) = pr(α) 1 − pr(α) − pr(α)(α − r)2/α , σrt(α) = −pr(α)pt(α) (1 + (α − r)(α − t)/α) , if t = r.

We shall use the notation

(r)
Dn,N

=

D2µr(n, N ) =

cov(µr(n, N ), µr(n, N )).

72

I. Fazekas, A. Chuprunov, J. Tu´ri

We shall need a lower bound for D(nr,)N , therefore the following remark will
be useful.

Remark 2.1.

(α − r)2 1 − pr(α) − pr(α) α ≥ cr > 0,

if r ≥ 2 is fixed and α is arbitrary, or if r = 0, 1 and α ≥ α0 > 0.

As in the theory of random allocations the roles of n and N are fixed,
therefore we shall use the following notation for two-dimensional indices:
(n, N ), (k, K) ∈ N2.
Let

(r) µr(n, N ) − Eµr(n, N )

SnN =

(r)

Dn,N

be the standardized variable, where (n, N ) ∈ N2.

The main inequality. Let n, N, r ∈ N, 0 ≤ k ≤ n. Recall that n is
the number of balls, N is the number of boxes. ξj denotes the jth ball, ∆i denotes the ith box. We use the notation A(k) = {k + 1, . . . , n}, k = 0, 1, . . . , n − 1. Let

N

r1

ζn = ζnN =

I{ξj ∈∆i}

I{ξj∈/∆i}−N Cn N r

i=1 |A|=r, j∈A

j∈A(0)\A

A⊆A(0)

1 1−
N

n−r
.

We see that ζn = µr(n, N ) − Eµr(n, N ), c.f. (2.1). We have

N

ζn =

(ηiA − EηiA),

i=1 |A|=r, A⊆A(0)

where

ηiA = I{ξj ∈∆i}

I{ξj ∈/∆i}

j∈A

j∈A(0)\A

is the indicator of the event that the ith box contains the balls with indices in the set A (and it does not contain any other ball). Let Fkn be the σalgebra generated by ξk+1, . . . , ξn. We will use the following conditional

Inequalities and limit theorems for random allocations

73

expectations ηi(Ak) = E(ηiA|Fnk) and
N
ζnk = ζnkN = E(ζn|Fkn) =
i=1 |A|=r, A⊆A(0)

ηi(Ak) − Eηi(Ak)

(2.4)

N
=
i=1 |A|=r, A⊆A(0)

1 N r−|A∩A(k)|

1 1−
N

k−(r−|A∩A(k)|)

1

1 n−r

×

I{ξj ∈∆i}

I{ξj ∈/∆i} − N r

1− N

.

j∈A∩A(k)

j∈A(k)\A

The following inequality will play an important role in the proofs of our theorems.

Theorem 2.1. Let 0 < k < n, 0 < r ≤ n and N be fixed. Then we have

(2.5) E(ζn − ζnk)2 ≤ ckαr−1

1 − 1 n+k αr + 1 − 1 n−r (α + 1) ,

N

N

where c < ∞ does not depend on n, N , and k, but can depend on r.

Remark 2.2. In Fazekas–Chuprunov [6] the following inequality was ob-

tained for the number of empty boxes. Let r = 0. Let k < n and N be

fixed. Then we have

(2.6)

k2

1 n−k

E(ζn − ζn) ≤ k

1− N

and (2.7)

E(ζn − ζnk)2 ≤ kNn .

In Chuprunov–Fazekas [6] a fourth moment inequality was obtained for µr(n, N ).

Limit theorems for random allocations for r ≥ 2. First we consider the Poisson limiting distribution. In that case we do not have one single limiting distribution in the ordinary limit theorem. Instead of a limit theorem we can prove a merge theorem, i.e. we can give a family of accompanying laws being close to the original distributions (Theorem 2.2). The limiting distribution in the almost sure limit theorem (i.e. in Theorem 2.3) will be a mixture of the accompanying laws.
The following result is a version of Theorem 3 in Section 3, Chapter II of Kolchin–Sevast’yanov–Chistyakov [12]. In our theorem the novelty is that we state uniformity with respect to (n, N ) in a certain domain, while l remains fixed.

74

I. Fazekas, A. Chuprunov, J. Tu´ri

Theorem 2.2. Let r ≥ 2 and l ∈ N be fixed. Then, as n, N → ∞,

(2.8)

P(µr(n, N ) = l) = 1 (N pr)le−Npr (1 + o(1))
l!

uniformly with respect to the domain T = {(n, N ) : N ≥ n(2r−1)/(2r−2) log n}.

Now turn to the a.s. version of Theorem 2.2.

Theorem 2.3. Let r ≥ 2, 0 < λ1 < λ2 < ∞ be fixed. Let Tn be the
following domain in N2

Tn = (k, K) ∈ N2 : k ≤ n, λ1 ≤ k ≤ λ2 .
K 1− r1

Let

1

1

Qn(ω) = r−r 1 (λ2 − λ1) log n (k,K)∈Tn K2− r1 δµr(k,K)(ω).

Then, as n → ∞,

Qn(ω) ⇒ µτ

for almost all ω ∈ Ω, where τ is a random variable with distribution

(2.9)

1

λ2 1

P(τ = l) =

λ2 − λ1 λ1 l!

xr l e− xrr! dx, r!

l = 0, 1, . . . .

Now consider the case of the normal limiting distribution.

Theorem B. Let r ≥ 2 be fixed. If n, N → ∞, so that N pr(α) → ∞, then Sn(rN) ⇒ γ.
Here and in the following γ denotes the standard normal law. The proof of Theorem B can be found in the monograph Kolchin et al. [12], Ch. 2, Sec. 3, Theorem 4.
Consider an almost sure version of Theorem B.

Theorem 2.4. Let r ≥ 2 be fixed, 0 < α1, α2 < ∞ and
Tn = (k, K) ∈ N2 : k ≤ n, α1k ≤ K ≤ α2k(2r+1)/(2r) .

Let

Q(nr)+(ω) = log1 n

1 δ (r) .
k(log α2 − log α1 + (1/2r) log k)K SkK(ω)

(k,K )∈Tn

Then, as n → ∞, we have

Q(nr)+(ω) ⇒ γ, for almost every ω ∈ Ω.

Inequalities and limit theorems for random allocations

75

Almost sure limit theorems for random allocations in the central domain. If n, N → ∞, so that
n 0 < α1 ≤ N ≤ α2 < ∞,

where α1 and α2 are some constants, then it is said that n, N → ∞ in a central domain. In a central domain we have the following central limit theorem.

Theorem A. Let 0 < α1 < α2 < ∞.

If n, N

→ ∞, so that α =

n N



[α1, α2], then Sn(rN) ⇒ γ.

The proof of Theorem A can be found in the monograph Kolchin et al. [12], Ch. 2, Sec. 2, Theorem 4.
Consider almost sure versions of Theorem A. In the following theorems the domain is narrower than the one in Theorem 2.4, but they are valid for arbitrary r ≥ 0.

Theorem 2.5. Let r ≥ 0 be fixed, 0 < α1 < α2 < ∞ and

Q(r)(ω) =

1

1

δ

.

n

(log α2 − log α1) log n

kK Sk(rK) (ω)

k≤n

{K

:

α1



k K

≤α2

}

Then, as n → ∞, we have

Q(nr)(ω) ⇒ γ, for almost every ω ∈ Ω.
In the above theorem the limit was considered for n → ∞ (and the indices of the summands were in a fixed central domain). The following theorem is a two-index limit theorem, i.e. n → ∞ and N → ∞. The relation of n and N could be arbitrary, however, as the indices of the summands are in a fixed central domain, we assume that (n, N ) is in the central domain considered.

Theorem 2.6. Let r ≥ 0 be fixed, 0 < α1 < α2 < ∞ and

(r)

1

1

QnN (ω) = (log α2 − log α1) log n

kK δSk(rK) (ω) .

k≤n

{K

:

K

≤N,

α1



k K

≤α2

}

Then,

as

n, N



∞,

so

that

α1



n N



α2,

we

have

Q(nrN) (ω) ⇒ γ, for almost every ω ∈ Ω.

3. Proof of Theorem 2.1. Since EηiA = Eηi(Ak) and

E(ηi1A1 − ηi(1kA) 1 )(ηi2A2 − ηi(2kA) 2 ) = E(ηi1A1 · ηi2A2 ) − E(ηi(1kA) 1 · ηi(2kA) 2 ),

76

I. Fazekas, A. Chuprunov, J. Tu´ri

for any A1, A2, we have



2

N
E(ζn − ζnk)2 = 

(ηiA − ηi(Ak))

 i=1 |A|=r,



A⊆A(0)





N

=





E(ηi1A1 − ηi(1kA) 1 )(ηi2A2 − ηi(2kA) 2 )

i1,i2=1 |A1|=|A2|=r,



A1 ,A2 ⊂A(0)





 =
 i1=i2 A1∩A2=∅,|A1|=|A2|=r,
A1 ,A2 ⊂A(0)


E(ηi1A1 · ηi2A2 ) − E(ηi(1kA) 1 · ηi(2kA) 2 ) 



 +
 i1=i2 A1∩A2=∅,|A1|=|A2|=r,
A1 ,A2 ⊂A(0)


E(ηi1A1 · ηi2A2 ) − E(ηi(1kA) 1 · ηi(2kA) 2 ) 



N +
 i=1 A1=A2,|A1|=|A2|=r,
A1 ,A2 ⊂A(0)


E(ηiA1 · ηiA2 ) − E(ηi(Ak)1 · ηi(Ak)2 ) 



N +


E(ηiA)2 − E(ηi(Ak))2 

i=1  |A|=r,



A⊂A(0)

= B1 + B2 + B3 + B4.

First consider B1. Let i1 = i2, A1 ∩ A2 = ∅ and j ∈ A1 ∩ A2. Then

I{ξj ∈∆i1 }I{ξj ∈∆i2 } = 0,
therefore E(ηi1A1 ηi2A2 ) = 0. So B1 ≤ 0.
Now turn to B3. Now i1 = i2, A1 = A2. If j ∈ A1 \ A2 or j ∈ A2 \ A1, then
I{ξj ∈∆i1 }I{ξj ∈/∆i2 } = 0 or I{ξj ∈/∆i1 }I{ξj ∈∆i2 } = 0.
So E(ηi1A1 · ηi2A2) = 0. Therefore we have B3 ≤ 0.

Inequalities and limit theorems for random allocations

77

Now consider B2. Let i1 = i2 and A1 ∩ A2 = ∅. It holds that

E(ηi1A1 ηi2A2 ) − E(ηi(1kA) 1 ηi(2kA) 2 )

1 = N 2r

2 1−
N

n−2r

1 − N 2r

1 1−
N

2k−(2r−|A(k)∩A1|−|A(k)∩A2|)

2 1−
N

n−k−|A(k)∩A1|−|A(k)∩A2|

1 = N 2r

2 n−2r

1 2k−2r+x

2 n−k−x

1−

− 1−

1−

.

N

N

N

Here x = |A(k) ∩ A1| + |A(k) ∩ A2|, so we have 0 ≤ x ≤ 2r, n − k. Now let a = 1 − N2 , b = 1 − N1 . Then 0 < a < b < 1, moreover b2 − a = 1/N 2. First consider those terms from B2 in which x = 2r. It means that A1, A2 ⊂
A(k). The number of these terms is N (N − 1)(n − k)!/(r!r!(n − k − 2r)!).
The magnitude of these terms is

1

2 n−2r

1 2k

2 n−k−2r

N 2r

1− N

− 1− N

1− N

=

1 an−k−2r(ak − b2k) ≤

1

an−k−2r kb2(k−1)

1 .

N 2r

N 2r

N2

(Above we applied the mean value theorem.) So the contribution of these terms is not greater than

(n − k)!

1

N (N − 1) r!r!(n − k − 2r)! N 2r

2 1−
N

n−k−2r
k

1 1−
N

2(k−1) 1 N 2 = B21.

Now turn to the remaining terms of B2, i.e. the terms with x < 2r. The number of these terms is

n!

(n − k)!

2rkn2r−1

N (N −1) r!r!(n − 2r)! − r!r!(n − k − 2r)! ≤ N (N −1) r!r! = B221.

(Above we applied the following fact. If 0 ≤ bi ≤ ai ≤ c and ai − bi ≤ l

for i = 1, 2, . . . , s, then

s i=1

ai



s i=1

bi

≤ slcs−1.)

Using

the

mean

value

78

I. Fazekas, A. Chuprunov, J. Tu´ri

theorem, we obtain for the magnitudes of these terms that

1 N 2r

an−2r − b2k−2r+xan−k−x

= 1 an−k−2r N 2r

ak − b2k + b2k 1 − a 2r−x b

≤ 1 an−k−2r N 2r

1 2(k−1) 1

2k

1

1− N

kN2 + b

(2r − x) N −1

1

2

= N 2r

1− N

n−k−2r

1 1−
N

2(k−1) 1

1

kN2 +

1− N

2k

1

(2r − x)

N −1

= B222.

Therefore we have

(3.1)

B2 ≤ B21 + B221B222

n2r ≤ c N 2r

1 1−
N

n+k−2r−2

n2r−1

k + c N 2r

1 1−
N

n+k−2r−2
k2

n2r−1 + c N 2r−1

1 1−
N

n+k−2r
k ≤ cα2r−1

1 1−
N

n+k
k(α + 1).

Finally, consider B4. Let r1 = |{1, 2, . . . , k} ∩ A| = r − |A ∩ A(k)|. We have

B4 = N
|A|=r, A⊂A(0)
=N
|A|=r, A⊂A(0)

E(ηiA)2 − E(ηi(Ak))2

1

1 n−r

Nr

1− N

1 − N 2r1

1 1−
N

2(k−r1) 1 N r−r1

1 1−
N

n−k−(r−r1)

min{k,r}

=N

Ckr1 Cnr−−rk1

r1=max{r−(n−k),0}

1

1 n−r

Nr

1− N

1 − N r+r1

1 1−
N

n+k−r−r1
DomainLimit TheoremsLimit TheoremTheoremDistribution