A Berry-Esseen bound for U-Statistics

Journal of Mathematical Sciences, Vol. 128, No. 1, 2005

A BERRY–ESSEEN BOUND FOR U -STATISTICS L. V. Gadasina

UDC 519.21

The rate of convergence in the central limit theorem for nondegenerate U -statistics of n independent random variables is investigated under minimal sufficient moment conditions on canonical functions of the Hoeffding representation. Bibliography: 12 titles.

1. Introduction Let X1 , . . . , Xn be independent random variables with values from a measurable space (X, B). Assume that n ≥ m ≥ 2 and consider an U -statistic
Un = Un (X1 , . . . , Xn ) = Φi1 ...im (Xi1 , . . . , Xim ), 1≤i1 <···
where Φi1 ...im : X → R are symmetric functions such that E|Φi1 ...im (Xi1 , . . . , Xim )| < ∞ for all 1 ≤ i1 < · · · < im ≤ n. We introduce the following notation: Ikc := ik+1 , . . . , ic ; Ic := I0c ; Iˇkc := 1 ≤ ik+1 < · · · < ic ≤ n; Iˇc := Iˇ0c ; XIc := Xi1 , . . . , Xic ; similarly, Jkc := jk+1 , . . . , jc; Jˇkc := 1 ≤ jk+1 < · · · < jc ≤ n etc. We define the canonical functions   c   gIc = gIc (XIc ) = ··· Un (δXis (dyis ) − Pis (dyis )) Ps (dys ) m

X

=

c


X

s∈Im \Ic

s=1




(−1)c−d (E[Un |XJd ] − EUn ),

d=1 Jˇd ,Jd ∈Ic

where 1 ≤ i1 < · · · < ic ≤ n, c = 1, . . . , m. According to the Hoefding representation, Un =

m





gIc + EUn =

c=1 1≤i1 <···
We assume that σn2 = Denote

n  j=1

m


Un (gIc ) + EUn .

c=1

Egj2 > 0, i.e., we consider nondegenerate U -statistics only. ∆n (x) := |P (σn−1 (Un − EUn ) < x) − Φ(x)|

and ∆n := sup ∆n (x), x

where Φ(x) is the distribution function of the standard normal random variable (the Laplace function). The central limit theorem for nondegenerate U -statistics in the case of not necessarily identically distributed random variables was proved in 1948 in [10]. Later, the hypotheses were weakened (see, e.g., [12]). Our aim is to establish the rate of convergence under the minimal admissible moment conditions on the canonical functions gi1 ,...,ic , c = 1, . . . , m. The main part of known results deals with the case m = 2. A bound depending on maxi<j E|Φ(Xi , Xj )|3 was obtained in 1982 in [9]. In 1989 (see [8]), a bound depending on maxj E|gj |3 and maxi<j E|gij |5/3 was found. In 1998 (see [1]), the following inequality was established: 
n
3 2 ∆n ≤ 17( E|gj | + Egij ). j=1

i<j (n)

In [3], an example of a kernel Φ and random variables Xj = Xj , j = 1, . . . , n, was constructed such that E|g1 |3 < ∞, E|Φ|5/3−ε < ∞ for ε > 0, and ∆n ≥ c(ε)n−1/2+3ε/2 with some constant c(ε) > 0. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 298, 2003, pp. 54–79. Original article submitted November 18, 2003. 2522

c 2005 Springer Science+Business Media, Inc. 1072-3374/05/1281-2522 

2. Results Consider the truncated random variables gInc = gIc I(|gIc | ≤ σn ),

1 ≤ i1 < · · · < ic ≤ n,

where I(A) is the indicator function of a set A ∈ B. Theorem 1. If σn2 > 0, then ∆n ≤ Am ( σn−2

n


Egj2 I(|gj | > σn ) + σn−3

j=1

+σn−1

m





E|gj |3 I(|gj | ≤ σn )

j=1

E|gIc |I(|gIc | > σn ) +

c=2 1≤i1 <···
+

n


m


1 σ−p (2 − p)3 n c=2




E|gin1 · . . . · ginc gInc |

1≤i1<···
c=2 m





σn−c−1

E|gIc |p I(|gIc | ≤ σn ))

1≤i1 <···
for all 1 ≤ p < 2 and n ≥ m, where Am depends on m only. Theorem 2. Under the conditions of Theorem 1, ∆n ≤ Am ( σn−2

n


Egj2 I(|gj | > σn ) + σn−3

j=1

+σn−1

m





E|gj |3 I(|gj | ≤ σn )

j=1

E|gIc |I(|gIc | > σn ) + σn−3

c=2 1≤i1 <···
+

n


m





E|gin1 |2/c · . . . · |ginc |2/c|gInc |

c=2 1≤i1<···
m
1 −p σ n (2 − p)3 c=2




E|gIc |pI(|gIc | ≤ σn )).

1≤i1 <···
Corollary. If δc =

2c + 1 , 2c − 1

then ∆n ≤ Am

m


c = 1, . . . , m,


σn−δc

E|gIc |δc ,

Iˇc

c=1

where Am depends on m only. 3. Proofs Proof of Theorem 1. We introduce the following notation: 

 ···

gIc n (XIc ) = X

and

X

 X

s∈Ic \Jd

 Ps (dys ) = −

X

Un (gInc )

d 

(δXjs (dyjs ) − Pjs (dyjs ))

s=1

Un (gIc I(|gIc | > σn )) X

(δXis (dyis ) − Pis (dyis ))

s=1

 ···

X

c 

 ···

gIc Jd n (XJd ) = 

Un (gInc )

d  s=1

(δXjs (dyjs ) − Pjs (dyjs ))



Ps (dys ).

s∈Ic \Jd

2523

Let c > d. By the Hoefding representation, c


Un (gInc ) =




gIc Jd n (XJd ) + EUn (gInc ).

d=1 1≤j1 <···<jd ≤n

Using an analog of the lemma on cut-off random variables of [4] for the case of nonidentically distributed random variables, we see that c
m

∆n (x) ≤ |P (σn−1 (θ1 + gIc Jd n (XJd )) < x) − Φ(x)| c=1 d=1 Jˇd

+

m





P (|gIc | > σn ),

c=1 1≤i1<...ic ≤n

where θ1 = −

m



E|gIc |I(|gIc | > σn ).

c=1 Iˇc

Now we write

c
m



gIc Jd n (XJd ) =

n m



c=1 d=1 Jˇd

+

m



gIc n (XIc ) +

c=2 Iˇc

Further,

n m



gIc jn (Xj )

c=1 j=1 m−1


m



gIc Jd n (XJd ).

d=2 c=d+1 Jˇd

gIc jn (Xj ) =

c=1 j=1

n


gjn (Xj ) +

n m



j=1

gIc jn (Xj ).

c=2 j=1

Denote hcj = gIc jn , hcjn = hncj − Ehncj , σ ¯n2 =

n


hncj = hcj I(|hcj | ≤ σn ), c = 2, . . . , m, E(gjn +

m


j = 1, . . . , n,

hcjn )2 ,

c=2

j=1

zj = zj (Xj ) = σ ¯n−1 (gjn +

m


hcjn ),

sn =

c=2

and zˆj = zj + E(gjn +

n


zj ,

j=1 m


hncj ).

c=2

Applying again the lemma on cut-off random variables to hcj , we get the estimate ∆n (x) ≤

|P (σn−1 (θ1

n m m−1 m




+ (gjn + hcjn ) + gIc Jd n (XJd ) j=1

+

m

c=2 Iˇc

+

m

c=1 Iˇc

2524

gIc n (XIc ) +

c=2

d=2 c=d+1 Jˇd

m n



Ehncj ) < x) − Φ(x)|

j=1 c=2

P (|gIc | > σn ) +

n m

c=2 j=1

P (|gIcjn | > σn )

= |P (¯ σnσn−1 (sn + vn + wn ) + an < x) − Φ(x)| + dn , where ¯n−1 θ1 + σ¯n−1 an = σ

m n



Ehncj ,

j=1 c=2

dn =

m



P (|gIc | > σn ) +

c=1 Iˇc

n m



P (|gIcjn | > σn ),

c=2 j=1

vn = σ ¯n−1

m−1


m



gIc Jd n (XJd ),

d=2 c=d+1 Jˇd

and wn = σ ¯n−1

m



gIc n (XIc ).

c=2 Iˇc

Thus, ∆n ≤ sup |P (sn + vn + wn < x) − Φ(x)| x

σ ¯n x) − Φ(x)| + dn . σ x x n The well-known properties of the Laplace function Φ imply that + sup |Φ(x + an ) − Φ(x)| + sup |Φ(

1 sup |Φ(x + an ) − Φ(x)| ≤ √ |an | x 2π

(1)

and

σ ¯n 1 σ σn ¯2 x) − Φ(x)| ≤ √ | n2 − 1| . σ σ σ ¯n x 2πe n n Estimating the values an and dn , we see that sup |Φ(

|an | ≤ σ¯n−1

n


E|gj |I(|gj | > σn ) + (2m + 1)¯ σn−1

dn ≤ σn−1

n


E|gj |I(|gj | > σn ) + (2m + 1)σn−1

n 

(3)

m



E|gIc |I(|gIc | > σn ).

(4)

c=2 Iˇc

j=1

Denote h := (

E|gIc |I(|gIc | > σn )

c=2 Iˇc

j=1

and

m



(2)

E|zj |3 )−1 . Without loss of generality, we may assume that h > 2m+3 . By the Esseen

j=1

inequality,

 2 2 h |Eeit(sn+vn +wn ) − e−t /2 |t−1 dt sup |P (sn + vn + wn < x) − Φ(x)| ≤ π x 0  h  2m+3 2 24 2 2 + √ h−1 ≤ |Eeitsn − e−t /2 |t−1 dt |Eeit(sn+vn +wn ) − Eeitsn |t−1 dt π π π 2π 0 0  2 h 24 24 + |Eeit(sn+vn +wn ) − Eeitsn |t−1 dt + √ h−1 = ε1 + ε2 + ε3 + √ h−1 . π 2m+3 π 2π π 2π To estimate ε1 , we use [6, Chapter XVI.5, Theorem 2] with T = h−1 instead of T = 8h−1 /9 as follows: ε1 ≤ π −1 σ ¯n−3

n
j=1

E|gjn +

m


hcjn |3 ≤≤ 16π −1 σ ¯n−3

c=2

+32π −1 (m − 1)2 m¯ σn−3 σn2

n


E|gjn |3

j=1 m



E|gIc |I(|gIc | > σn ).

c=2 Iˇc

The term containing h−1 can be estimated similarly. 2525

(k)

(k)

Proposition 1. Let γ1 , . . . , γn , k = 1, . . . , c, be a series of sequences consisting of independent identically (1) (c) distributed random variables such that γi1 , . . . , γic are independent for i1 = · · · = ic and, in addition, do not depend on X1 , . . . , Xn . Then E|




(1)

(c)

γi1 . . . γic gIc n |p ≤ 2(2−p)c

Iˇc

c 

(s)

E|γ1 |p

s=1




E|gIcn |p ,

1 ≤ p ≤ 2.

Iˇc

To prove this proposition, we need the following statement. Proposition 2. For any x ∈ R, the following inequalities hold: (1) |eix − 1| ≤ |x|; (2) |eix − 1| ≤ |x|p−1, 1 ≤ p ≤ 2; (3) |eix − 1 − ix| ≤ 2|x|p, 1 ≤ p ≤ 2; (4) a · b ≤ p−1 ap + q −1 bq , a > 0, b > 0, p−1 + q −1 = 1. Estimation of ε2 . We need the following lemma. Lemma 1. If 0 ≤ t ≤ h and 1 ≤ i1 < · · · < ic ≤ n for c = 1, . . . , m, then n 

|E exp(itzk )| ≤ exp(−t2 (1/3 − c2−(2m+9)/3))).

k=1,k=Ic

Proof. Expanding exp(itzk ) into the Taylor series, we see that 1 1 1 1 |E exp(itzk )| ≤ 1 − Ezk2 t2 + |t|3E|zk |3 ≤ 1 − t2 (Ezk2 − hE|zk |3 ) 2 6 2 3   1 1 ≤ exp − t2 (Ezk2 − hE|zk |3 ) , 2 3 where the last inequality follows from the inequality 1 − x ≤ e−x , which holds for all x ∈ R. Thus,   n 

1 1 |E exp(itzk )| ≤ exp − t2 ( Ezk2 − h E|zk |3 ) 2 3 k=1, k=Ic

k=Ic

k=Ic

  1 2 1 1 = exp − t2 ( − Ezi21 − · · · − Ezi2c + hE|zi1 |3 + · · · + hE|zic |3 ) . 2 3 3 3 In addition, E|zi |3 ≥ 0 and Ezi2 ≤ (E|zi |3 )2/3 ≤ h−2/3 ≤ 2−2(m+3)/3 . This proves the lemma. Consider the integrand in ε2 : Eeit(sn +vn +wn ) − Eeitsn = Eeitsn (eit(vn+wn ) − eitvn + eitvn − 1) = Eeit(sn +vn ) (eitwn − 1) + Eeitsn (eitvn − 1) = Eeit(sn+vn ) (eitwn − 1 − itwn ) + (itEeitsn wn + itEeitsn (eitvn − 1)wn + Eeitsn (eitvn − 1) = L1 + L2 + L3 + L4 . To estimate L1 , we apply the third inequality of Proposition 2 and then Proposition 1 as follows: |L1 | ≤ 2|t|pE|wn |p ≤ 2(2−p)m+1 (m − 1)p−1 σ¯n−p |t|p

m



E|gIcn |p ,

c=2 Iˇc

Now we estimate L2 : |L2 | ≤ σ ¯n−1 |t|

m

c=2 Iˇc

2526

|E exp(it


k=Ic

zk )eitzi1 . . . eitzic gIc n |

1 ≤ p ≤ 2.

=σ ¯n−1 |t|

m



|E exp(it

c=2 Iˇc




zk )| · |E(eitˆzi1 − 1) . . . (eitˆzic − 1)gIc n |.

k=Ic

The last inequality holds since the gIc n are degenerate. By Lemma 1, ¯n−1 |t|m+1 exp(−t2 (1/3 − m2−(2m+9)/3 )) |L2 | ≤ σ

m



E|ˆ zi1 . . . zˆic gIc n |.

c=2 Iˇc

Now we pass to L3 . The H¨older inequality with 1 ≤ p ≤ 2 and q = p/(p − 1) implies that |L3 | ≤ |t|(E|eitvn − 1|q )1/q (E|wn |p)1/p . By Propositions 1 and 2, 2 1 |t|E|vn| + |t|p E|wn|p q p m
m


2 m 1 (2−p)m −1 p−1 p −p ≤ 3 |t|¯ σn E|gIc |I(|gIc | > σn ) + 2 (m − 1) |t| σ ¯n E|gIc n |p . q p c=3 ˇ c=2 ˇ |L3 | ≤ 21/q |t|1+1/q (E|vn |)1/q (E|wn |p )1/p ≤

Ic

Ic

Finally, |L4 | ≤ |t|E|vn | ≤ σ¯n−1 |t|

m−1


m



E|gIc Jd n | ≤ 3m σ ¯n−1 |t|

d=2 c=d+1 Jˇd

m



E|gIc |I(|gIc | > σn ).

c=3 Iˇc

Estimation of ε3 . Decompose the integrand as follows: Eeit(sn +vn +wn ) − Eeitsn = (Eeit(sn +wn ) − Eeitsn ) + (Eeit(sn +vn +wn ) − Eeit(sn+wn ) ) = I1 + I2 . We use a randomization method (see, e.g., [1,2]). Fix t ∈ [2m+3 , h] and consider a sequence of mutually independent and independent of X1 , . . . , Xn random variables α1 , . . . , αn with the Bernoulli distribution and such that P (αj = 1) = 1 − P (αj = 0) = f(t) = 9 · 2m−1 t−2 log(t), j = 1, . . . , n. Note that f(t) ∈ [0, 1] for all t. The random variables Xj , j = 1, . . . , n, can be represented in the following form: d

¯ j + (1 − αj )X ˜j , Xj = αj X

j = 1, . . . .n,

¯j and X ˜j are independent copies of Xj for all j = 1, . . . , n. In this case, where X d

sn =

n


αj z¯j +

j=1

n
(2) ˜ ¯ (1 − αj )˜ zj = s(1) n (X) + sn (X). j=1

Since the functions gIc n are additive and homogeneous, wn = σ ¯n−1 d

c m



Wck =

c=2 k=0

where ¯ ck = σ W ¯n−1







k 

αls

ˇ k Iˇc ,I c =Lk s=1 L k k

and d

vn =

m−1


m
d


V¯cdk = σ ¯n−1







k 

ˇ k Jˇd ,J d =Lk s=1 L k k

Note that Wck consists of

¯ ck , W

c=2 k=0 c 

¯ Lk , X ˜ I \L ), (1 − αis )gIc n (X c k

(6)

s=k+1

V¯cdk = σ¯n−1

d=2 c=d+1 k=0

where

c m



m−1


m
d


Vcdk ,

d=2 c=d+1 k=0

αls

d 

¯ Lk , X ˜ J \L ). (1 − αjs )gIc Jd n (X d k

s=k+1

    c d summands and Vcdk consists of summands. k k 2527

Lemma 2. Denote the sequence α1 , . . . , αn by α. Then E|E[eitsn |α]|2 ≤ t−3·2 (1)




E|E[exp(it

m−1

,

(2)

E|E[eitsn |α]|2 ≤ t3·2

αk zk )|α]|2 ≤ t−3·2

m/3−1

m−1

e−t

(22m/3 −3c/4)

2

/3

,

,

k=Ic

and E|E[exp(it




(1 − αk )zk )|α]|2 ≤ t3·2

m/3−1

(22m/3 −3c/4)

exp(−t2 (1/3 − c2−2(m+3)/3 )).

k=Ic

˘ n such that the X ˘ j are independent copies of Xj for ˘1 , . . . , X Proof. Consider a sequence of random variables X ˘ all j = 1, . . . , n. Then z¯j , z˜j , and zj (Xj ) = z˘j are independent and identically distributed for all j = 1, . . . , n. It follows that n n

E|E[exp(it αj z¯j )|α]|2 = EE[exp(it αj (¯ zj − z˘j ))|α] j=1

= E(exp(it

n


j=1

αj (¯ zj − z˘j ))) =

j=1

n 

E exp(itαj (¯ zj − z˘j )).

j=1

Expand exp(itαj (¯ zj − z˘j )) into the Taylor series: 1 1 zj − z˘j ))| ≤ 1 − t2 E(αj (¯ zj − z˘j ))2 + |t|3 E(αj |¯ zj − z˘j |)3 . |E exp(itαj (¯ 2 6 Using the inequality E|¯ zj − z˘j |3 ≤ 4E|zj |3 , we see that 2 2 zj − z˘j ))| ≤ 1 − t2 f(t)(Ezj2 − hE|zj |3 ) ≤ exp(−t2 f(t)(Ezj2 − hE|zj |3 )). |E exp(itαj (¯ 3 3 Hence, n n
(1) m−1 2
E|E[eitsn |α]|2 ≤ exp(−t2 f(t)( Ezj2 − h E|zj |3 )) = exp(−3 · 2m−1 t2 t−2 log(t)) = t−3·2 . 3 j=1

j=1

This proves the first inequality of the lemma. We proceed similarly to prove the second inequality: (2) m−1 2 1 E|E[eitsn |α]|2 ≤ exp(−t2 (1 − f(t)) ) = t3·2 e−t /3 . 3

The last two inequalities are obtained similarly to Lemma 1: E|E[exp(it


k=Ic

c c 1
2 2
αk zk )|α]|2 ≤ exp(−t2 f(t)( − Ezis + h E|zis |3 )) 3 s=1 3 s=1

m/3−1 1 (22m/3 −3c/4) ≤ exp(−t2 f(t)( − c2−2(m+3)/3 )) = t−3·2 . 3 The proof of Lemma 2 is completed.

Decompose I1 as follows: (2) I1 = E exp(it(s(1) n + sn +

c m



(2) ¯ ck )) − E exp(it(s(1) W n + sn ))

c=2 k=0

(2) = E exp(it(s(1) n + sn +

m
c=2

2528

¯ cc )) − E exp(it(s(1) + s(2) )) W n n

(2) +E exp(it(s(1) n + sn +

m m

(2) ¯ cc )) ¯ cc + W ¯ c0 ))) − E exp(it(s(1) W (W + s + n n c=2

(2) +E exp(it(s(1) n + sn +

c m



c=2

¯ ck )) − E exp(it(s(1) + s(2) + W n n

c=2 k=0

m


¯ cc + W ¯ c0 ))) = I11 + I12 + I13 . (W

c=2

Now we transform the first summand: (2) I11 = E exp(it(s(1) n + sn ))(exp(it

m


¯ cc ) − 1 − it W

c=2

(2) +itE exp(it(s(1) n + sn ))

m


m


¯ cc ) W

c=2

¯ cc = I111 + I112 . W

c=2

For a fixed α, the random variable inequality

(2) sn

(1)

does not depend on sn m


|I111| ≤ 2|t|p(m − 1)p−1

and Wcc . Hence, Proposition 2 implies the

(2)

¯ cc|p |α]|. E|E[eitsn |α] · E[|W

c=2

Using the H¨ older inequality, Proposition 1 and Lemma 2, we see that |I111 | ≤ Am σ ¯n−p |t|p

m
c
 (2) (E|E[eitsn |α]|2)1/2 ( E|αis |2p)1/2 E|gIc n |p c=2 Iˇc

≤ Am σ¯n−p |t|p+3·2

m−2

s=1

e−t

2

/6

f(t)

m



E|gIc n |p ,

1 ≤ p ≤ 2.

c=2 Iˇc

Now we estimate I112 : σn−1 |I112| ≤ |t|¯

m






(2)

E|E[eitsn |α] · E[exp(it

c=2 Iˇc

αk z¯k )|α]

c 

αis E[

s=1

k=Ic

c 

eitαis z¯is gIc n |α]|.

s=1

Similarly to the case of L2 , we get the estimate |I112| ≤

|t|¯ σn−1

m



its(2) n

E|E[e

|α] · E[exp(it

c=2 Iˇc




αk z¯k )|α]

c 

α is

s=1

k=Ic

×E[(eitαi1 zˆi1 − 1) · . . . · (eitαic zˆic − 1)gIc n |α]|. By the H¨older inequality, Proposition 2, and Lemma 2, ¯n−1 |I112 | ≤ |t|m+1 σ

m

(2) (E|E[eitsn |α]|2)1/2 c=2 Iˇc

(E|E[exp(it




αk zk )|α]|2)1/2 (

Eα4is )1/2 × E|ˆ zi1 · . . . · zˆic gIc n |

s=1

k=Ic

≤ Am σ ¯n−1 |t|3m/4(1+3·2

c 

m/3−1

)+1 −t2 /6

e

logm/2 (t)

m



E|ˆ zi1 · . . . · zˆic gIc n |.

c=2 Iˇc

We decompose I12 as follows: (2) I12 = E exp(it(s(1) n + sn ))(exp(it

m
c=2

¯ cc ) − 1)(exp(it W

m


¯ c0 ) − 1) W

c=2

2529

m m

(2) ¯ ¯ c0 ) W W +E exp(it(s(1) + s ))(exp(it( )) − 1 − it c0 n n c=2 (2) +itE exp(it(s(1) n + sn ))

m


c=2

¯ c0 = I121 + I122 + I123 . W

c=2

The H¨older inequality with 1 ≤ p ≤ 2 and q = p/(p − 1) and Propositions 1 and 2 imply that |I121 | ≤ (E| exp(it

m


¯ cc ) − 1|p)1/p (E| exp(it W

c=2

m


¯ c0 ) − 1|q )1/q W

c=2

m m

¯ cc|p )1/p ( ¯ c0 |p )1/q ≤ 21/q |t|1+p/q (m − 1)p−1 ( E|W E|W c=2

≤ Am |t|pf(t)2/p σ ¯n−p

c=2

m



E|gIc n |p ,

1 ≤ p < 2.

c=2 Iˇc (1)

(2)

For a fixed α, sn does not depend on Wc0 and sn . The same reasoning as in the case of I111 shows that |I122 | ≤ Am σ¯n−p |t|p−3·2

m−2

m



E|gIcn |p ,

1 ≤ p ≤ 2.

c=2 Iˇc

We estimate I123 similarly to I112 : σn−1 I123 ≤ |t|¯

m



(1)

E|E[eitsn |α] · E[exp(it

c=2 Iˇc c 




(1 − αk )zk |α]

k=Ic

(1 − αis ) × E[(eit(1−αi1 )ˆzi1 − 1) · . . . · (eit(1−αic )ˆzic − 1)gIc n |α]|

s=1

≤ |t|1−9m2

m/3−4

e−t

2

(1/6−m2−2m/3−3 ) −1 σ ¯n

m



E|ˆ zi1 · . . . · zˆic gIc n |.

c=2 Iˇc

For I13 , we use the following representation: (2) I13 = E exp(it(s(1) n + sn +

m


¯ c0 ))(exp(it W

c=2

(exp(it

c−1 m



c−1 m



¯ ck ) − 1 − it W

m


c=2 m


¯ c0 )) W

c=2

c=2 k=1

+

¯ cc ) − 1) W

(2) ¯ ck ) − 1) + E exp(it(s(1) W n + sn +

c=2 k=1

(exp(it

m


c−1 m



¯ ck ) + itE exp(it(s(1) + s(2) W n n

c=2 k=1

¯ c0 )) W

c=2

c−1 m



¯ ck = I131 + I132 + I133 , W

c=2 k=1

where the values I131 and I132 can be estimated as above. (s) (s) To estimate I133 , we need a series of randomizations. Let η1 , . . . , ηn , s = 1, . . . , m − 1, be a series of independent identically distributed random variables that are independent of α and of X1 , . . . , Xn and have the Bernoulli distributions (s)

P (ηj 2530

(s)

= 1) = 1 − P (ηj

= 0) = 1/2,

j = 1, . . . , n, s = 1, . . . , m − 1.

¯ j can be represented in the following way: We denote this series by η. In this case, X d (1) (1) (1) (1) ¯j = X ηj Yj + (1 − ηj )Y¯j , (1)

where Yj

(1) ¯j for all j = 1, . . . , n. Further, and Y¯j are independent copies of X (1) d

Yj

(2)

(2)

(2)

(2)

+ (1 − ηj )Y¯j ,

= ηj Yj

... (m−1) d

Yj (s+1)

where Yj

(m)

= ηj

(m)

(m)

+ (1 − ηj

Yj

(m)

)Y¯j

,

(s+1) (s) and Y¯j are independent copies of Yj for s = 2, . . . , m − 1. In this case,

d

(1)

(2)

(1) ¯ ) + sn1 (Y¯ (1) ) = s(1) n (X) = sn1 (Y

n


(1)

(1)

ηj αj zj (Yj ) +

n
(1) (1) (1 − ηj )αj zj (Y¯j ).

j=1

j=1

For s = 1, . . . , m − 1, (1)

(2)

(1)

(2)

(s+1) ) + sns+1 (Y¯ (s+1) ). s(1) ns = sns+1 + sns+1 = sns+1 (Y

Set (1)

(2)

sn0 := s(1) n

and sn0 := s(2) n .

The equalities (2) d

(1)

sn0 + sn0 =

k


(1) d

s(2) nr + snk =

r=0

s


(1)

s(2) nr + snk ,

s = 1, . . . , k,

r=0

hold, where (1) snk (Y¯ (k) ) =

k n 


(s)

(k)

ηl αl zl (Yl

)

l=1 s=1

and ¯ (r) ) = s(2) nr (Y

n r−1


(s)

(r)

(r)

ηl (1 − ηl )αl zl (Y¯l

).

l=1 s=1

Therefore, d ¯ ck = W

k






c 

ˇ k ,Lk ∈Ic s=k+1 b1 =0 Iˇc L

×

b1 

ηr(1) s

s=1

k 

1


1

b1 

αls

ˇ b ,Rb ∈Lk s=1 R 1 1

(1) (1) (1) ˜I \L ) (1 − ηls )gIc nRb1 (YRb , Y¯Lk \Rb , X c k




ˇb L ˇ k ,Lk =Rb Iˇc ,I c =Lk b1 =0 R 1 b b 1 k k b

×

k 

1

s=b1 +1

k



d

=




(1 − αis )

ηr(1) s

s=1

1

k 

1

c 

(1 − αis )

k 

αls

s=1

Rb1 s=k+1

(1) (1) (1) ˜ I \L ). (1 − ηls )gIc nRb1 (YRb , Y¯Lk\Rb , X c k 1

1

s=b1 +1

¯ ck into summands of three types: We decompose W d ¯ ck = W

k


¯ ckb1 = W ¯ ck0 (Y¯ (1), X ˜I \L ) + W ¯ ckk (Y (1), X ˜I \L ) W c k c k Lk Lk

b1 =0

2531

+

k−1


¯ ckb (Y (1) , Y¯ (1) ˜ W 1 Rb Lk \Rb , XIc \Lk ). 1

1

b1 =1

Further, k−1


k−1


d ¯ ckb = W 1

d

k−1


¯ ckB b (Y (2) , Y¯ (2) ¯ (1) ˜ W 1 2 Rb Rb \Rb , YLk \Rb , XIc \Lk ) 2

b1 =1

=

b1


k−1 1 −1
b


k−1 1 −1
b


¯ ckB b + W ¯ ckB 0 ) + (W 1 1 1

b1 =1

+




¯ ckBk−1 bk−1 + W ¯ ckBk−1 0 ) = (W

where




WckBj bj =


j

 b j−1

i=1

¯ ckB b + W ¯ ckB 0 ) + . . . (W 2 2 2

k−1





¯ ckBj bj + W ¯ ckBj 0 ), (W

j−1 

(




··· 2

j

2

k 

ηr(i) (1 − ηr(j) )) · · · s s

s=bj +1 i=1





ˇ k Iˇc ˇ b1 ,Rb1 =( Rbs−1 ) L R b1 k b b bs

ˇ b ˇ bj−1 bj−1 R ,Rb =Rbj j Rb

ηr(i) s

1

j=1 1≤bj <···
bk−1 =1

bj  j+1  

2

b1 =1 b2 =1

bk−2

···

b1 =1 b2 =1

s=1

1

b1 =1 b2 =0

(1)

(1 − ηls )

(j+1) j

(j)

, Y¯Rb

j−1

αls

s=1

s=b1 +1

×gIc nRbj (YRb

k 

c 

(1 − αis )

s=k+1

¯ (1) ˜ \Rbj , . . . , YLk \Rb1 , XIc \Lk )

for j > 0. Thus, I133 = it

c−1 k−1 m







c=2 k=1 j=0 1≤bj <···
d=2

¯ ckBj bj + W ¯ ckBj 0 means W ¯ ck0 + W ¯ ckk . Note that the WckBj bj does not depend on where for j = 0, the sum W (2) (1) (j+1) (j+1) snj+1 (Y¯ ) and the WckBj 0 does not depend on snj+1 (Y ) for fixed α and η. The values J1 and J2 are estimated similarly; we consider J1 only: J1 = it

c−1 k−1 m







 
 j+1 m
(1) ¯ d0 ) − 1)W ¯ ckB b ] W E[exp it s(2) + s (exp(it j j nr nj+1

c=2 k=1 j=0 1≤bj <···
+it

c−1 k−1 m




r=0

d=2

 
 j+1 (1) (2) ¯ ckB b ] = J11 + J12 . E[exp it snr + snj+1 W j j




c=2 k=1 j=0 1≤bj <···
r=0

To estimate J11 , we select the independent part and take into account that the gIc nRbj are degenerate: |J11| ≤ |t|

c−1 k−1 m










c=2 k=1 j=0 1≤bj <···
j

E|

bj  j+1   s=1

j+1  s=1

2532

i=1

···


ˇk L b

 k  (2) ηr(i) · · · αls × E[eitsnj+1 |α, η]E[exp(it s s=1

ηa(s) αa za (Y (j+1) ))|α, η] × E[

 b a= Rbs−1 s

(exp(it

j+1  s=1

1


b a= Rbs−1 s

ηa(s) αa za (Y (j+1))) − 1)

(exp(it

m


¯ d0 ) − 1) W

c


(1 − αis )gIc nRbj |α, η]|.

Iˇkc s=k+1

d=2

We use the H¨older inequality with 1 ≤ p ≤ 2 and q = p/(p − 1) and Propositions 1 and 2 to show that the last mathematical expectation does not exceed

(



E[| exp(it

b a= Rbs−1 s

j+1 

m


ηa(s) αaza ) − 1|q |α, η] · E[| exp(it

s=1

×(2

¯ d0 ) − 1|q |α, η])1/q W

d=2

(2−p)(c−k)

c


(1 − αis )p E[|gIcnRbj |p |α, η])1/p

Iˇkc s=k+1



≤ Am |t|k+p−1 σ ¯n−1 (

b a= Rbs−1 s

αqa

j+1 

(ηa(s) )q E|za |q )1/q

s=1

m


˜Ic )|p )1/q (2(2−p)(c−k) ×( 2(2−p)c E|gIcn (X E|gIc nRbj |p )1/p . c=2

Iˇc

Iˇkc

Since q ≥ 2, E|za |q = Eza2 |za |q−2 ≤ mq−2 2q−3 (σn /¯ σn )q−2 Eza2 . Therefore, the H¨ older inequality for sums implies that σn )(q−2)/q σ ¯n−p × |J11 | ≤ Am (σn /¯ ×

c−1 m



|t|k+p

c=2 k=1

k−1







b a= Rbs−1 s

Eza2


ˇk L b




j+1 

j

s=1

×(

···

ˇb j=0 1≤bj <···
bj j+1 k    (2) (i) 2 E| ( ηrs ) · · · α2ls × E[eitsnj+1 |α, η]E[exp(it s=1 i=1




m



1

b s=1 a= Rbs−1 s

ηa(s) αa za (Y (j+1) ))|α, η]


E|gIc n |p)1/q ( E|gIc nRbj |p )1/p

c=2 Iˇc

Iˇkc

≤ Am |t|p−1.06 log(m−1)/2 (t)(σn /¯ σn )1/p−1 σ¯n−p c−1 k−1 m


×(




m



E|gIc n |p )1/q

c=2 k=1 j=0 1≤bj <···






E|gIcn |p )1/p,

1≤bj <···
where we have applied the inequality


c 

1≤i1=···=ic ≤n s=1

n
Ezi2s ≤ ( Ezi2 )c = 1. i=1

It follows that |J11 | ≤ Am (σn /¯ σn )1/p−1 σ ¯n−p |t|p−1.06 log(m−1)/2 (t)

m



E|gIcn |p .

c=2 Iˇc

2533

We pass to J12 (denote b0 := k). Since the gIc nRbj are degenerate, |J12| ≤ |t|¯ σn−1

c−1 k−1 m










···

c=2 k=1 j=0 1≤bj <···
Iˇkc

j

E|




bj j+1 k c     (2) ( ηr(i) ) · · · α × (1 − αis )E[eitsnj+1 |α, η] l s s s=1 i=1 j 

s=1

E[exp(it

d=1

s=k+1




d−1 

b

s=1

a=Rbd−1

ηa(s) (1 − ηa(d) )αa za )|α, η]

d




×E[exp(it

(1 − αa )za )|α, η] × E[exp(it

a=Ikc bd−1 j  

(exp(it

d−1 

ηa(s)αa za )|α, η]

a=1 s=1

ηr(a) (1 s

−

− 1) ×

ηr(d) )αrs zˆrs ) s

a=1

d=1 s=bd +1

n j+1


bj 

(exp(it

s=1 c 

j+1 

ηr(a) αrs zˆrs ) − 1) s

a=1

(exp(it(1 − αis )ˆ zis ) − 1)gIc nRbj |.

s=k+1

Using the same methods as above, we obtain the estimate |J12 | ≤ Am |t|m+3·2

m−2

−9·2m/3−4 −3/2

ׯ σn−1

exp(−t2 (1/6 − (m − 1)2−2m/3−3 )) log1/2 (t)

m



E|ˆ zi1 . . . zˆic gIc n |.

c=2 Iˇc

It remains to estimate I2 . We represent (2) I2 = E exp(it(s(1) n + sn +

c m



¯ ck + W

c=2 k=0

(2) −E exp(it(s(1) n + sn +

c m



m−1


m
d


V¯cdk ))

d=2 c=d+1 k=0

(2) ¯ ck )) = E exp(it(s(1) W n + sn +

c=2 k=0

(exp(it

c m



¯ ck ) − 1 − it W

c=2 k=1

¯ ck ) × (exp(it W

c=2 k=1 m


m−1


m


m


m


c m



V¯cd0 ) − 1)

V¯cd0 ) − 1)

¯ c0 ) − 1) W

c=2

(2) V¯cd0 ) − 1) + E exp(it(s(1) n + sn ))(exp(it

c=2 k=0

2534

m−1


¯ ck + E exp(it(s(1) + s(2) ))(exp(it W n n

d=2 c=d+1 (2) +E exp(it(s(1) n + sn +

m


d=2 c=d+1

c=2 k=1

(exp(it

m−1


d=2 c=d+1

¯ c0 ))(exp(it W

c=2 c m



¯ c0 )) W

c=2

c m



(2) +itE exp(it(s(1) n + sn +

m


m−1


m


V¯cd0 ) − 1)

d=2 c=d+1

¯ ck + W

m−1


m


d=2 c=d+1

(2) V¯cd0 )) − E exp(it(s(1) n + sn +

c m

c=2 k=0

¯ ck )) W

and use the same reasoning as above. In particular, the second summand does not exceed (q−2)/2

Am (σn /¯ σn )

|t|

2+1/q

c
m

c=2 k=1 L ˇk

(E|E[exp(it




αj zj )|α]|2)1/2 f(t)k × (¯ σn−1

m−1





Ezl2s )1/q (¯ σn−p

E|gIc Jd n |

d=2 c=d+1 Jˇd

j=Lk k 

m



E|gIc n |p )1/p ≤ Am (σn /¯ σn )2/p−1 |t|1+9m·2

m/3−4

−1/p−3·2m−2

Iˇkc ,Ikc =Lk

s=1

× log(t) × σ¯n−1

m−1


m



E|gIc Jd n |)1/q (¯ σn−p




d=2 c=d+1 Jˇd

E|gIc n |p)1/p , 1 ≤ p ≤ 2, q = p/(p − 1).

Iˇc

To complete the proof, we need the following two lemmas. Lemma 3. The estimates

2

n m




σ

¯n − 1 ≤ 2σ−2 Egj2 I(|gj | > σn ) + 2m(m + 4)σn−1 E|gIc |I(|gIc | > σn ) n

σ2

n c=2 ˇ j=1

Ic

and σ ¯n2 ≥ 0.5 · σn2 hold. Proof. By definition, σ ¯n2 =

n


E(gjn +

n
j=1

≤ 2σn m

hcjn )2 =

c=2

j=1

where

m


m n



n


2 Egjn +

j=1

n
j=1

m m n


E( hcjn )2 + 2 E(gjn hcjn ), c=2

m m n
n


E( hcjn)2 = Eh2cjn + c=2




Ehc1 jn hc2 jn

j=1 2≤c1=c2 ≤m

j=1 c=2




E|gIc−1 ,j |I(|gIc−1 ,j | > σn ) ≤ 2σn m

2

j=1 c=2 Iˇc−1 ,Ic−1 =j n


E(gjn

n


2 Egjn =

j=1

n


hcjn) ≤ 2σn

j=1

E(gjn )2 −

m



E|gIc |I(|gIc | > σn ),

c=2 Iˇc

c=2

j=1

and

m


c=2

j=1

m n



Ehcjn ≤ 4σn m

j=1 c=2

m



E|gIc |I(|gIc | > σn ),

c=2 Iˇc

n n n


(Egjn )2 = σn2 − Egj2 I(|gj | > σn ) − (Egj I(|gj | > σn ))2 . j=1

j=1

j=1

Hence, σ ¯n2 ≥ σn2 −

n


Egj2 I(|gj | > σn ) −

j=1

m
n

(Egj I(|gj | > σn ))2 − 2m(m + 4)σn E|gIc |I(|gIc | > σn ) j=1

c=2 Iˇc

and σ ¯n2 ≤ σn2 −

n
j=1

Egj2 I(|gj | > σn ) −

m
n

(Egj I(|gj | > σn ))2 + 2m(m + 4)σn E|gIc |I(|gIc | > σn ). j=1

c=2 Iˇc

This proves the first inequality of the lemma. Since ∆n ≤ 1, we may assume that the right-hand side of the first inequality is less than 0.5; in this case, σ ¯n2 ≥ 0.5 · σn2 . 2535

Lemma 4. The inequality σn−1

m



m

E|ˆ zi1 · . . . · zˆic gIc n | ≤ Am ( σn−c−1 E|gin1 · . . . · ginc gInc |

c=2 Iˇc

+σn−2

Iˇc

c=2

m



EgI2c I(|gIc | ≤ σn ) +

c=2 Iˇc

m m


(σn−1 E|gIr |I(|gIr | > σn ))c ) c=1

r=2 Iˇr

holds. Proof. By definition, ¯n−c E| E|ˆ zi1 · . . . · zˆic gIc n | = σ

c 

(gins +

s=1

≤ σ¯n−c E|gin1 · . . . · ginc gInc | + +¯ σn−c

c


m


hnris )gInc |

r=2




E|

d=1 1≤j1<···<jd ≤c

d
m c−d   ( hnrijs ) ginks gInc |, s=1 r=2

s=1

m where ks ∈ {1, . . . , c}\{Jd}. Using the H¨ older inequality and estimating E( r=2 hnrijs )2 as in Lemma 3, we see that the second summand does not exceed σ¯n−c



2(m − 1)

c





(

d 

σn

d=1 1≤j1<···<jd ≤c s=1

E|gLr−1ijs |I(|gLr−1 ijs | > σn ) ×

c−d 

m





r=2 Lr−1 =ijs

E(ginks )2 )1/2 (E(gInc )2 )1/2 .

s=1

Applying the H¨ older inequality for sums and taking into account that


c−d 

E(ginks )2 ≤ σn2(c−d) ,

1≤ik1 <···
we complete the proof of the lemma. Combining formulas (1)–(4), estimates of ε1 , ε2 , and ε3 and the relations σn−1 EgI2c I(|gIc | ≤ σn ) = σn−p E|gIc |p I(|gIc | ≤ σn ) and

σn−1 E|gj |I(|gj | > σn ) = σn−2 Egj2 I(|gj | > σn ),

we obtain the statement of Theorem 1. Proof of Theorem 2. Consider the value σn−c−1



c 

Iˇc

E|gin1 · . . . · ginc gInc |. Since

|gins |1−2/c ≤ σnc−2 ,

s=1

σn−c−1




E|gin1 · . . . · ginc gInc | ≤ σn−3

Iˇc


Iˇc

E(

c 

|gins |2/c · |gInc |).

s=1

This proves Theorem 2. Proof of the Corollary. Using the fourth inequality of Proposition 2 with p = δc = the inequality σn−3


Iˇc

2536

E|

c  s=1

2c+1 2c−1

and q =


 2c+1 2c − 1 −δc
2 σn E|gInc |δc + σn−2c−1 E|gins | c . 2c + 1 2c + 1 ˇ ˇ s=1 c

|gins |2/c · |gInc | ≤

2c+1 2 ,

Ic

Ic

we obtain

Thus, the second summand is estimated as follows: n
2 − 2c+1 E{|gin |3/c|gin |2(c−1)/c})c (σn 2 2c + 1 i=1

≤

n n n

c−1
2 2 1 − 2c+1 E(gin )2 ) c ( E|gin |3 ) c )c ≤ E|gin |3 . (σn 2 ( σn−3 2c + 1 2c + 1 i=1 i=1 i=1

This proves the corollary. This research was supported by the Program “Leading Scientific Schools” (project 2258-2003-1). Translated by V. Sudakov. REFERENCES 1. I. B. Alberink, “A Berry-Esseen bound for U -statistics in non-i.i.d. case,” Preprint 98-057 SBF 343, Universit¨ at Bielefeld (1998), 1–12. 2. V. Bentkus, M. Bloznelis, and F. G¨ otze, “A Berry-Esseen bound for Student’s statistics in non-I.I.D. case,” J. Theor. Probab., 9, 765–796 (1996). 3. V. Bentkus, F. G¨ otze, and R. Zitikis, “Lower estimates of the convergence rate for U -statistics,” Ann. Probab., 22, 1707–1714 (1994). 4. Yu. V. Borovskikh, “Normal approximation of U -statistics,” Teor. Veroyatn. Primen., 45, 469–488 (2000). 5. Yu. V. Borovskikh and V. S. Korolyuk, Theory of U -Statistics [in Russian], Kiev (1989). 6. Yu. V. Borovskikh and V. S. Korolyuk, “Martingale approximation,” in: VSP, Utreht (1997), pp. 196–230. 7. W. Feller, An Introduction to Probability Theory and Its Applications [Russian translation], Moscow (1984). 8. K. O. Friedrich, “A Berry-Esseen bound for functions of independent random variables,” Ann. Statist., 17, 170–183 (1989). 9. M. Ghosh and R. Dasgupta, “Berry-Esseen theorem for U -statistics in the non-i.i.d. case,” in: Colloquia mathem. soc. J´ anos Bolyai, 32 (1982), pp. 293–313. 10. W. Hoeffding, “A class of statistics with asymptotically normal distribution,” Ann. Math. Statist., 19, 293–325 (1948). 11. Sh. A. Khashimov and G. R. Abdurakhmanov, “Estimate of rate of convergence in the central limit theorem for generalized U -statistics,” Teor. Veroyatn. Primen., 43, 61–82 (1998). 12. T. L. Malevich and G. R. Abdurakhmanov, “Central limit theorem for generalized (inhomogeneous) U statistics of differently distributed random values,” Izv. Akad. Nauk Uzb. SSR, Ser. Mat., 2, 28–33 (1986).

2537