Large Deviations of U-Statistics

Yuri V. Borovskikh

Transport University

St Petersburg

Neville C. Weber

University of Sydney

Sydney

12 January, 2001

Large deviation results with explicit order terms and Cramér’s series are developed for non-degenerate U-statistics of degree m under Cramér type conditions on the kernel. The method of the proof is based on the contraction technique of Keener, Robinson and Weber (1998), which is the natural generalization of the classical method of Cramér (1938). Other techniques used in the proofs include truncation, decoupling inequalities, Borell’s inequality for Rademacher chaos and a partitioning method to bound the degenerate remainder term.

1 Introduction and Results.

Let X, X_{1}, …, X_{n} be independent and identically distributed random variables with the distribution F taking values in the measurable space (X, X). Consider a U-statistic U_{n} = U_{n}(X_{1}, …, X_{n}) of the form

U_{n} = \frac{(m − 1) ⋯ 2 · 1}{(n − 1) ⋯ (n − m + 1)} ∑_{1≤i_{1}<···<i_{m}≤n}h(X_{i_{1}}, …, X_{i_{m}})

where the kernel h : X^{m} → R is an integrable, symmetric function. According to the Hoeffding representation

U_{n} = S_{n} − \frac{n(m − 1)}{m}μ + v_{n},

AMS 1991 subject classification. Primary 60F10. Key words and phrases. Large deviations, U-statistics, Cramér’s series, decoupling inequalities.

where

μ = Eh(X_{1}, …, X_{m}), S_{n} = ∑_{i=1}^{n} g(X_{i}),

g(x) = E(h(X_{1}, …, X_{m−1}, X_{m})|X_{m} = x), and

v_{n} = \frac{m − 1}{n − 1} ∑_{1≤i_{1}<i_{2}≤n} g_{2}(X_{i_{1}}, X_{i_{2}}) + ⋯

+\frac{(m − 1) ⋯ 2 · 1}{(n − 1) ⋯ (n − m + 1)} ∑_{1≤i_{1}<···<i_{m}≤n} g_{m}(X_{i_{1}}, …, X_{i_{m}}),

where g_{c} : X^{c} → R, c = 2, …, m are canonical functions which are defined for a given kernel h by the operator formula

g_{c}(x_{1}, …, x_{c}) = (δ_{x_{1}} − F) ⋯ (δ_{x_{c}} − F)F^{m−c}h,

where Q_{1} ⋯ Q_{m}h = ∫ ⋯ ∫ h(x_{1}, …, x_{m})dQ_{1}(x_{1}) ⋯ dQ_{m}(x_{m}). The following useful representation holds:

g_{c}(x_{1}, …, x_{c}) = ∑_{d=0}^{c}(−1)^{c−d} ∑_{1≤i_{1}<···<i_{d}≤c} E h(x_{i_{1}}, …, x_{i_{d}}, X_{d+1}, …, X_{m}).

The functions g_{c} possess the degeneracy property Eg_{c}(x_{1}, …, x_{c−1}, X_{c}) = 0 a.s., c = 2, …, m.

Let σ^{2} = E(g(X)−μ)^{2}. Assume that 0 < σ^{2} < ∞ and without loss of generality, take μ = 0. By the central limit theorem for non-degenerate U-statistics,

P (U_{n}/(σ\sqrt{n}) ≤ x) → Φ(x),

uniformly in x as n → ∞, provided t^{2c/(2c−1)}P (|g_{c}(X_{1}, …, X_{c})| > t) → 0 as t → ∞ for each c = 2, …, m and Φ(x) denotes the standard normal distribution function.

We are interested in the relative error

\frac{P (U_{n}/(σ\sqrt{n}) > x)}{(1 − Φ(x))} = (1 + o(1))

as x tends to infinity together with n.

This result was proved initially for x = O((ln n)^{1/2}) under different conditions on the kernel by Ghosh(1974), Rubin and Sethuraman(1965), Slastnikov(1978), Malevich and Abdalimov(1979). For non-degenerate kernels h such that

E|h(X_{1}, …, X_{m})|^{k} ≤ C^{k}k^{γk}, k = 1, 2, …

for some constants C > 0 and γ ≥ 0 Malevich and Abdalimov(1979) have shown that Cramér type large deviations are valid when x = o(n^{1/(10+4γ)}). Vandemaele(1982) refined this theorem to obtain the result for x = o(n^{1/(6+4γ)}). If γ = 0, which corresponds to the kernel being bounded, then this result gives the natural range 0 ≤ x ≤ o(n^{1/6}). For this range results have also been obtained by Inglot, Kallenberg and Ledwina(1992), Inglot and Ledwina(1993) and Wang Qiying(1996). With γ ≥ 1 Aleshkevichene(1990) established this large deviation theorem for x = O(n^{1/(4γ+2)}) and for γ ≥ 2 Aleshkevichene(1992) proved that the error was o(1) = O((1 + x^{3} + x ln n)/\sqrt{n}) for x in the range 0 ≤ x ≤ O(n^{1/(4γ−2)}).

Keener, Robinson and Weber(1998) proposed a contraction technique for establishing Cramér type large deviation theorems for U-statistics of degree 2. Their approach is the natural generalization of the classical method of Cramér (1938). Borovskikh and Weber(2000) developed this contraction technique for U-statistics with bounded kernels to establish a Cramér type large deviation theorem with convergent Cramér series for x = o (\sqrt{n}). In this paper we extend the contraction technique to establish Cramér’s series for large deviation probabilities for U-statistics of any degree m when the kernel h satisfies Cramér’s condition or Linnik’s condition. Following Borovskikh and Weber(2000) but under Cramér type conditions we find the explicit solution of the analogue of the contraction equation in the form of a convergent power series in t with coefficients depending on x ∈ X. This enables the construction of an explicit Cramér series. Aleshkevichiene (1990) established Cramér type large deviations, including a truncated Cramér series and bounds on the rate of convergence, for U-statistics of degree 2 with bounded kernels via the cumulant method.

Borovskikh and Weber(2001) established large deviation results with Cramér’s series for U-statistics with the kernel h(x_{1}, …, x_{m}) = x_{1} ⋯ x_{m} under Cramér’s condition E exp{a|X|} < ∞, for some a > 0.

Assume E exp{t ∑_{s=1}^{m} g(X_{s})}|h(X_{1}, …, X_{m})| < ∞ and E exp{t|g(X)|} < ∞ for t ∈ [0, α], for some α > 0. Define the operator H_{t}^{m−1}, by

H_{t}^{m−1}g = \frac{E\{∏_{s=1}^{m−1} e^{tg(X_{s})}h(X_{1}, …, X_{m−1}, ·)\}}{(Ee^{tg(X)})^{m−1}}, t ∈ [0, α],

for any fixed integer m = 2, 3, ….

In what follows we will show that the equation g = H_{t}^{m−1}g has an essentially unique solution g_{t} , i.e. g_{t} = H_{t}^{m−1}g_{t}. (1)

The function g_{t} is the key to defining the Cramér series. As in Borovskikh and Weber(2000) we give the solution of (1), g_{t}(x), in the form of an analytic function in t, but here we only assume that a Cramér type condition holds. To formulate this result we need some notation which we develop in line with Borovskikh and Weber(2000). For x ∈ X and k = 1, 2, … let

c_{k}(x) = ∑_{l=0}^{k−1} a_{l}(x) b_{k−1−l}, (2)

where,

a_{0}(x) = g(x),
a_{l}(x) = ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} Eh(X_{1}, …, X_{m−1}, x) ∏_{s=1}^{l} \frac{1}{ν_{s}!} ( ∑_{j=1}^{m−1} c_{s}(X_{j}))^{ν_{s}}, l ≥ 1

and

b_{0} = 1,
b_{l} = ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} (ν_{1} + ⋯ + ν_{l})! ∏_{s=1}^{l} \frac{(−1)^{ν_{s}}}{ν_{s}!} β_{s}^{ν_{s}}, l ≥ 1,

where

β_{l} = ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} E ∏_{s=1}^{l} \frac{1}{ν_{s}!} ( ∑_{j=1}^{m−1} c_{s}(X_{j}))^{ν_{s}}, l ≥ 1.

The summation in a_{l}(x), b_{l} and β_{l} is carried out over all integer-valued vectors (ν_{1}, …, ν_{l}) such that ν_{1} + 2ν_{2} + ⋯ + lν_{l} = l, ν_{j} ≥ 0, j = 1, …, l. Thus, for example,

a_{1}(x) = (m − 1)Eh (X_{1}, …, X_{m−1}, x) c_{1} (X_{1}) ,
a_{2}(x) = (m − 1)Eh (X_{1}, …, X_{m−1}, x) c_{2} (X_{1}) +

+\frac{1}{2}(m − 1)Eh (X_{1}, …, X_{m−1}, x) c_{1}^{2} (X_{1}) +

+\binom{m − 1}{2}Eh (X_{1}, …, X_{m−1}, x) c_{1} (X_{1}) c_{1} (X_{2}) ,

and

b_{1} = −β_{1}, b_{2} = β_{1}^{2} − β_{2},

with

β_{1} = (m − 1)Ec_{1} (X) ,
β_{2} = (m − 1)Ec_{2} (X) + \frac{1}{2}(m − 1)Ec_{1}^{2} (X) + \binom{m − 1}{2} (Ec_{1}(X))^{2} .

Here, by definition, \binom{n}{k} = n (n − 1) ⋯ (n − k + 1) / k!, if n ≥ k and \binom{n}{k} = 0, if n < k. The expression on the right in (2) depends only on c_{1}(x), …, c_{k−1}(x). Hence (2) is a recurrence relation defining c_{k}(x), k = 1, 2, …. For example,

c_{1}(x) = g(x),
c_{2}(x) = (m − 1)Eh(X_{1}, …, X_{m−1}, x)g(X_{1}),
c_{3}(x) = \binom{m − 1}{2}Eh(X_{1}, …, X_{m−1}, x)g(X_{1})g(X_{2})
+(m − 1)^{2}Eh(X_{1}, …, X_{m−1}, x)h(X_{1}, X_{m} …, X_{2m−2})g(X_{m})

+\frac{1}{2}(m − 1)Eh(X_{1}, …, X_{m−1}, x)g^{2}(X_{1}) (3)

−((m − 1)^{2} + \frac{1}{2}(m − 1)) g(x)Eg^{2}(X_{1}).

In what follows we will need the notation

c(x) = (Eh^{2}(X_{1}, …, X_{m−1}, x))^{1/2} , x ∈ X
∥ c ∥ = (Ec^{2}(X))^{1/2}

and under Cramér’s condition

E exp{a | h(X_{1}, …, X_{m}) |} < ∞ (4)

for some a > 0, we denote

b = E exp{a | h(X_{1}, …, X_{m}) |} and d = (E exp{ac(X)})^{1/2} .

Note that E exp\{ac(X)\} ≤ (1 + \sqrt{2})b. (5) In fact,

E exp\{ac(X)\} = 1 + aEc(X) + ∑_{k=2}^{∞} \frac{a^{k}}{k!} Ec^{k}(X).

Since x^{2} ≤ 2e^{x}, x ≥ 0 and using Hölder’s inequality

aEc(X) ≤ (E{a^{2}h^{2}(X_{1}, …, X_{m})})^{1/2}
≤ \sqrt{2} (E exp\{a|h(X_{1}, …, X_{m})|\})^{1/2}
≤ \sqrt{2}b.

Again by Hölder’s inequality

Ec^{k}(X) ≤ E | h(X_{1}, …, X_{m}) |^{k}, k ≥ 2.

This proves (5). The inequality (5) indicates that the condition d < ∞ on the kernel h is weaker than the Cramér condition (4).

Theorem 1. Assume d < ∞. Then for all x ∈ X and k = 1, 2, …

| c_{k}(x) |≤ c(x) \frac{1}{8} (8d(1 + d))^{k} (\frac{m − 1}{a})^{k−1} (6)

and the function

g_{t}(x) = ∑_{k=1}^{∞} c_{k}(x)t^{k−1}, x ∈ X (7)

is the unique analytical solution of equation (1) in the region 0 ≤ t < a/ (8d(1 + d)(m − 1)) . Further,

| g_{t}(x) |≤ 2dc(x),

| g_{t}(x) − g(x) |≤ c(x) t \frac{m − 1}{a} (8d(d + 1))^{2} / (1 − t8d(1 + d)(m − 1)/a) , (8)

and if 0 ≤ t ≤ a/ ((m − 1)8d(1 + d)(8d(1 + d) + 1)) then

E exp\{\frac{a}{2} | g_{t}(X) | \}≤ 2b. (9)

Note that the function g_{t}(x) in (7) can be written as

g_{t}(x) = g(x) + ∑_{k=1}^{∞} c_{k+1}(x)t^{k}.

Hence, the estimate (8) is true by virtue of (6), and (9) follows from (8). Moreover, throughout we assume that m ≥ 2 since if m = 1 we have g_{t}(x) = g(x) for all t > 0.

In the following theorem we suppose that x = o(\sqrt{n}), n → ∞ and we use the iterated logarithmic function ln_{l} n = ln(ln_{l−1} n), l = 1, 2, …, setting ln_{0} n = n.

Theorem 2. Let σ^{2} = Eg^{2}(X) > 0 and assume the kernel h satisfies Cramér’s condition (4). Then for x = O(\sqrt{n}/ ln_{l} n) with any fixed integer l ≥ 1

P (U_{n} > xσ\sqrt{n}) / (1 − Φ(x)) = exp\{\frac{x^{3}}{\sqrt{n}} λ_{m} (\frac{x}{\sqrt{n}}) \}(1 + O (\frac{1 + x}{\sqrt{n}})) (10)

with Cramér series

λ_{m}(u) = ∑_{k=0}^{∞} λ_{mk}u^{k}, (11)

where

|λ_{mk}| ≤ λ^{k+3}, k = 0, 1, …

with

λ = (\frac{152md(1 + d)^{2}}{aσ} ) (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}}) .

Equation (10) is also valid in the region O(\sqrt{n}/ ln_{l} n) ≤ x ≤ o(\sqrt{n}) if the function h^{2} satisfies Cramér’s condition, i.e. E exp (a_{0}h^{2}) < ∞ for some constant a_{0} > 0.

Explicit formulae for the evaluation of the coefficients λ_{mk} for any k = 0, 1, … are given at (29). The power series in (11) is convergent for |u| < λ^{−1}.

Let 0 < α < 1/2 and s = [4α/(1 − 2α)] denote the integer part of 4α/(1 − 2α). Introduce the truncated Cramér series

λ_{m}^{[s]}(u) = λ_{m0} + λ_{m1}u + ⋯ + λ_{ms}u^{s}.

Theorem 3. Let x = o(n^{α}), n → ∞. Suppose that Linnik’s condition

E exp (a_{α}|h|^{4α/(2α+1)}) < ∞ (12)

holds for some a_{α} > 0. Then

P (U_{n} > xσ\sqrt{n}) / (1 − Φ(x)) = exp\{\frac{x^{3}}{\sqrt{n}} λ_{m}^{[s]} (\frac{x}{\sqrt{n}}) \}(1 + O (\frac{1 + x}{\sqrt{n}})) . (13)

2 Proofs.

Proof of Theorem 1. The following lemma provides the inequalities needed to establish (6). Lemma 1. If the kernel h satisfies the condition d < ∞, then for all k = 1, 2, … |c_{k}(x)| ≤ c(x)γ_{k}, x ∈ X (14) where

γ_{k} = \binom{2k}{k} \frac{(2d(1 + d))^{k}}{4(2k − 1)(1 + d)} (\frac{m − 1}{a})^{k−1} .

Proof. We will use induction on k. By the definition (3) and Hölder’s inequality

| c_{1}(x) | ≤ c(x)
| c_{2}(x) | ≤ (m − 1)c(x) (Ec^{2}(X))^{1/2} .

Next according to the definition of {γ_{k}}

γ_{1} = d, and γ_{2} = 2d^{2}(1 + d) \frac{m − 1}{a}.

Here d ≥ 1 and moreover

d = (E exp\{ac(X)\})^{1/2} = (1 + aEc(X) + \frac{1}{2}a^{2}Ec^{2}(X) + ⋯)^{1/2} ≥ \frac{a}{\sqrt{2}} (Ec^{2}(X))^{1/2}

and

γ_{2} ≥ 2d \frac{m − 1}{a} ≥ (m − 1)\sqrt{2} (Ec^{2}(X))^{1/2} .

Therefore

| c_{1}(x) |≤ c(x)γ_{1}, and | c_{2}(x) |≤ c(x)γ_{2}.

Now suppose that (14) is valid for s = 1, …, k − 1, that is,

| c_{s}(x) |≤ c(x) γ_{s}, s = 1, …, k − 1.

From (2)

| c_{k}(x) |≤ ∑_{l=0}^{k−1} | a_{l}(x) | | b_{k−l−1} |,

where by the induction hypothesis

|a_{l}(x)| ≤ ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} E | h (X_{1}, …, X_{m−1}, x) | ∏_{s=1}^{l} \frac{1}{ν_{s}!}\{( ∑_{j=1}^{m−1} c(X_{j})) γ_{s}\}^{ν_{s}}
= ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} E | h (X_{1}, …, X_{m−1}, x) | ( ∑_{j=1}^{m−1} c(X_{j}))^{ν_{1}+···+ν_{l}} ∏_{s=1}^{l} \frac{1}{ν_{s}!}γ_{s}^{ν_{s}}.

Since c^{ν}(x) ≤ \frac{ν!}{a^{ν}} exp\{ac(x)\}, a > 0, ν = ν_{1}+⋯+ν_{l} and using Hölder’s inequality |a_{l}(x)|

≤ E | h (X_{1}, …, X_{m−1}, x) | exp\{\frac{a}{2(m − 1)} ∑_{j=1}^{m−1} c(X_{j})\}

× ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l}(ν_{1} + ⋯ + ν_{l})! ∏_{s=1}^{l} \frac{1}{ν_{s}!} (\frac{2(m − 1)}{a}γ_{s})^{ν_{s}}

≤ c(x) (E exp (\frac{a}{m − 1}c(X)))^{\frac{m−1}{2}} ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} (ν_{1} + ⋯ + ν_{l})! ∏_{s=1}^{l} \frac{1}{ν_{s}!} (\frac{2(m − 1)}{a}γ_{s})^{ν_{s}}
≤ c(x) (E exp{ac(X)})^{1/2} ā_{l}
= c(x) d ā_{l}.

Also

|β_{l}| ≤ ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} E ∏_{s=1}^{l} \frac{1}{ν_{s}!}\{( ∑_{j=1}^{m−1} c(X_{j})) γ_{s}\}^{ν_{s}}
= ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} E ( ∑_{j=1}^{m−1} c(X_{j}))^{ν_{1}+···+ν_{l}} ∏_{s=1}^{l} \frac{1}{ν_{s}!}γ_{s}^{ν_{s}}
≤ E exp\{\frac{a}{2(m − 1)} ∑_{j=1}^{m−1} c(X_{j})\}

× ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} (ν_{1} + ⋯ + ν_{l})! ∏_{s=1}^{l} \frac{1}{ν_{s}!} (\frac{2(m − 1)}{a}γ_{s})^{ν_{s}}

≤ (E exp{ac(X)})^{1/2} ā_{l}
= d ā_{l}

and

|b_{l}| ≤ ∑_{ν_{1}+2ν_{2}+···+lν_{l}=l} (ν_{1} + ⋯ + ν_{l})! ∏_{s=1}^{l} \frac{1}{ν_{s}!} (d ā_{s})^{ν_{s}} = b̄_{l},

setting ā_{0} = 1 and b̄_{0} = 1. Hence,

| c_{k}(x) |≤ c(x) d ∑_{l=0}^{k−1} ā_{l} b̄_{k−l−1}. (15)

It is sufficient to show that in (15)

γ_{k} = d ∑_{l=0}^{k−1} ā_{l} b̄_{k−l−1}. (16)

Let

γ(z) = ∑_{k=1}^{∞} γ_{k} z^{k}

be the generating function of the sequence {γ_{k}}. If (16) holds then

γ(z) = d ∑_{k=1}^{∞} (∑_{l=0}^{k−1} ā_{l} b̄_{k−l−1}) z^{k} = d z ∑_{k=0}^{∞} (∑_{l=0}^{k} ā_{l} b̄_{k−l}) z^{k}
= d z (∑_{k=0}^{∞} ā_{k} z^{k}) (∑_{k=0}^{∞} b̄_{k} z^{k}) ,

where

∑_{k=0}^{∞} ā_{k} z^{k} = 1 + ∑_{k=1}^{∞} (  ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{2(m − 1)}{a}γ_{s})^{ν_{s}} ) z^{k}
= (1 − \frac{2(m − 1)}{a} ∑_{k=1}^{∞} γ_{k} z^{k})^{−1}

and

∑_{k=0}^{∞} b̄_{k} z^{k} = 1 + ∑_{k=1}^{∞} (  ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}(d ā_{s})^{ν_{s}} ) z^{k}
= (1 − d ∑_{k=1}^{∞} ā_{k} z^{k})^{−1} .

Hence,

γ(z) = d z (1 − \frac{2(m − 1)}{a}γ(z))^{−1} (1 + d − \frac{d}{1 − \frac{2(m−1)}{a}γ(z)})^{−1}
= \frac{d z}{(1 + d) (1 − \frac{2(m−1)}{a}γ(z)) − d}.

Therefore from (16) we obtain the quadratic equation for the generating function

γ^{2}(z) − \frac{a}{2(m − 1)(1 + d)}γ(z) + \frac{a d z}{2(m − 1)(1 + d)} = 0, γ(0) = 0.

From here for |z| ≤ a/(8d(1 + d)(m − 1)) we find the solution

γ(z) = \frac{a}{4(m − 1)(1 + d)} − \frac{a}{4(m − 1)(1 + d)} (1 − 8d(1 + d)\frac{(m − 1)z}{a} )^{1/2} . (17)

Using the well-known expansion

(1 − 4z)^{1/2} = 1 − ∑_{k=1}^{∞} \binom{2k}{k}\frac{1}{2k − 1}z^{k}, |z| ≤ \frac{1}{4}

we have from (17)

γ(z) = ∑_{k=1}^{∞} γ_{k} z^{k}

with coefficients

γ_{k} = \binom{2k}{k} \frac{(2d(1 + d))^{k}}{4(2k − 1)(1 + d)} (\frac{m − 1}{a})^{k−1} .

This proves Lemma 1.

From (17) it follows that if |z| ≤ a/(8d(1 + d)(m − 1)) then

|γ(z)| ≤ 2d |z|.

The coefficients {γ_{k}} satisfy the inequality

γ_{k} ≤ \frac{1}{8} (8d(1 + d))^{k} (\frac{m − 1}{a})^{k−1} , k = 1, 2, … (18)

since \binom{2k}{k} ≤ 2^{2k} and d ≥ 1.

From (14) and (18) we get the estimate (6). Lemma 2. If d < ∞ and 0 ≤ t < a/(8d(1 + d)(m − 1)) then the function g_{t}(x) defined in (7) is the solution of equation (1). Proof. Denote z_{t}(x) = t g_{t}(x) and rewrite equation (1) in the form

z_{t}(x) = t \frac{E ∏_{s=1}^{m−1} e^{z_{t}(X_{s})}h (X_{1}, …, X_{m−1}, x)}{(Ee^{z_{t}(X)})^{m−1}}. (19)

We must prove that under the condition d < ∞ the analytical function

z_{t}(x) = ∑_{k=1}^{∞} c_{k}(x)t^{k} (20)

satisfies equation (19). In (20) the power series converges in the region 0 ≤ t < a/(8d(1+d)(m−1)) due to (6). The numerator in (19) has the convergent expansion

E ∏_{s=1}^{m−1} e^{z_{t}(X_{s})}h (X_{1}, …, X_{m−1}, x)

= E exp{∑_{k=1}^{∞} ( ∑_{j=1}^{m−1} c_{k}(X_{j}))t^{k}}h (X_{1}, …, X_{m−1}, x)
= ∑_{k=0}^{∞} \{  ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} Eh (X_{1}, …, X_{m−1}, x) ∏_{s=1}^{k} \frac{1}{ν_{s}!} ( ∑_{j=1}^{m−1} c_{s}(X_{j}))^{ν_{s}}\}t^{k}
= ∑_{k=0}^{∞} a_{k}(x) t^{k}, a_{0}(x) = g(x).

Similarly the denominator in (19) has the convergent expansion

(Ee^{z_{t}(X)})^{−(m−1)}
= (E exp{∑_{k=1}^{∞} ( ∑_{j=1}^{m−1} c_{k}(X_{j}))t^{k}})^{−1}
= (1 + ∑_{k=1}^{∞} \{  ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} E ∏_{s=1}^{k} \frac{1}{ν_{s}!} ( ∑_{j=1}^{m−1} c_{s}(X_{j}))^{ν_{s}}\}t^{k})^{−1}
= (1 + ∑_{k=1}^{∞} β_{k}t^{k})^{−1}
= 1 + ∑_{k=1}^{∞} \{  ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{(−1)^{ν_{s}}}{ν_{s}!} β_{s}^{ν_{s}}\}t^{k}
= ∑_{k=0}^{∞} b_{k} t^{k}, b_{0} = 1.

Hence

\frac{E ∏_{s=1}^{m−1} e^{z_{t}(X_{s})}h (X_{1}, …, X_{m−1}, x)}{(Ee^{z_{t}(X)})^{m−1}} = ∑_{k=0}^{∞} \{∑_{l=0}^{k} a_{l}(x) b_{k−l}\}t^{k}

and thus

t \frac{E ∏_{s=1}^{m−1} e^{z_{t}(X_{s})}h (X_{1}, …, X_{m−1}, x)}{(Ee^{z_{t}(X)})^{m−1}} = ∑_{k=1}^{∞} \{∑_{l=0}^{k−1} a_{l}(x) b_{k−l−1}\}t^{k}, (21)

where due to (6) the series converges in the region 0 ≤ t < a/(8d(1 + d)(m − 1)). Comparing (19) - (21) we see that for all k = 1, 2, …

c_{k}(x) = ∑_{l=0}^{k−1} a_{l}(x) b_{k−1−l}, x ∈ X.

This formula coincides with (2). As a result we obtain the proof of Lemma 2.

Theorem 1 follows from Lemma 1 and Lemma 2. Proof of Theorem 2. Define F_{t} by

dF_{t} = e^{tg_{t}−ψ(t)}dF,

where

ψ(t) = ln E exp{tg_{t}(X)}.

Let E_{t} denote the expectation under P_{t}, where P_{t} is a probability measure under which X_{1}, X_{2}, … are i.i.d. from F_{t}.

We will specify t via the saddle-point equation

μ_{t} = \frac{mσx}{\sqrt{n}}, (22)

where μ_{t} = E_{t}g_{t}(X) and xn^{−1/2} → 0. Lemma 3. Let t = t (\frac{x}{σ\sqrt{n}}) be the solution of equation (22). Then

t = ∑_{k=1}^{∞} π_{k}(\frac{x}{σ\sqrt{n}})^{k} (23)

is a convergent power series with π_{1} = 1 and coefficients π_{k}, k ≥ 2 specified at (26), which satisfy the inequality

|π_{k}| ≤ \frac{2}{k} (\frac{128md(1 + d)^{2}}{a} )^{k−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k−1} , k ≥ 1.

Proof. By definition

μ_{t} = \frac{E exp\{t ∑_{j=1}^{m} g_{t}(X_{j})\}h (X_{1}, …, X_{m})}{E exp\{t ∑_{j=1}^{m} g_{t}(X_{j})\}}.

Using (7) we obtain the expansions

E exp{t ∑_{j=1}^{m} g_{t}(X_{j})}h (X_{1}, …, X_{m}) = ∑_{k=1}^{∞} d_{k}(h)t^{k}, d_{1}(h) = mσ^{2}

and

E exp{t ∑_{j=1}^{m} g_{t}(X_{j})}= 1 + ∑_{k=1}^{∞} d_{k}(1)t^{k},

with

d_{k}(h) = ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} Eh (X_{1}, …, X_{m}) ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{∑_{j=1}^{m} c_{s}(X_{j})\}^{ν_{s}}, k ≥ 1

where due to (6)

|d_{k}(h)| ≤ ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} E | h (X_{1}, …, X_{m}) |

× ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{(∑_{j=1}^{m} c(X_{j})) (8d(1 + d))^{s} (\frac{m}{a})^{s−1} \frac{1}{2}\}^{ν_{s}}

= (\frac{8md(1 + d)}{a})^{k} ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} E | h (X_{1}, …, X_{m}) |

× ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{(∑_{j=1}^{m} c(X_{j})) \frac{a}{2m}\}^{ν_{s}}

≤ (\frac{8md(1 + d)}{a})^{k} E | h(X_{1}, …, X_{m}) | exp\{\frac{a}{2m} ∑_{j=1}^{m} c(X_{j})\}

× ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}

≤ \frac{1}{2} (\frac{16md(1 + d)}{a})^{k} ∥ c ∥ d, k ≥ 1

by virtue of Hölder’s inequality and the formula

∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}y^{ν_{s}} = y(1 + y)^{k−1}, k ≥ 1. (24)

Similarly,

|d_{k}(1)| ≤ \frac{1}{2} (\frac{16md(1 + d)}{a})^{k} d, k ≥ 1.

Further

∑_{k=1}^{∞} d_{k}(h)t^{k} = tmσ^{2} (1 + ∑_{k=1}^{∞} (\frac{d_{k+1}(h)}{mσ^{2}})t^{k})
= tmσ^{2} exp\{ln (1 + ∑_{k=1}^{∞} (\frac{d_{k+1}(h)}{mσ^{2}})t^{k}) \}
= tmσ^{2} exp{∑_{k=1}^{∞} A_{k}t^{k}},

where

A_{k} = ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k} − 1)! ∏_{s=1}^{k} \frac{(−1)^{ν_{s}−1}}{ν_{s}!} (\frac{d_{s+1}(h)}{mσ^{2}})^{ν_{s}} ,

in addition

|A_{k}| ≤ ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{\frac{1}{2mσ^{2}} (\frac{16md(1 + d)}{a})^{s+1} ∥ c ∥ d\}^{ν_{s}}
= (\frac{16md(1 + d)}{a})^{k} ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ×

× ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{\frac{8d(1 + d)}{σ^{2}a} ∥ c ∥ d\}^{ν_{s}}

= (\frac{16md(1 + d)}{a})^{k} (\frac{8d^{2}(1 + d) ∥ c ∥}{aσ^{2}}) (1 + \frac{8d^{2}(1 + d) ∥ c ∥}{aσ^{2}})^{k−1}
≤ (\frac{16md(1 + d)}{a})^{k} (1 + \frac{8d^{2}(1 + d) ∥ c ∥}{aσ^{2}})^{k} , k ≥ 1

taking account of (24).

Further,

(1 + ∑_{k=1}^{∞} d_{k}(1)t^{k})^{−1} = exp{− ln (1 + ∑_{k=1}^{∞} d_{k}(1)t^{k}) }= exp{− ∑_{k=1}^{∞} B_{k}t^{k}},

where

B_{k} = ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k} − 1)! ∏_{s=1}^{k} \frac{(−1)^{ν_{s}−1}}{ν_{s}!} (d_{s}(1))^{ν_{s}},

in addition

|B_{k}| ≤ ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{\frac{d}{2} (\frac{16md(1 + d)}{a})^{s} \}^{ν_{s}}
= (\frac{16md(1 + d)}{a})^{k} ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{d}{2})^{ν_{s}}
= (\frac{16md(1 + d)}{a})^{k} \frac{d}{2} (1 + \frac{d}{2})^{k−1}
≤ (\frac{16md(1 + d)}{a})^{k} (1 + \frac{d}{2})^{k} , k ≥ 1

because of (24).

Hence the equation (22) is reduced to the form

t = \frac{x}{σ\sqrt{n}} exp\{D(t)\}, (25)

where

D(t) = ∑_{k=1}^{∞} D_{k}t^{k},

with the coefficients D_{k} = B_{k} − A_{k}, and

|D_{k}| ≤ 2 (\frac{16md(1 + d)^{2}}{a} )^{k} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k} , k ≥ 1.

Using the Lagrange expansion (see, Whittaker and Watson (1927)) we find the solution of equation (25) is

t = ∑_{k=1}^{∞} π_{k} (\frac{x}{σ\sqrt{n}})^{k},

where

π_{k} = \frac{1}{k} ∑_{ν_{1}+2ν_{2}+···+(k−1)ν_{k−1}=k−1} ∏_{s=1}^{k−1} \frac{1}{ν_{s}!} (kD_{s})^{ν_{s}}, k ≥ 1, (26)

setting π_{1} = 1. Note that

|π_{k}| ≤ \frac{1}{k} ∑_{ν_{1}+2ν_{2}+···+(k−1)ν_{k−1}=k−1} ∏_{s=1}^{k−1} \frac{1}{ν_{s}!}\{2k (\frac{16md(1 + d)^{2}}{a} )^{s} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{s} \}^{ν_{s}}
= \frac{4^{k−1}}{k} (\frac{16md(1 + d)^{2}}{a} )^{k−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k−1}

× ∑_{ν_{1}+2ν_{2}+···+(k−1)ν_{k−1}=k−1} ∏_{s=1}^{k−1} \frac{1}{ν_{s}!}\{2k (\frac{1}{4})^{s} \}^{ν_{s}}

≤ \frac{4^{k−1}}{k} (\frac{16md(1 + d)^{2}}{a} )^{k−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k−1} ∏_{s=1}^{k−1}\{ ∑_{ν_{s}=0}^{∞} \frac{1}{ν_{s}!} (2k (\frac{1}{4})^{s})^{ν_{s}}\}
= \frac{4^{k−1}}{k} (\frac{16md(1 + d)^{2}}{a} )^{k−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k−1} ∏_{s=1}^{k−1} exp\{2k (\frac{1}{4})^{s} \}
= \frac{4^{k−1}}{k} (\frac{16md(1 + d)^{2}}{a} )^{k−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k−1} exp\{\frac{2k}{3} (1 − (\frac{1}{4})^{k}) \}
≤ \frac{2}{k} (\frac{128md(1 + d)^{2}}{a} )^{k−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k−1} , k ≥ 1.

This proves Lemma 3.

Let U_{n}(t) denote the U-statistic U_{n}, where X_{1}, X_{2}, … are i.i.d. with the distribution F_{t}. Using the Hoeffding representation under P_{t}

U_{n}(t) = S_{n}(t) − \frac{n(m − 1)}{m}μ_{t} + v_{n}(t),

where

S_{n}(t) = ∑_{i=1}^{n} g_{t}(X_{i}),
g_{t}(x) = E_{t}(h(X_{1}, …, X_{m−1}, X_{m})|X_{m} = x),

and

v_{n}(t) = \frac{m − 1}{n − 1} ∑_{1≤i_{1}<i_{2}≤n} g_{2t}(X_{i_{1}}, X_{i_{2}}) + ⋯

+\frac{(m − 1) ⋯ 2 · 1}{(n − 1) ⋯ (n − m + 1)} ∑_{1≤i_{1}<···<i_{m}≤n} g_{mt}(X_{i_{1}}, …, X_{i_{m}}),

where g_{ct} : X^{c} → R, c = 2, …, m, are canonical functions satisfying the property of complete degeneracy E_{t}g_{ct}(x_{1}, …, x_{c−1}, X_{c}) = 0, a.s. and having the representation

g_{ct}(x_{1}, …, x_{c}) = ∑_{d=0}^{c}(−1)^{c−d} ∑_{1≤i_{1}<···<i_{d}≤c} E_{t} h(x_{i_{1}}, …, x_{i_{d}}, X_{d+1}, …, X_{m}). (27)

In what follows t is the solution of the equation (22), that is, t has the expansion (23). By virtue of (22)

U_{n}(t) − xσ\sqrt{n} = S_{n}(t) − nμ_{t} + v_{n}(t)

and hence

P (U_{n} > xσ\sqrt{n})
= ∫ ⋯ ∫ I(U_{n}(y_{1}, …, y_{n}) > xσ\sqrt{n}) ∏_{i=1}^{n} dF (y_{i})
= ∫ ⋯ ∫ exp\{∑_{i=1}^{n}(ψ(t) − tg_{t}(y_{i}))\} I(U_{n}(y_{1}, …, y_{n}) > xσ\sqrt{n}) ∏_{i=1}^{n} dF_{t}(y_{i})
= E_{t}[e^{nψ(t)−tS_{n}(t)}I(U_{n}(t) > xσ\sqrt{n})]
(28) = e^{nψ(t)−ntμ_{t}} T_{n}(t),

where

T_{n}(t) = E_{t}[e^{−t(S_{n}(t)−nμ_{t})}I(S_{n}(t) − nμ_{t} + v_{n}(t) > 0)].

Definition of Cramér’s series. With the help of (7), under the condition xn^{−1/2} → 0 we have

ψ(t) = ln(1 + ∑_{k=2}^{∞} G_{k}t^{k}) = ∑_{k=2}^{∞} H_{k}t^{k},

where

G_{1} = 0, G_{k} = ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} E ∏_{s=1}^{k} \frac{1}{ν_{s}!}c_{s}^{ν_{s}}(X), and,

H_{0} = H_{1} = 0, H_{k} = ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k} − 1)! ∏_{s=1}^{k} \frac{(−1)^{ν_{s}−1}}{ν_{s}!} G_{s}^{ν_{s}}, k ≥ 2.

Using (6) for k ≥ 2

|G_{k}| ≤ ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} E ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{c(X) (8d(1 + d))^{s} (\frac{m − 1}{a})^{s−1} \}^{ν_{s}}
= (8d(1 + d))^{k} (\frac{m − 1}{a})^{k} ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} E (\frac{a}{2} c(X))^{ν_{1}+···+ν_{k}} ∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{2}{m − 1})^{ν_{s}}
≤ (8d(1 + d))^{k} (\frac{m − 1}{a})^{k} d ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{2}{m − 1})^{ν_{s}}
≤ (\frac{24md(1 + d)}{a})^{k} d

and

|H_{k}| ≤ ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{(\frac{24md(1 + d)}{a})^{s} d\}^{ν_{s}}
= (\frac{24md(1 + d)}{a})^{k} ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k} (ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!} d^{ν_{s}}
= (\frac{24md(1 + d)}{a})^{k} d(1 + d)^{k−1} ≤ (\frac{24md(1 + d)^{2}}{a} )^{k} .

Since t is the solution of the saddle-point equation (22)

ψ(t) = ∑_{k=2}^{∞} ψ_{k}(\frac{x}{σ\sqrt{n}})^{k}

with coefficients

ψ_{k} = ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! H_{ν_{1}+···+ν_{k}} ∏_{s=1}^{k} \frac{1}{ν_{s}!}π_{s}^{ν_{s}},

and, moreover, due to (6)

|ψ_{k}| ≤ ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! (\frac{24md(1 + d)^{2}}{a} )^{ν_{1}+···+ν_{k}}

× ∏_{s=1}^{k} \frac{1}{ν_{s}!}\{(\frac{128md(1 + d)^{2}}{a} )^{s−1} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{s−1} \}^{ν_{s}}

≤ (\frac{128md(1 + d)^{2}}{a} )^{k} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k}

× ∑_{ν_{1}+2ν_{2}+···+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{3}{16})^{ν_{s}}

≤ (\frac{128md(1 + d)^{2}}{a} )^{k} (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}})^{k} (1 + \frac{3}{16})^{k}, k ≥ 1.

Since g_{t}(x) can be written as in (7) and t = t (\frac{x}{σ\sqrt{n}}) is the solution of the saddlepoint equation (22) then in (28)

n(ψ(t) − tμ_{t}) = nψ (t (\frac{x}{σ\sqrt{n}})) − mt (\frac{x}{σ\sqrt{n}}) xσ\sqrt{n}
(29)  = −\frac{x^{2}}{2} + \frac{x^{3}}{\sqrt{n}} ∑_{k=0}^{∞} λ_{mk} (\frac{x}{\sqrt{n}})^{k} = −\frac{x^{2}}{2} + \frac{x^{3}}{\sqrt{n}}λ_{m} (\frac{x}{\sqrt{n}}) ,

defining the Cramér series (11) with the coefficients

λ_{mk} = \frac{1}{σ^{k+3}} ψ_{k+3} − \frac{m}{σ^{k+1}} π_{k+2}, k = 0, 1, ….

Since

d^{2} = Ee^{ac(X)} = 1 + aEc(X) + \frac{1}{2}a^{2}Ec^{2}(X) + ⋯ ≥ \frac{1}{2}a^{2}Ec^{2}(X) ≥ \frac{1}{2}a^{2}σ^{2},

then from here we find that λ_{mk} satisfy the inequality

|λ_{mk}| ≤ \{(\frac{152md(1 + d)^{2}}{aσ} ) (1 + \frac{8d^{2} ∥ c ∥}{aσ^{2}}) \}^{k+3}, k = 0, 1, ….

Estimate of T_{n}(t).

Next we need to estimate T_{n}(t) in (28). Denote

v_{nc}(t) = \frac{(m − 1) ⋯ (m − c + 1)}{(n − 1) ⋯ (n − c + 1)} ∑_{1≤i_{1}<···<i_{c}≤n} g_{ct}(X_{i_{1}}, …, X_{i_{c}}). (30)

Then v_{n}(t) = v_{n2}(t) + ⋯ + v_{nm}(t).

Further for c = 2, …, m and δ > 0 let

f_{c}(x_{1}, …, x_{c}) = (δ_{x_{1}} − F_{t}) ⋯ (δ_{x_{c}} − F_{t}) g_{ct} I (|g_{ct}| ≤ \frac{2^{2c+2}}{a} δ\sqrt{n}/x) ,
f̄_{c}(x_{1}, …, x_{c}) = (δ_{x_{1}} − F_{t}) ⋯ (δ_{x_{c}} − F_{t}) g_{ct} I (|g_{ct}| > \frac{2^{2c+2}}{a} e_{l−1} (δ\sqrt{n}/x)) ,
φ_{pc}(x_{1}, …, x_{c}) = (δ_{x_{1}} − F_{t}) ⋯ (δ_{x_{c}} − F_{t})

×g_{ct}I (\frac{2^{2c+2}}{a} e_{p−1} (δ\sqrt{n}/x) < |g_{ct}| ≤ \frac{2^{2c+2}}{a} e_{p} (δ\sqrt{n}/x)) ,

where e_{p}(y) = exp{exp_{p−1}(y)} is the iterated exponential function, p = 1, …, l − 1, setting exp_{0}(y) = y, and l ≥ 2 is any fixed integer. Each of these functions can be written in the form (27). Next we define v_{nc}^{f}(t) and v_{n}^{f}(t) by analogy with (30), where instead of g_{ct} we take f_{c}. Obviously

g_{ct} = f_{c} + f̄_{c} + ∑_{p=1}^{l−1} φ_{pc}, v_{nc}(t) = v_{nc}^{f}(t) + vf̄ ; nc(t) + ∑_{p=1}^{l−1} v_{nc}^{φ_{p}}(t),

and

v_{n}(t) = ∑_{c=2}^{m} v_{nc}^{f}(t) + ∑_{c=2}^{m} vf̄ ; nc(t) + ∑_{c=2}^{m} ∑_{p=1}^{l−1} v_{nc}^{φ_{p}}(t),

v_{n}(t) = v_{n}^{f}(t) + vf̄ ; n(t) + ∑_{p=1}^{l−1} v_{n}^{φ_{p}}(t). (31)

Estimate of exponential moments. Now we will use the decomposition (31), the representation in Hoeffding (1963), the decoupling inequalities due to de la Peña (1992) and the inequality in Borell (1979) for Rademacher chaos.

Hoeffding’s formula. Denote

ϕ_{n}(x_{1}, …, x_{n}) = \frac{1}{k} ∑_{j=1}^{k} ϕ(x_{jm−m+1}, …, x_{jm}),

for some symmetric function ϕ, where k = [n/m] is the integer part of the number n/m. Then

\binom{n}{m}^{−1} ∑_{1≤i_{1}<···<i_{m}≤n} ϕ(X_{i_{1}}, …, X_{i_{m}}) = \frac{1}{n!} ∑ ϕ_{n}(X_{i_{1}}, …, X_{i_{n}}), (32)

where the summation on the right is carried out over all the permutations (i_{1}, …, i_{n}) of (1, …, n).

de la Peña decoupling inequalities. Let ϕ : X^{m} → B be a symmetric degenerate kernel taking values in a Banach space (B, ∥ · ∥) and let Ψ : R → R be any convex increasing function. If X_{1}^{j}, …, X_{n}^{j}, j = 1, …, m, are independent copies of X_{1}, …, X_{n}, then the upper decoupling inequality

E Ψ (∥ ∑_{1≤i_{1}<···<i_{m}≤n} ϕ(X_{i_{1}}, …, X_{i_{m}}) ∥)

≤ E Ψ (m^{m} ∥ ∑_{1≤i_{1}<···<i_{m}≤n} ϕ(X_{i_{1}}^{1}, …, X_{i_{m}}^{m}) ∥) (33)

and the lower decoupling inequality

E Ψ (∥ ∑_{1≤i_{1}<···<i_{m}≤n} ϕ(X_{i_{1}}^{1}, …, X_{i_{m}}^{m}) ∥)

≤ E Ψ (2^{2m−2}(m − 1)! ∥ ∑_{1≤i_{1}<···<i_{m}≤n} ϕ(X_{i_{1}}, …, X_{i_{m}}) ∥) (34)

are valid.

Borell’s inequality. Let {ε_{j}}, {ε_{j}^{i}}, i, j ≥ 1, be the independent sequences of i.i.d. random variables with distribution 2^{−1}δ_{−1} + 2^{−1}δ_{1} and let x_{i_{1},...,i_{m}} be elements in a Banach space (B, ∥ · ∥). Denote

X = ∑_{1≤i_{1}<···<i_{m}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{m}}^{m}x_{i_{1},...,i_{m}}.

By Borell’s inequality for all p ≥ 2

E ∥ X ∥^{p}≤ (p − 1)^{pm/2} s^{p}, (35) where

s^{2} = ∑_{1≤i_{1}<···<i_{m}≤n} x_{i_{1},...,i_{m}}^{2}.

It follows from (35) that

E exp (θ ∥ X ∥^{α}) ≤ 2 exp\{\frac{2 − αm}{2}(4αm)^{αm/(2−αm)}θ^{2/(2−αm)}s^{2α/(2−αm)}\} (36)

for any θ > 0 and 0 < α < 2/m (see, Arcones (1995) or Arcones and Giné (1993)).

In the following we will use the geometric-arithmetic mean inequality |x_{1} ⋯ x_{m}| ≤ q_{1}^{−1}|x_{1}|^{q_{1}} + ⋯ + q_{m}^{−1}|x_{m}|^{q_{m}}, q_{1}^{−1} + ⋯ + q_{m}^{−1} = 1, x_{i} ∈ R. (37) Lemma 4. If δ > 0 satisfies the condition (4m)^{2m}12eδt\sqrt{n}/x < a then

E_{t} exp\{3t|v_{n}^{f}(t)|\} ≤ (1 − (4m)^{2m}12e\frac{δ}{a} t \frac{\sqrt{n}}{x})^{−1} .

Proof. We have from (37) and (33)

E_{t} exp{3t|v_{n}^{f}(t)|} ≤ E_{t} ∏_{c=2}^{m} exp{3t|v_{nc}^{f}(t)|}
≤ \frac{1}{m − 1} ∑_{c=2}^{m} E_{t} exp\{3(m − 1)t|v_{nc}^{f}(t)|\}
≤ \frac{1}{m − 1} ∑_{c=2}^{m} E_{t} exp\{3m^{m}c^{c}tn^{−c+1} | ∑_{1≤i_{1}<···<i_{c}≤n} f_{c} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c}) | \}.

By symmetrization (cf. Ledoux and Talagrand (1991), p.152) and noting |f_{c}| ≤ 2^{c}(2^{2c+2}/a) δ \sqrt{n}/x, E_{t} exp{3t|v_{n}^{f}(t)|}

≤ \frac{1}{m − 1} ∑_{c=2}^{m} E exp\{3 m^{m} c^{c} 2^{c} t n^{−c+1} | ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}f_{c} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c}) | \}
≤ \frac{1}{m − 1} ∑_{c=2}^{m} E exp\{3 m^{m} c^{c} 2^{c} 2^{(3c+2)(c−2)/c} (\frac{δ}{a})^{(c−2)/c} (t\sqrt{n}/x)

× | n^{−c/2} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}f_{c} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c}) |^{2/c} }

= \frac{1}{m − 1} ∑_{c=2}^{m} ∑_{k=0}^{c} \frac{1}{k!} (3 m^{m} c^{c} 2^{c} 2^{(3c+2)(c−2)/c} (\frac{δ}{a})^{(c−2)/c} (t\sqrt{n}/x))^{k}

×E |n^{−c/2} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}f_{c} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c})|^{2k/c}

+\frac{1}{m − 1} ∑_{c=2}^{m} ∑_{k=c+1}^{∞} \frac{1}{k!} (3 m^{m} c^{c} 2^{c} 2^{(3c+2)(c−2)/c} (\frac{δ}{a})^{(c−2)/c} (t\sqrt{n}/x))^{k}

×E |n^{−c/2} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}f_{c} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c})|^{2k/c}

≤ \frac{1}{m − 1} ∑_{c=2}^{m} ∑_{k=0}^{c} \frac{1}{k!} (3 m^{m} c^{c} 2^{c} 2^{(3c+2)(c−2)/c} (\frac{δ}{a})^{(c−2)/c} (t\sqrt{n}/x))^{k}

×E_{t} (n^{−c} ∑_{1≤i_{1}<···<i_{c}≤n} f_{c}^{2} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c}) \frac{x^{2}}{n} )^{\frac{k}{c}}

+\frac{1}{m − 1} ∑_{c=2}^{m} ∑_{k=c+1}^{∞} \frac{1}{k!} (3 m^{m} c^{c} 2^{c} 2^{(3c+2)(c−2)/c} (\frac{δ}{a})^{(c−2)/c} (t\sqrt{n}/x))^{k} k^{k}

×E_{t} (n^{−c} ∑_{1≤i_{1}<···<i_{c}≤n} f_{c}^{2} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c}) \frac{x^{2}}{n} )^{\frac{k}{c}}

where the last inequality follows from Hölder’s inequality and Borell’s inequality (35). Since |f_{c}| ≤ 2^{c} (2^{2c+2}/a)δ \sqrt{n}/x and k! ≥ e^{−k} k^{k} we have

E_{t} exp\{3t|v_{n}^{f}(t)|\} ≤ \frac{1}{m − 1} ∑_{c=2}^{m} ∑_{k=0}^{c} \frac{1}{k!} (3 m^{m} c^{c} 2^{4c+2} \frac{δ}{a} t \frac{\sqrt{n}}{x})^{k}

+\frac{1}{m − 1} ∑_{c=2}^{m} ∑_{k=c+1}^{∞} (3 m^{m} c^{c} 2^{4c+2} e \frac{δ}{a} t \frac{\sqrt{n}}{x})^{k}

≤ ∑_{k=0}^{∞} ((4m)^{2m}12 e \frac{δ}{a} t \frac{\sqrt{n}}{x})^{k}
= (1 − (4m)^{2m}12 e \frac{δ}{a} t \frac{\sqrt{n}}{x})^{−1} ,

since (4m)^{2m}12 e δ t \sqrt{n}/x < a. This proves Lemma 4. Lemma 5. If m ≥ 2 and 0 ≤ t ≤ 2^{−2m−8}a/m then under Cramér’s condition (4)

E_{t} exp\{3 t |vf̄ ; n(t)|\}≤ 2 exp\{t^{2} n (e_{l} (δ\sqrt{n}/x))^{−1} A_{t}\},

where

A_{t} = 3m2^{4m} (E_{t}h^{8})^{1/4} E_{t} exp (\frac{a}{2}|h|) .

Proof. By (32) and the convexity of e^{|x|},

E_{t} exp\{3 t |vf̄ ; n(t)|\} ≤ \frac{1}{m − 1} ∑_{c=2}^{m} E_{t} exp\{3 (m − 1) t |vf̄ ; nc(t)|\}

≤ \frac{1}{m − 1} ∑_{c=2}^{m} E_{t} exp\{6 m t | ∑_{j=1}^{[n/c]} f̄_{c}(X_{jc−c+1}, …, X_{jc})|\}
≤ \frac{1}{m − 1} ∑_{c=2}^{m} E_{t} exp\{6 m t ∑_{j=1}^{[n/c]} f̄_{c}(X_{jc−c+1}, …, X_{jc})\}

+\frac{1}{m − 1} ∑_{c=2}^{m} E_{t} exp\{− 6 m t ∑_{j=1}^{[n/c]} f̄_{c}(X_{jc−c+1}, …, X_{jc})\},

since e^{|x|} ≤ e^{x} + e^{−x},

≤ \frac{1}{m − 1} ∑_{c=2}^{m} (E_{t} exp\{6 m t f̄_{c}(X_{1}, …, X_{c})\})^{[n/c]}

+\frac{1}{m − 1} ∑_{c=2}^{m} (E_{t} exp\{− 6 m t f̄_{c}(X_{1}, …, X_{c})\})^{[n/c]} , (38)

using the independence of X_{1}, …, X_{n}. Next apply the formula

e^{x} = ∑_{r=0}^{s−1} \frac{1}{r!} x^{r} + \frac{1}{(s − 1)!}x^{s} ∫_{0}^{1}(1 − u)^{s−1} e^{ux} du (39)

which is valid for all x ∈ R and integers s = 1, 2, …. Then

E_{t} exp{6 m t f̄_{c}(X_{1}, …, X_{c})} = 1 + (6mt)^{2} ∫_{0}^{1}(1 − u){E_{t}f̄_{c}^{2} e^{6mtuf̄_{c}}} du
≤ 1 + 2(3mt)^{2} E_{t} f̄_{c}^{2} e^{6mt|f̄_{c}|}
≤ 1 + 2(3mt)^{2} (E_{t} f̄_{c}^{4})^{1/2} (E_{t} e^{12mt|f̄_{c}|})^{1/2}
(40)  ≤ exp{2 (3m)^{2} t^{2} (E_{t} f̄_{c}^{4})^{1/2} (E_{t} e^{12mt|f̄_{c}|})^{1/2} }.

Here

E_{t} f̄_{c}^{4} ≤ 2^{4c} E_{t} g_{ct}^{4} I (|g_{ct}| > 2^{2c+2}a^{−1} e_{l−1} (δ \sqrt{n}/x))
≤ 2^{4c} e^{−2e_{l−1} (δ \sqrt{n}/x)} E_{t} g_{ct}^{4} e^{2^{−2c−1}a|g_{ct}|}
≤ 2^{4c} (e_{l} (δ \sqrt{n}/x))^{−2} (E_{t} g_{ct}^{8})^{1/2} (E_{t} e^{2^{−2c−1}a|g_{ct}|})^{1/2} ,
E_{t} g_{ct}^{8} ≤ 2^{8c} E_{t} h^{8}, and
E_{t} e^{2^{−2c−1}a|g_{ct}|} ≤ E_{t} exp\{2^{c+1} 2^{−2c−1} a |h|\} ≤ E_{t} exp\{\frac{a}{2} |h|\}.

Since t ≤ 2^{−2m−6} a/m then

E_{t} e^{12mt|f̄_{c}|} ≤ E_{t} exp\{2^{2c+4} 3 m t |h|\}≤ E_{t} exp\{\frac{a}{2} |h|\}.

Lemma 5 now follows from (38) and (40).

Lemma 6. Suppose that Cramér’s condition (4) is satisfied. Let

B_{t} = l^{2} (8m)^{4m} (1 + t \frac{\sqrt{n}}{x})^{2} (E_{t} h^{8})^{1/4} E_{t} exp (\frac{a}{2} |h|) .

If

l (4m)^{4m} (t + \frac{x}{\sqrt{n}}) ≤ a

and for c = 2, …, m

B_{t} t^{c} (\frac{x}{\sqrt{n}})^{c−2} ≤ 1 and l (4m)^{4m}B_{t}^{c−1} t^{c+1} (\frac{x}{\sqrt{n}})^{c−1} ≤ a^{2},

then

E_{t} exp{3 t | ∑_{p=1}^{l−1} v_{n}^{φ_{p}}(t)|}≤ l (2m)^{2m}.

Proof. From (37)

E_{t} exp{3 t | ∑_{c=2}^{m} ∑_{p=1}^{l−1} v_{nc}^{φ_{p}}(t)|}

≤ \frac{1}{(m − 1)(l − 1)} ∑_{c=2}^{m} ∑_{p=1}^{l−1} E_{t} exp \{3 (m − 1) (l − 1) t |v_{nc}^{φ_{p}}(t)|\}.

Here by the upper decoupling inequality (33) and symmetrization E_{t} exp {3 (m − 1) (l − 1) t |v_{nc}^{φ_{p}}(t)|}≤ E exp{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|}, (41) where v_{nc}^{dφ_{p}}(t) denotes a decoupling symmetrization version v_{nc}^{φ_{p}}(t), that is,

v_{nc}^{dφ_{p}}(t) = \frac{(c − 1) ⋯ 2 · 1}{(n − 1) ⋯ (n − c + 1)} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}φ_{pc} (X_{i_{1}}^{1}, …, X_{i_{c}}^{c})

and further

E exp{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|}

= E exp\{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|\} I (|v_{nc}^{dφ_{p}}(t)| ≤ 2B_{t}x\sqrt{n}/e_{p} (δ \sqrt{n}/x))

+E exp\{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|\} I (|v_{nc}^{dφ_{p}}(t)| > 2B_{t}x\sqrt{n}/e_{p} (δ \sqrt{n}/x)) . (42) In (42), by Chebyshev’s inequality

E exp\{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|\} I (|v_{nc}^{dφ_{p}}(t)| > 2B_{t}x\sqrt{n}/e_{p} (δ \sqrt{n}/x))

≤ exp\{−2 x^{2} B_{t}/e_{p} (δ \sqrt{n}/x) \}E exp\{(3 m l (2c)^{c} t + x/\sqrt{n}) |v_{nc}^{dφ_{p}}(t)|\}
≤ exp\{−2 x^{2} B_{t}/e_{p} (δ \sqrt{n}/x) \}E exp\{3 l (2c)^{c} 2^{2m−2} m! \frac{n}{c} \binom{n}{c}^{−1} (t + \frac{x}{\sqrt{n}})

×| ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}} ⋯ ε_{i_{c}}φ_{pc}(X_{i_{1}}, …, X_{i_{c}})|}, by (34).

By Hoeffding’s formula (32), the convexity of e^{|x|} and noting m! ≤ m^{m}

E exp\{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|\} I (|v_{nc}^{dφ_{p}}(t)| > 2B_{t}x\sqrt{n}/e_{p} (δ \sqrt{n}/x))
≤ exp\{−2 x^{2} B_{t}/e_{p} (δ \sqrt{n}/x) \}E exp\{3 l (4m)^{2m} (t + x/\sqrt{n})

×| ∑_{j=1}^{[n/c]} ε_{jc−c+1} ⋯ ε_{jc}φ_{pc}(X_{jc−c+1}, …, X_{jc})|}

(43)  ≤ 2 exp\{−x^{2} B_{t}/e_{p} (δ \sqrt{n}/x) \},

where the last inequality follows from (38), (40) and noting that 24 l (8m)^{2m} (t + x/\sqrt{n}) ≤ a. Further we will show that in (42)

E exp\{3 m l (2c)^{c} t |v_{nc}^{dφ_{p}}(t)|\} I (|v_{nc}^{dφ_{p}}(t)| ≤ 2B_{t}x\sqrt{n}/e_{p} (δ \sqrt{n}/x))

≤ 1 + 6 m l (2c)^{c}. (44) To do this we set

V_{c}^{dec}(u) = P (|v_{nc}^{dφ_{p}}(t)| ≤ u) , u ≥ 0
u_{t} = 2 B_{t} x \sqrt{n}/e_{p} (δ \sqrt{n}/x) , and a_{c} = 3 m l (2c)^{c}.

Then

E exp{a_{c} t |v_{nc}^{dφ_{p}}(t)|} I (|v_{nc}^{dφ_{p}}(t)| ≤ u_{t}) = − ∫_{0}^{u_{t}} e^{a_{c} t u} d (1 − V_{c}^{dec}(u))
(45)  ≤ 1 + a_{c} t ∫_{0}^{u_{t}} e^{a_{c} t u} (1 − V_{c}^{dec}(u)) du.

Here

1 − V_{c}^{dec}(u) ≤ e^{−θu^{α}} E exp{θ|v_{nc}^{dφ_{p}}(t)|^{α}}

for any θ > 0 and 0 < α < 1. Further by the inequality (36) with m = c, α = \frac{2}{c+1} and θ = (a_{c} + 1) t u^{1−α}

1 − V_{c}^{dec}(u) ≤ 2 e^{−(2a_{c}+1) t u}E_{t} exp\{\frac{2a_{c} + 1}{c + 1} (\frac{8c}{c + 1})^{c} t^{c+1} u^{c−1}

×\frac{((c − 1)!)^{2}}{((n − 1) ⋯ (n − c + 1))^{2}} ∑_{1≤i_{1}<···<i_{c}≤n} φ_{pc}^{2}(X_{i_{1}}^{1}, …, X_{i_{c}}^{c})\}

≤ 2 e^{−(2a_{c}+1) t u}E_{t} exp\{\frac{2a_{c} + 1}{c + 1} (\frac{8c}{c + 1})^{c} t^{c+1} u^{c−1} \frac{2^{2c−2}((c − 1)!)^{3}}{((n − 1) ⋯ (n − c + 1))^{2}}

× ∑_{1≤i_{1}<···<i_{c}≤n} φ_{pc}^{2}(X_{i_{1}}, …, X_{i_{c}})}, using (34),

(46) ≤ 2 e^{−(2a_{c}+1)tu} E_{t} exp\{b_{c} t^{c+1} u^{c−1} \frac{1}{n^{c−1}} ∑_{j=1}^{[n/c]} φ_{pc}^{2}(X_{jc−c+1}, …, X_{jc})\},

by (32) and convexity, where

b_{c} = \frac{2a_{c} + 1}{c + 1} (\frac{8c}{c + 1})^{c} 2^{2c−2} c^{c−1} (c − 1)! ≤ m l (4m)^{3m}.

In (46), since 1 + x ≤ e^{x} ≤ 1 + x e^{x}, x ≥ 0,

E_{t} exp\{b_{c} t^{c+1} u^{c−1} \frac{1}{n^{c−1}} ∑_{j=1}^{[n/c]} φ_{pc}^{2}(X_{jc−c+1}, …, X_{jc})\}

≤ (E_{t} exp\{b_{c} t^{c+1} u^{c−1} \frac{1}{n^{c−1}} φ_{pc}^{2}(X_{1}, …, X_{c})\})^{n}
≤ (1 + b_{c} t^{c+1} u^{c−1} \frac{1}{n^{c−1}} E_{t} (φ_{pc}^{2}(X_{1}, …, X_{c}) e^{b_{c} t^{c+1} u^{c−1} n^{1−c}φ_{pc}^{2}(X_{1},...,X_{c})}))^{n}
≤ exp\{b_{c} t^{c+1} (\frac{u}{n})^{c−2} uE_{t} (φ_{pc}^{2}(X_{1}, …, X_{c}) exp (b_{c} t^{c+1} (\frac{u}{n})^{c−1} φ_{pc}^{2}(X_{1}, …, X_{c}))) \}.

By Hölder’s inequality

E_{t} (φ_{pc}^{2}(X_{1}, …, X_{c}) exp (b_{c} t^{c+1} (\frac{u}{n})^{c−1} φ_{pc}^{2}(X_{1}, …, X_{c})))

≤ (E_{t} φ_{pc}^{4}(X_{1}, …, X_{c}))^{1/2} (E_{t} exp (2b_{c} t^{c+1} (\frac{u}{n})^{c−1} φ_{pc}^{2}(X_{1}, …, X_{c})))^{1/2} .

Taking into account the definition of φ_{pc}, (27) and convexity we have

E_{t} φ_{pc}^{4}(X_{1}, …, X_{c}) ≤ 2^{8c}E_{t} h^{4} ≤ 2^{8c} (E_{t} h^{8})^{1/2} ,
|φ_{pc}(x_{1}, …, x_{c})| ≤ 2^{3c+2}a^{−1}e_{p} (δ\sqrt{n}/x) ,

and since u ≤ 2x\sqrt{n}B_{t}/e_{p} (δ \sqrt{n}/x)

E_{t} exp (2b_{c} t^{c+1} (\frac{u}{n})^{c−1} φ_{pc}^{2}(X_{1}, …, X_{c}))

≤ E_{t} exp (2^{4c+4} b_{c} B_{t}^{c−1} a^{−1} t^{c+1} (\frac{x}{\sqrt{n}})^{c−1} |φ_{pc}|)
≤ E_{t} exp (2^{6c+4} b_{c} B_{t}^{c−1} a^{−1} t^{c+1} (\frac{x}{\sqrt{n}})^{c−1} |h|)
≤ E_{t} exp (\frac{a}{2}|h|) ,

as 2^{6c+5} b_{c} B_{t}^{c−1} t^{c+1} (x/\sqrt{n})^{c−1} ≤ a^{2} under the conditions of this lemma. Hence in (46),

1 − V_{c}^{dec}(u) ≤ 2e^{−(2a_{c}+1)tu} exp\{2^{9c} b_{c} (E_{t} h^{8})^{1/4} (E_{t} e^{\frac{a}{2} |h|}) t^{c+1} (\frac{x}{\sqrt{n}})^{c−2} u\}.

Since 2^{9c} b_{c} (E_{t} h^{8})^{1/4} (E_{t} e^{\frac{a}{2} |h|}) t^{c} (x/\sqrt{n})^{c−2} ≤ a_{c}, under the conditions of this lemma 1 − V_{c}^{dec}(u) ≤ 2e^{−(a_{c}+1)tu} (47) Estimate (44) follows from (45) and (47). This combined with (41)-(43) proves Lemma 6. Lemma 7. Under the conditions of Theorem 2

E_{t} e^{t |v_{n}(t)|} = O(1).

Proof. First we consider the case when Cramér’s condition (4) is satisfied and x ≤ δ\sqrt{n}/ ln_{l} n. By the inequality (37)

E_{t} e^{t |v_{n}(t)|} ≤ E_{t} e^{3 t |v_{n}^{f}(t)|} + E_{t} e^{3 t |vf̄ ; n(t)|} + E_{t} e^{3 t | ∑_{p=1}^{l−1} v_{n}^{φp}(t)|}. (48)

Let δ > 0 satisfy the condition of Lemma 4. Then the first expectation on the right side of (48) is O(1). Since δ\sqrt{n}/x ≥ ln_{l} n then in Lemma 5 e_{l} (δ\sqrt{n}/x) ≥ n and therefore the second expectation on the right side of (48) is O(1). All of the conditions of Lemma 6 are satisfied, since x n^{−1/2} → 0. Hence the third expectation on the right of (48) is also O(1) by Lemma 6.

Next we consider the case where h^{2} satisfies Cramér’s condition, that is, E exp (a_{0} h^{2}) < ∞ for some a_{0} > 0 instead of condition (4), and x = o(\sqrt{n}), as n → ∞. For this situation we will develop a bound as in the proof of Lemma 6. Using (37)

E_{t} e^{t |v_{n}(t)|} ≤ \frac{1}{m − 1} ∑_{c=2}^{m} E_{t} e^{(m−1) t |v_{nc}(t)|}
(49)  ≤ ∑_{c=2}^{m} E_{t} e^{m t |v_{nc}(t)|} I (|v_{nc}(t)| > n) + ∑_{c=2}^{m} E_{t} e^{m t |v_{nc}(t)|} I (|v_{nc}(t)| ≤ n) .

Here by (32) and convexity

E_{t} e^{m t |v_{nc}(t)|} I (|v_{nc}(t)| > n)

≤ e^{−x\sqrt{n}} E_{t} exp\{m (t + \frac{x}{\sqrt{n}}) |v_{nc}(t)|\}
≤ e^{−x\sqrt{n}} E_{t} exp\{2 m (t + \frac{x}{\sqrt{n}}) | ∑_{j=1}^{[n/c]} g_{ct}(X_{jc−c+1}, …, X_{jc}) | \}
≤ e^{−x\sqrt{n}} (E_{t} exp\{2 m (t + \frac{x}{\sqrt{n}}) g_{ct}(X_{1}, …, X_{c})\})^{[n/c]}

+e^{−x\sqrt{n}} (E_{t} exp\{−2 m (t + \frac{x}{\sqrt{n}}) g_{ct}(X_{1}, …, X_{c})\})^{[n/c]}

≤ 2e^{−x\sqrt{n}} exp\{m^{2} x^{2} (1 + t \frac{\sqrt{n}}{x})^{2} (E_{t} g_{ct}^{2})^{1/2}

× (E_{t} exp (4 m (t + \frac{x}{\sqrt{n}})) |g_{ct}|)^{1/2} \}

(50)  = o(1), as xn^{−1/2} → 0, x → ∞, n → ∞.

Further in (49) we have E_{t} e^{m t |v_{nc}(t)|} I (|v_{nc}(t)| ≤ n) ≤ 1 + m t ∫_{0}^{n} e^{mtu} (1 − V_{c}(u)) du, (51) where 1 − V_{c}(u) = P (|v_{nc}(t)| > u) .

By Chebyshev’s inequality 1 − V_{c}(u) ≤ e^{−(m+1)tu} E_{t} exp\{(m + 1) t u^{\frac{c−1}{c+1}} |v_{nc}(t)|^{2/(c+1)}\}. (52) Here

E_{t} exp\{(m + 1) t u^{\frac{c−1}{c+1}} |v_{nc}(t)|^{2/(c+1)}\}
= ∑_{k=0}^{∞} \frac{1}{k!} ((m + 1) t u^{\frac{c−1}{c+1}} )^{k} E_{t}|v_{nc}(t)|^{\frac{2k}{c+1}}
= ∑_{k=0}^{[(c+1)/2]} \frac{1}{k!} ((m + 1) t u^{\frac{c−1}{c+1}} )^{k} E_{t}|v_{nc}(t)|^{\frac{2k}{c+1}}

+ ∑_{[(c+1)/2]+1}^{∞} \frac{1}{k!} ((m + 1) t u^{\frac{c−1}{c+1}} )^{k} E_{t}|v_{nc}(t)|^{\frac{2k}{c+1}} , (53)

where by Hölder’s inequality

E_{t}|v_{nc}(t)|^{\frac{2k}{c+1}} ≤ (E_{t} v_{nc}^{2}(t))^{\frac{k}{c+1}} ≤ n^{− \frac{c−2}{c+1} k} (E g_{ct}^{2})^{\frac{k}{c+1}} , 0 ≤ k ≤ [(c + 1)/2], and for k ≥ [(c + 1)/2] + 1 by the upper decoupling inequality (34) and symmetrization

E_{t}|v_{nc}(t)|^{\frac{2k}{c+1}} ≤ E_{t} |\frac{(c − 1)! c^{c}}{(n − 1) ⋯ (n − c + 1)} ∑_{1≤i_{1}<···<i_{c}≤n} g_{ct}(X_{i_{1}}^{1}, …, X_{i_{c}}^{c})|^{\frac{2k}{c+1}}

≤ E_{t} |\frac{(c − 1)! c^{c} 2^{c}}{(n − 1) ⋯ (n − c + 1)} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}g_{ct}(X_{i_{1}}^{1}, …, X_{i_{c}}^{c})|^{\frac{2k}{c+1}} .

Hence in (53) E_{t} exp\{(m + 1) t u^{\frac{c−1}{c+1}} |v_{nc}(t)|^{2/(c+1)}\} (54)

≤ ∑_{k=0}^{[(c+1)/2]} \frac{1}{k!} ((m + 1) t u^{\frac{1}{c+1}} )^{k} (\frac{u}{n})^{\frac{c−2}{c+1} k} (E_{t} g_{ct}^{2})^{\frac{k}{c+1}}

+E exp\{(m + 1) t u^{\frac{c−1}{c+1}} |\frac{(c − 1)! c^{c} 2^{c}}{(n − 1) ⋯ (n − c + 1)} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}g_{ct}(X_{i_{1}}^{1}, …, X_{i_{c}}^{c})|^{\frac{2}{c+1}} \}.

Here

∑_{k=0}^{[(c+1)/2]} \frac{1}{k!} ((m + 1) t u^{\frac{1}{c+1}} )^{k} (\frac{u}{n})^{\frac{c−2}{c+1} k} (E_{t} g_{ct}^{2})^{\frac{k}{c+1}}

≤ exp\{(m + 1) t u^{\frac{1}{c+1}} (E_{t} g_{ct}^{2})^{\frac{1}{c+1}} \}. (55) Using inequality (36) with m = c, α = 2/(c + 1)

E exp\{(m + 1) t u^{\frac{c−1}{c+1}} |\frac{(c − 1)! c^{c} 2^{c}}{(n − 1) ⋯ (n − c + 1)} ∑_{1≤i_{1}<···<i_{c}≤n} ε_{i_{1}}^{1} ⋯ ε_{i_{c}}^{c}g_{ct}(X_{i_{1}}^{1}, …, X_{i_{c}}^{c})|^{\frac{2}{c+1}} \}

≤ 2E_{t} exp\{\frac{(m + 1)^{c−1}}{c + 1} (\frac{8c}{c + 1})^{c} t^{c+1} u^{c−1} (\frac{(c − 1)! c^{c} 2^{c}}{(n − 1) ⋯ (n − c + 1)})^{2}

× ∑_{1≤i_{1}<···<i_{c}≤n} g_{ct}^{2}(X_{i_{1}}^{1}, …, X_{i_{c}}^{c})}

≤ 2E_{t} exp\{\frac{(m + 1)^{c−1}}{c + 1} (\frac{8c}{c + 1})^{c} 2^{2(c−1)} (c − 1)! t^{c+1} u^{c−1} (\frac{(c − 1)! c^{c} 2^{c}}{(n − 1) ⋯ (n − c + 1)})^{2}

× ∑_{1≤i_{1}<···<i_{c}≤n} g_{ct}^{2}(X_{i_{1}}, …, X_{i_{c}})}, using (34),

≤ 2E_{t} exp\{(4m)^{5m} t^{c+1} (\frac{u}{n})^{c−1} ∑_{j=1}^{[n/c]} g_{ct}^{2}(X_{jc−c+1}, …, X_{jc})\},

using (32) and convexity,

≤ 2 (E_{t} exp\{(4m)^{5m} t^{c+1} (\frac{u}{n})^{c−1} g_{ct}^{2}(X_{1}, …, X_{c})\})^{n}
= 2 exp\{(4m)^{5m} t^{c+1} (\frac{u}{n})^{c−2} u Eg_{ct}^{2}\}

× (E_{t} exp\{(4m)^{5m} t^{c+1} (\frac{u}{n})^{c−1} (g_{ct}^{2}(X_{1}, …, X_{c}) − E g_{ct}^{2}) \})^{n}

≤ 2 exp\{(4m)^{5m} t^{c+1} (\frac{u}{n})^{c−2} u Eg_{ct}^{2}\} exp\{(4m)^{10m} t^{2(c+1)} (\frac{u}{n})^{2c−2}

×n (E_{t} (g_{ct}^{2} − E g_{ct}^{2})^{4})^{1/2} (E_{t} exp (2 (4m)^{5m} t^{c+1} (\frac{u}{n})^{c−1} |g_{ct}^{2} − E g_{ct}^{2}|))^{1/2} \}

≤ 2 exp{(4m)^{5m} t^{c+1} u Eg_{ct}^{2}}

× exp{4 (4m)^{10m} t^{2(c+1)} u (E_{t} g_{ct}^{4})^{1/2} E_{t} exp (2 (4m)^{5m} t^{c+1} g_{ct}^{2}) }. (56) Since xn^{−1/2} → 0 and E exp{a_{0}h^{2}} < ∞, then from (51)-(56) we obtain the estimate

E_{t} e^{mt|v_{nc}(t)|} I (|v_{nc}(t)| ≤ n) = O(1).

This combined with (49)-(50) proves Lemma 7.

Now we will apply Lemmas 4-7 to the estimation of T_{n}(t) . We introduce the following notation where the dependence on t has been suppressed. Let

S̃ = \frac{1}{σ_{t}\sqrt{n}} ∑_{i=1}^{n}(g_{t}(X_{i}) − μ_{t}),

ṽ_{n} = \frac{1}{σ_{t}\sqrt{n}} v_{n}(t), Φ_{n}(x) = P_{t}(S̃ + ṽ_{n} ≤ x), x ∈ R,

σ_{t}^{2} = E_{t}(g_{t}(X_{1}) − μ_{t})^{2} and x_{t} = \sqrt{n}tσ_{t}. Then T_{n}(t) can be written as

T_{n}(t) = E_{t}e^{−x_{t}S̃} I(S̃ + ṽ_{n} > 0).

With the help of (39) we have the following representation

T_{n}(t) = E_{t}e^{x_{t}ṽ_{n}} {e^{−x_{t}(S̃+ṽ_{n})} I(S̃ + ṽ_{n} > 0)}
= E_{t} {e^{−x_{t}(S̃+ṽ_{n})} I(S̃ + ṽ_{n} > 0)}
+ x_{t} ∫_{0}^{1} E_{t}ṽ_{n}e^{ux_{t}ṽ_{n}} {e^{−x_{t}(S̃+ṽ_{n})} I(S̃ + ṽ_{n} > 0)} du
(57)  = I_{n}(t) + t ∫_{0}^{1} I_{n}(u, t)du,

where

I_{n}(t) = E_{t} {e^{−x_{t}(S̃+ṽ_{n})} I(S̃ + ṽ_{n} > 0)} ,
I_{n}(u, t) = E_{t}v_{n}(t)e^{utv_{n}(t)} {e^{−x_{t}(S̃+ṽ_{n})} I(S̃ + ṽ_{n} > 0)} .

Estimate I_{n}(t).

By definition

I_{n}(t) = ∫ e^{−x_{t}y} I(y > 0) dΦ_{n}(y)
= ∫_{0}^{∞} e^{−x_{t}y}dΦ_{n}(y)
(58)  = ∫_{0}^{∞} e^{−x_{t}y}dΦ(y) + ∫_{0}^{∞} e^{−x_{t}y}d(Φ_{n}(y) − Φ(y)).

Here by (7), (23) and (39)

∫_{0}^{∞} e^{−x_{t}y}dΦ(y) = ∫_{0}^{∞} e^{−x(1+t·O(1))y}dΦ(y)
= ∫_{0}^{∞} e^{−xy}dΦ(y)
− ∫_{0}^{1} {xt · O(1) ∫_{0}^{∞} ye^{−xy−xtyu·O(1)}dΦ(y)}du.

Further,

∫_{0}^{∞} e^{−xy}dΦ(y) = e^{x^{2}/2} (1 − Φ(x))

and since t = \frac{x}{σ\sqrt{n}} (1 + O (\frac{x}{\sqrt{n}})) and e^{−y^{2}/2} ≤ 1

xt ∫_{0}^{∞} ye^{−xy−xtyu·O(1)}dΦ(y) ≤ \frac{x^{2}}{σ\sqrt{n}}(1 + O(1)) ∫_{0}^{∞} ye^{−(x+xtuO(1))y}dy.

After the substitution z = (x + xtu · O(1))y

xt ∫_{0}^{∞} ye^{−xy−xtyu·O(1)}dΦ(y)

≤ \frac{x^{2}}{σ\sqrt{n}}(1 + O(1))(x + xtu · O(1))^{−2} ∫_{0}^{∞} e^{−z}zdz
= e^{x^{2}/2}(1 − Φ(x)) · O (\frac{1 + x}{\sqrt{n}}) .

Consequently,

∫_{0}^{∞} e^{−x_{t}y}dΦ(y) = e^{x^{2}/2}(1 − Φ(x)) (1 + O (\frac{1 + x}{\sqrt{n}})) . (59)

Then we have in (58)

∫_{0}^{∞} e^{−x_{t}y}d(Φ_{n}(y) − Φ(y)) = −(Φ_{n}(0) − Φ(0)) + x_{t} ∫_{0}^{∞}(Φ_{n}(y) − Φ(y))e^{−x_{t}y}dy. By the normal approximation theorem for U-statistics (see Borovskikh (1996), (1998))

sup_{y}|Φ_{n}(y) − Φ(y)| ≤ A_{m}(a_{t} + b_{t})\frac{1}{\sqrt{n}}, (60)

where A_{m} is a positive constant depending only on m, and

a_{t} = σ_{t}^{−3} E_{t}|g_{t}(X_{1}) − μ_{t}|^{3},
b_{t} = ∑_{c=2}^{m} σ_{t}^{−δ_{c}} E_{t}|g_{ct}(X_{1}, …, X_{c})|^{δ_{c}}

with δ_{c} = (2c + 1)/(2c − 1).

By applying (6)-(8) and (23) and we have in (60)

a_{t} = σ^{−3} E|g(X)|^{3} (1 + O(\frac{x}{\sqrt{n}})),
b_{t} = ∑_{c=2}^{m} σ^{−δ_{c}} E|g_{c}(X_{1}, …, X_{c})|^{δ_{c}} (1 + O(\frac{x}{\sqrt{n}})),

as xn^{−1/2} → 0. Hence we get the following estimate

| ∫_{0}^{∞} e^{−x_{t}y}d(Φ_{n}(y) − Φ(y))| = e^{x^{2}/2}(1 − Φ(x)) O (\frac{1 + x}{\sqrt{n}}) . (61)

From (58), (59) and (61) we see that

I_{n}(t) = e^{x^{2}/2}(1 − Φ(x)) (1 + O (\frac{1 + x}{\sqrt{n}})) . (62)

Estimate I_{n}(u, t).

First we will prove that for any m ≥ 2 |I_{n}(u, t)| ≤ c_{1} (R(t) + R̄(t)) + c_{2}n^{−1/2}, (63) where

R(t) = E_{t}{e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + ṽ_{n2} + ε > 0)]},
R̄(t) = E_{t}{v_{n2}^{2}(t) [e^{−x_{t}(S̃+ṽ_{n2})} I (S̃ + ṽ_{n2} + ε > 0)] }

for some positive constants c_{i} and ε = n^{− \frac{1}{2}} . For 0 ≤ u ≤ 1 we have

|I_{n}(u, t)| ≤ E_{t}{(|v_{n2}(t)| + |r_{n}|)e^{t(|v_{n2}(t)|+|r_{n}|)} [e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + ṽ_{n2} + r̃_{n} > 0)]} where r_{n} = v_{n3}(t) + ⋯ + v_{nm}(t) and r̃_{n} = r_{n}/(σ_{t}\sqrt{n}).

Applying the inequalities e^{x} − 1 ≤ xe^{x}, x ≥ 0 with x = t|r_{n}| and r̃_{n} > −(S̃ + ṽ_{n2}) we get

|I_{n}(u, t)| ≤ E_{t}{|v_{n2}(t)| e^{t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + ṽ_{n2} + r̃_{n} > 0)]}

+E_{t}{|r_{n}|(1 + t|v_{n2}(t)|) exp(2t(|v_{n2}(t)| + |r_{n}|))}.

By Hölder’s inequality and Lemma 7

E_{t}{|r_{n}|(1 + t|v_{n2}(t)|) exp(2t(|v_{n2}(t)| + |r_{n}|)} ≤ c_{3} (E_{t}r_{n}^{2})^{1/2} .

Here

E_{t}r_{n}^{2} ≤ (m − 2)m^{m−2}n^{−1} ∑_{c=3}^{m} E_{t}|n^{−c/2}  ∑_{1≤i_{1}<···<i_{c}≤n}g_{ct}(X_{i_{1}}, …, X_{i_{c}})|^{2}
= (m − 2)m^{m−2}n^{−1} ∑_{c=3}^{m} \binom{n}{c}n^{−c}E_{t}g_{ct}^{2}(X_{1}, …, X_{c}).

Further write

E_{t}{|v_{n2}(t)|e^{t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + ṽ_{n2} + r̃_{n} > 0)]}
= E_{t}{|v_{n2}(t)|e^{t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + ṽ_{n2} + r̃_{n} > 0)I(|r̃_{n}| ≤ ε)]}
+E_{t}{|v_{n2}(t)|e^{t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + ṽ_{n2} + r̃_{n} > 0)I(|r̃_{n}| > ε)]}
≤ R(t) + R̄(t) + E_{t}{|v_{n2}(t)|e^{t(|v_{n2}(t)|+|r_{n}|)} I(|r̃_{n}| > ε)}
≤ R(t) + R̄(t) + σ_{t} E_{t}{|v_{n2}(t)| · |r_{n}| e^{t(|v_{n2}(t)|+|r_{n}|)}}.

The inequality (63) follows by applying Hölder’s inequality and Lemma 7.

Partitioning estimates. In what follows we shall estimate R(t) and R̄(t). We do this by partitioning v_{n2}(t) into several terms. We will give detailed estimates for R(t) only. The bounds for R̄(t) can be obtained by repeating the same method step by step. Now we will prove that

R(t) ≤ c_{4}x^{−1}. (64)

For n → ∞ let k = [n/2], k_{1} = [k/2], k_{2} = k − k_{1}, n_{1} = [(n − k)/2] and n_{2} = n − k − n_{1}, where [z] denotes the integer part of z. Then

v_{n2}(t) = v_{k}^{1} + v_{n−k}^{2} + v_{k_{1},n−k}^{3} + v_{k_{2},n−k}^{4}, (65)

where

v_{k}^{1} = \frac{m − 1}{n − 1} ∑_{1≤i_{1}<i_{2}≤k} g_{2t}(X_{i_{1}}, X_{i_{2}}),
v_{n−k}^{2} = \frac{m − 1}{n − 1} ∑_{k+1≤i_{1}<i_{2}≤n} g_{2t}(X_{i_{1}}, X_{i_{2}}),

v_{k_{1},n−k}^{3} = \frac{m − 1}{n − 1} ∑_{i_{1}=1}^{k_{1}} ∑_{i_{2}=k+1}^{n} g_{2t}(X_{i_{1}}, X_{i_{2}}),
v_{k_{2},n−k}^{4} = \frac{m − 1}{n − 1} ∑_{i_{1}=k_{1}+1}^{k} ∑_{i_{2}=k+1}^{n} g_{2t}(X_{i_{1}}, X_{i_{2}}).

Further let v_{k_{1},n−k}^{3} = v_{k_{1}n_{1}}^{31} + v_{k_{1}n_{2}}^{32}, (66) where

v_{k_{1}n_{1}}^{31} = \frac{m − 1}{n − 1} ∑_{i_{1}=1}^{k_{1}} ∑_{i_{2}=k+1}^{n_{1}} g_{2t}(X_{i_{1}}, X_{i_{2}}),
v_{k_{1}n_{2}}^{32} = \frac{m − 1}{n − 1} ∑_{i_{1}=1}^{k_{1}} ∑_{i_{2}=n_{1}+1}^{n} g_{2t}(X_{i_{1}}, X_{i_{2}}),

and v_{k_{2},n−k}^{4} = v_{k_{2}n_{1}}^{41} + v_{k_{2}n_{2}}^{42}, (67) where

v_{k_{2}n_{1}}^{41} = \frac{m − 1}{n − 1} ∑_{i_{1}=k_{1}+1}^{k} ∑_{i_{2}=k+1}^{n_{1}} g_{2t}(X_{i_{1}}, X_{i_{2}}),
v_{k_{2}n_{2}}^{42} = \frac{m − 1}{n − 1} ∑_{i_{1}=k_{1}+1}^{k} ∑_{i_{2}=n_{1}+1}^{n} g_{2t}(X_{i_{1}}, X_{i_{2}}).

We also define the corresponding partitioned terms for the normalized quantity ṽ_{n2}. For any real a, b and c we have the following inequality

I(a + b > c) ≤ I(2a > c) + I(2b > c). (68)

Hence by (65) and four applications of the inequality (68)

I(S̃ + ṽ_{n2} + ε > 0) ≤ I(S̃ + 2ṽ_{k}^{1} > 0)
+I(S̃ + 2ṽ_{n−k}^{2} + 2ṽ_{k_{1},n−k}^{3} + 2ṽ_{k_{2},n−k}^{4} + 2ε > 0)
≤ I(S̃ + 2ṽ_{k}^{1} > 0) + I(S̃ + 4ṽ_{n−k}^{2} > 0)
+I(S̃ + 4ṽ_{k_{1},n−k}^{3} + 4ṽ_{k_{2},n−k}^{4} + 4ε > 0)
≤ I(S̃ + 2ṽ_{k}^{1} > 0) + I(S̃ + 4ṽ_{n−k}^{2} > 0)
+I(S̃ + 8ṽ_{k_{1},n−k}^{3} > 0) + I(S̃ + 16ṽ_{k_{2},n−k}^{4} > 0)

+I(S̃ + 16ε > 0). (69)

Using (69) we can bound R(t) as follows

R(t) ≤ E_{t}{e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + 2ṽ_{k}^{1} > 0)]}
+E_{t}{e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + 4ṽ_{n−k}^{2} > 0)]}
+E_{t}{e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + 8ṽ_{k_{1},n−k}^{3} > 0)]}
+E_{t}{e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + 16ṽ_{k_{2},n−k}^{4} > 0)]}

+E_{t}{e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}I(S̃ + 16ε > 0)]}. (70)

In (70) each expectation has the same structure. Consider the first expectation in (70). By (37) and (65)

e^{2t|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}] = e^{2t|v_{n2}(t)|+tv_{k}^{1}−tv_{n−k}^{2}−tv_{k_{1},n−k}^{3}−tv_{k_{2},n−k}^{4}}e^{−x_{t}(S̃+2ṽ_{k}^{1})}
≤ ∑_{i=1}^{4} q_{i1}^{−1}e^{δ_{i1}|v^{i}|}[e^{−x_{t}(S̃+2ṽ^{1})}],

where for simplicity we write v^{1} = v_{k}^{1}, v^{2} = v_{n−k}^{2} and so forth. Hence from (70) we obtain

R(t) ≤ ∑_{i=1}^{4} ∑_{j=1}^{4} q_{ij}^{−1}Q_{ij} + ∑_{i=1}^{4} q_{i}^{−1}Q_{i}, (71)

where

Q_{ij} = E_{t}{e^{δ_{ij}t|v^{i}|}[e^{−x_{t}(S̃+2^{j}ṽ^{j})}I(S̃ + 2^{j}ṽ^{j} > 0)]},
Q_{i} = E_{t}{e^{δ_{i}t|v^{i}|}[e^{−x_{t}S̃}I(S̃ + 16ε > 0)]},

δ_{i} and δ_{ij} are positive constants, and ε = n^{−1/2}.

We shall use (66) and (67) to further partition the expectations when i or j takes the value 3 or 4. Thus using (37), for some constants δ_{j}^{i},

Q_{31} ≤ E_{t}{e^{δ_{1}^{1}t|v^{31}|}[e^{−x_{t}(S̃+2ṽ^{1})}I(S̃ + 2ṽ^{1} > 0)]}

+E_{t}{e^{δ_{1}^{2}t|v^{32}|}[e^{−x_{t}(S̃+2ṽ^{1})}I(S̃ + 2ṽ^{1} > 0)]}, (72)

with a similar expression for Q_{41}. For terms like Q_{13} and Q_{14} we have

Q_{13} ≤ E_{t}{e^{δ_{2}^{1}t|v^{1}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}
+E_{t}{e^{δ_{2}^{2}t|v^{1}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}
+E_{t}{e^{δ_{2}^{3}t|v^{31}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}

+E_{t}{e^{δ_{2}^{4}t|v^{31}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}
+E_{t}{e^{δ_{2}^{5}t|v^{32}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}

+E_{t}{e^{δ_{2}^{6}t|v^{32}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}, (73)

and for terms like Q_{34} and Q_{43} we have

Q_{43} ≤ E_{t}{e^{δ_{3}^{1}t|v^{41}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}
+E_{t}{e^{δ_{3}^{2}t|v^{41}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}
+E_{t}{e^{δ_{3}^{3}t|v^{42}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}
+E_{t}{e^{δ_{3}^{4}t|v^{42}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}
+E_{t}{e^{δ_{3}^{5}t|v^{31}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}
+E_{t}{e^{δ_{3}^{6}t|v^{31}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}
+E_{t}{e^{δ_{3}^{7}t|v^{32}|}[e^{−x_{t}(S̃+16ṽ^{31})}I(S̃ + 16ṽ^{31} > 0)]}

+E_{t}{e^{δ_{3}^{8}t|v^{32}|}[e^{−x_{t}(S̃+16ṽ^{32})}I(S̃ + 16ṽ^{32} > 0)]}. (74)

All of the terms we need to bound to obtain (64) have similar structure. Let

Q = E_{t}{e^{δt|Δ_{n}|}[e^{−x_{t}(ξ_{n}+η_{n})}I(ξ_{n} + η_{n} > 0)]}, (75)

where

ξ_{n} = \frac{1}{σ_{t}\sqrt{n}} ∑_{j∈J} g_{t}(X_{j}) + Δ̃_{n1},

η_{n} = \frac{1}{σ_{t}\sqrt{n}} ∑_{j∈J̄}g_{t}(X_{j}) + Δ̃_{n2},

Δ_{n} is part of the sum v_{n}, Δ̃_{n1} and Δ̃_{n2} are parts of the normalized sum ṽ_{n}, and J̄ = {1, …, n}\J. The set of indices J has cardinality |J| ∼ λn, 0 < λ < 1 as n → ∞. Here the random variable ξ_{n} is independent of Δ_{n} and η_{n}.

The expectations Q_{i} in (71) have a simpler form than (75). All expectations (72) - (74) have the structure (75). The following lemma provides a bound for Q in (75). Lemma 8. Under the conditions of Theorem 2

Q ≤ c_{5}x^{−1} + c_{6}n^{−1/2}

for some positive constants c_{5} and c_{6}. Proof. Let λ_{n} = (|J|/n)^{1/2} and

ξ̃_{n} = \frac{1}{σ_{t}\sqrt{|J|}} ∑_{j∈J} g_{t}(X_{j}) + λ_{n}^{−1}Δ̃_{n1}

and Φ̃_{n}(u) = P (ξ̃_{n} ≤ u), u ∈ R. Further, in (75), since ξ_{n} is independent of Δ_{n} and η_{n} we can write Q = E_{t}{e^{δt|Δ_{n}|−x_{t}η_{n}}E^{ξ}e^{−x_{t}ξ_{n}}I(ξ_{n} + η_{n} > 0)}, (76) where E^{ξ}{⋯} denotes the expectation with respect to ξ_{n}. Here (see the proof of (62)),

E^{ξ}e^{−x_{t}ξ_{n}}I(ξ_{n} + η_{n} > 0)
= ∫_{−∞}^{∞} e^{−x_{t}λ_{n}u}I(λ_{n}u + η_{n} > 0)dΦ̃_{n}(u)
(77)  = ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}d(Φ̃_{n}(u) − Φ(u)) + ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}dΦ(u).

In (77) ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}d(Φ̃_{n}(u) − Φ(u))

= −e^{x_{t}η_{n}}(Φ̃_{n}(−η_{n}λ_{n}^{−1}) − Φ(−η_{n}λ_{n}^{−1})) + x_{t}λ_{n} ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}(Φ̃_{n}(u) − Φ(u))du

and by the inequality (60)

| ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}d(Φ̃_{n}(u) − Φ(u))| ≤ c_{7}e^{x_{t}η_{n}} \frac{1}{\sqrt{n}}.

Further in (77)

∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}dΦ(u) = \frac{1}{\sqrt{2π}} ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}e^{−u^{2}/2}du
≤ ∫_{−η_{n}λ_{n}^{−1}}^{∞} e^{−x_{t}λ_{n}u}du
= (x_{t}λ_{n})^{−1}e^{x_{t}η_{n}},

where x_{t} ∼ x, λ_{n} ∼ λ as n → ∞. Hence in (76)

Q ≤ (c_{7} \frac{1}{\sqrt{n}} + c_{8} \frac{1}{x})Ee^{δt|Δ_{n}|}. (78)

Note that for the expectation of Q_{i} in (71) we can replace (78) by the inequality

Q ≤ (c_{9} \frac{1}{\sqrt{n}} + c_{10} \frac{1}{x}) e^{δ^{1}εx_{t}}Ee^{δt|Δ_{n}|}. (79)

From (78)-(79) and Lemma 7 we obtain the proof of Lemma 8, and hence the desired estimate (64). Combining (28)-(29), (57) and (62)-(64) completes the proof of Theorem 2. Proof of Theorem 3. Define the truncated kernel h̄ = h I (|h| ≤ n^{\frac{1}{2} +α}) and introduce the U-statistic Ū_{n} with this kernel h̄. In what follows μ̄, σ̄, t̄, ψ̄, … denote μ, σ, t, ψ, … respectively, where, instead of the kernel h we substitute the truncated kernel h̄. For example,

ḡ(x) = E (h̄(X_{1}, …, X_{m})|X_{m} = x) ,
μ̄ = E h̄(X_{1}, …, X_{m}),
σ̄^{2} = E (ḡ(X) − μ̄)^{2} .

Lemma 9. Under Linnik’s condition (12) for 1 ≤ x ≤ o(n^{α})

P (U_{n} − μ n/m > xσ\sqrt{n}) − P (Ū_{n} − μ̄ n/m > xσ̄\sqrt{n})

= (1 − Φ(x)) exp\{\frac{x^{3}}{\sqrt{n}} λ_{m}^{[s]} (\frac{x}{\sqrt{n}}) \} O (\frac{x}{\sqrt{n}}) .

Proof. It is not difficult to prove (see, for example, Borovskikh (1998)) that

|P (U_{n} − μ n/m > xσ\sqrt{n}) − P (Ū_{n} − μ̄ n/m > xσ̄\sqrt{n}) |

≤ \frac{1}{2} n (n − 1) P (|h| > n^{\frac{1}{2} +α}) ,

and

P (|h| > n^{\frac{1}{2} +α}) ≤ e^{−a_{α} n^{2α}} E exp\{a_{α} |h|^{\frac{4α}{2α+1}} \}.

Since 1 ≤ x ≤ o(n^{α}) then

e^{−a_{α} n^{2α}} = e^{−a_{α} n^{2α}/2} exp\{\frac{x^{3}}{\sqrt{n}} λ_{m}^{[s]} (\frac{x}{\sqrt{n}}) − \frac{x^{2}}{2} \}

× exp\{−n^{2α} [\frac{a_{α}}{2} − (\frac{x}{n^{α}} )^{2} (\frac{1}{2} − \frac{x}{\sqrt{n}} λ_{m}^{[s]} (\frac{x}{\sqrt{n}}))] \}

= e^{−a_{α} n^{2α}/2} exp\{\frac{x^{3}}{\sqrt{n}} λ_{m}^{[s]} (\frac{x}{\sqrt{n}}) \}(1 − Φ(x)) · O(1).

This proves Lemma 9. Lemma 10. If 1 ≤ x ≤ o(n^{α}) and Linnik’s condition (12) is satisfied then

P (Ū_{n} − μ̄ n/m > xσ̄\sqrt{n})

= (1 − Φ(x)) exp\{\frac{x^{3}}{\sqrt{n}} λ_{m}^{[s]} (\frac{x}{\sqrt{n}}) \}(1 + O (\frac{x}{\sqrt{n}})) .

Proof. We can apply Theorem 2. Under our new conditions we take a = a_{α} n^{− \frac{1}{2} +α}. Then the connection between Cramér’s condition (4) and Linnik’s condition (12) is given by the inequality

E exp\{a|h̄|\}≤ E exp\{a_{α}|h|^{\frac{4α}{2α+1}} \}.

This guarantees that the key results of Lemma 1 and Lemma 7 hold. By analogy with (29)

n (ψ̄(t̄) − t̄μ̄t̄) = −\frac{x^{2}}{2} + \frac{x^{3}}{\sqrt{n}} λ̄_{m} (\frac{x}{\sqrt{n}}) .

Hence by virtue of Theorem 2 for 1 ≤ x ≤ o(n^{α}) under the Linnik’s condition (12)

P (Ū_{n} − μ̄ n/m > xσ̄\sqrt{n})

= (1 − Φ(x)) exp\{\frac{x^{3}}{\sqrt{n}} λ̄_{m} (\frac{x}{\sqrt{n}}) \}(1 + O (\frac{x}{\sqrt{n}}))

with the Cramér series

λ̄_{m}(u) = ∑_{k=0}^{∞} λ̄_{mk} u^{k}

which converges for 0 ≤ u ≤ δ n^{− \frac{1}{2} +α} with sufficiently small δ > 0 and which is obtained from the Cramér series (11) where the coefficients λ̄_{mk}, depending on the moments of the truncated kernel h̄, are used instead of the coefficients λ_{mk}. It is straightforward to proceed from here to obtain the statement of Lemma 10. Theorem 3 follows directly from Lemmas 9 and 10.

REFERENCES

Aleshkevichiene, A.K. (1990). Probabilities of large deviations for U-statistics and von Mises functionals. Theory Prob. Appl. 35, 1-14.

Aleshkevichiene, A.K. (1992). Large deviations for U-statistics. Liet. Matem. Rink. 32, 7-19.

Arcones, M.A. and Giné, E. (1993). Limit theorems for U-processes. Ann. Probab. 21, 1494-1542.

Arcones, M.A. (1995). A Bernstein-type inequality for U-statistics and U-processes. Statist. and Probab. Letters. 22, 239-247.

Borell, C. (1979). On the integrability of Banach space valued Walsh polynomials. Seminaire de Probabilités XIII. Lecture Notes in Math. 721, 1-3. Springer, New York.

Borovskikh, Yu.V. (1996). U-statistics in Banach Spaces. VSP, Utrecht, The Netherlands, xii + 420 p.

Borovskikh, Yu.V. (1998). Sharp estimates of the rate of convergence for Ustatistics. Report 98-21, School of Mathematics and Statistics, University of Sydney. +42p.

Borovskikh, Yu.V. and Weber, N.C. (2000). On large deviations of U-statistics. Report 00-4, School of Mathematics and Statistics, University of Sydney. +25p.

Borovskikh, Yu.V. and Weber, N.C. (2001). Large deviation results for a Ustatistical sum with product kernel. Bull. Austral. Math. Soc. 63.(To appear)

Cramér, H. (1938). Sur un nouveaux théorème limit de la théorié des probabilités. Actualités Scientifiques et Industrielles, Paris, 736, 5-23.

Ghosh, M. (1974). Probabilities of moderate deviations under m-dependence. Canad. J. Statist. 2, 157-168.

Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58, 13-30.

Inglot, T., Kallenberg, W.C.M. and Ledwina, T. (1992). Strong moderate deviation theorems. Ann. Probab. 20, 987-1003.

Inglot, T. and Ledwina, T. (1993). Cramér type large deviations for some Ustatistics. Theory Probab. Appl. 38, 858-868.

Keener, R.W., Robinson, J., and Weber, N.C. (1998). Tail probability approximations for U-statistics. Statist. and Probab. Letters, 37, 59-65.

Lang, S. (1994). Real and Functional Analysis. Springer-Verlag, New York, 3rd edition.

Ledoux, M. and Talagrand, M. (1991). Probability in Banach Spaces. Springer-Verlag, New York.

Malevich, T.L. and Abdalimov, B. (1979). Probabilities of large deviations for U-statistics. Theory Probab. Appl. 24, 215-219.

de la Peña, V. (1992). Decoupling and Khintchine’s inequalities for U-statistics. Ann. Probab. 20, 1877-1892.

Rubin, H. and Sethuraman, J. (1965). Probabilities of moderate deviations. Sankhya A, 27, 325-346.

Slastnikov, A.D. (1978). Limit theorems for the probabilities of moderate deviations. Theory Probab. Appl. 23, 340-357.

Vandemaele, M. (1982). On large deviation probabilities for U-statistics. Theory Probab. Appl. 27, 614.

Wang Qiying (1996). Probabilities of large deviations for U-statistics. Journal of Nanjing University. Mathematical Biquarterly. 13, 168-172.

Whittaker, E.T. and Watson, G.N. (1927). A Course of Modern Analysis. Cambridge University Press, 4th edition.

Department of Applied Mathematics Transport University Moskovsky Avenue, 9 190031, St.Petersburg, Russia e-mail:borovski@spb.cityline.ru School of Mathematics and Statistics, FO7 University of Sydney NSW 2006, Australia e-mail:neville@maths.usyd.edu.au