On Large Deviations of U-Statistics

Yuri V. Borovskikh Transport University St Petersburg

Neville C. Weber University of Sydney Sydney

January 11, 2000

Large deviation results with explict order terms and Cramér’s series are developed for non-degenerate U-statistics of degree m with bounded kernels using the contraction technique of Keener, Robinson and Weber (1998) and a partitioning method to bound the degenerate remainder term.

1 Introduction and Results.

Let X_{1}, ⋯, X_{n} be independent and identically distributed random variables 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 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},

where

μ = Eh(X_{1}, ⋯, X_{m}),

AMS 1991 subject classification. Primary 60F10. Key words and phrases. Large deviations, U-statistics, Cramer’s series.

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 possessing the degeneracy property Eg_{c}(x_{1}, …, x_{c−1}, X_{c}) = 0 a.s., c = 2, …, m.

Let σ^{2} = E(g(X_{1}) − μ)^{2} and assume 0 < σ^{2} < ∞. By the central limit theorem for non-degenerate U-statistics,

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

uniformly in x as n → ∞, provided

t^{γ_{c}}P (|g_{c}(X_{1}, …, X_{c})| > t) → 0 as t → ∞

for each c = 2, …, m, where γ_{c} = 2c/(2c−1) and Φ(x) denotes the standard normal distribution function.

We are interested in the relative error o(1) in

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

as x tends to infinity together with n . In what follows, without loss of generality, we take μ = 0.

We will develop the new contraction technique proposed by Keener, Robinson and Weber (1998) for U-statistics of degree 2 to establish Cramér’s series for large deviation probabilities for U-statistics of any degree m. We find the explicit solution 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 the Cramér’s series with coefficients in explicit form. Further we use a new partitioning method to handle the error term. The degenerate part of the U-statistic is expressed as a sum of separate terms. This partitioning enables us to bound the required expectation by the sum of several terms where in each term we can identify a sum that is independent of all other components in that term. We then use this independence to bound the necessary expectations.This new result also enables the range of x values for which the expansion in Keener et al. holds to be extended to x = o (\sqrt{n}). Aleshkevichiene (1990) established large deviation results for U-statistics of degree 2 with bounded kernels with the help of the cumulant method. In their Theorem 3 instead of the full Cramér’s series they have only a truncated version.

Let C = {g : ∥ g ∥_{∞}≤ c}, where ∥ · ∥_{∞} denotes the essential supremum. If d(g_{0}, g_{1}) =∥ g_{0} − g_{1} ∥_{∞} , then (C, d) is a complete metric space. For g, h ∈ C define the operator H_{t}^{m−1} : g → H_{t}^{m−1}g, 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_{1})})^{m−1}}, t ∈ R,

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

As in Keener et al. (1998) we can to show that the operator H_{t}^{m−1} is a contraction if 2(m−1)c|t| exp(2(m−1)c|t|) < 1. Therefore from the contraction mapping theorem (Lemma 14.1.1 in Lang (1994)) it follows that the contraction equation g = H_{t}^{m−1}g has an essentially unique solution g_{t} ∈ C , i.e. g_{t} = H_{t}^{m−1}g_{t}. (1)

Our first result relates to the equation (1). We give the contraction solution g_{t}(x) of (1) in the form of an analytic function in the parameter t. To formulate this result we need some notation. 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_{1}) ,
β_{2} = (m − 1)Ec_{2} (X_{1}) + \frac{1}{2}(m − 1)Ec_{1}^{2} (X_{1}) + \binom{m − 1}{2} (Ec_{1}(X_{1}))^{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})

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

Theorem 1. Let ∥ h ∥_{∞}= c < ∞. Then for all x ∈ X and k = 1, 2, …

| c_{k}(x) |≤ E | h(X_{1}, …, X_{m−1}, x) | (c(m − 1))^{k−1} · 10^{k} (3)

and the function

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

is the unique analytical solution of the contraction equation (1) in the region 0 ≤ t < (10c(m − 1))^{−1}. Further

| g_{t}(x) − g(x) |≤ E | h(X_{1}, …, X_{m−1}, x) | (10c(m − 1)t) (1 − 10c(m − 1)t)^{−1} . (5)

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

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

and, hence, the estimate (5) is true by virtue of (3). Moreover, throughout what follows we assume that m ≥ 2 since in the case m = 1 we have g_{t}(x) = g(x) for all t > 0. Theorem 2. Let ∥ h ∥_{∞}= c < ∞ and σ^{2} = Eg^{2}(X_{1}) > 0. Suppose that x = o(\sqrt{n}), n → ∞. Then

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}})) (6)

with Cramér’s series

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

where

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

with

δ = (400em(\frac{ce}{σ})^{3}) (1 + 20ecm).

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

2 Proofs.

Proof of Theorem 1. The following lemma provides the inequalities needed to establish (3). Lemma 1. If ∥ h ∥_{∞}= c < ∞, then for all k = 1, 2, …

| c_{k}(x) |≤ c(x) (c(m − 1))^{k−1} γ_{k}, x ∈ X (8)

where

c(x) = E | h(X_{1}, …, X_{m−1}, x) |,
γ_{k+1} = \frac{1}{k + 1} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!}((k + 1)α_{s})^{ν_{s}}, k ≥ 1,

γ_{1} = 1, α_{1} = 2 and

α_{k} = ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k}(ν_{1} + … + ν_{k} − 1)!∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{1}{s!})^{ν_{s}}, k ≥ 2.

Proof. We will use induction on k. Clearly

| c_{1}(x) | ≤ c(x)γ_{1},
| c_{2}(x) | ≤ c(x)c(m − 1)γ_{2}

since γ_{1} = 1 and γ_{2} = 2.

Now suppose that the inequalities (8) are valid for s = 1, …, k − 1, that is,

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

Further we write by virtue of (2)

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

where by the induction hypothesis

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

and

|β_{l}| ≤ ∑_{ν_{1}+2ν_{2}+...+lν_{l}=l} ∏_{s=1}^{l} \frac{1}{ν_{s}!}\{(c(m − 1))^{s} γ_{s}\}^{ν_{s}}
= (c(m − 1))^{l} ∑_{ν_{1}+2ν_{2}+...+lν_{l}=l} ∏_{s=1}^{l} \frac{1}{ν_{s}!}γ_{s}^{ν_{s}}
= (c(m − 1))^{l} ā_{l},

and also

| b_{l} | ≤ ∑_{ν_{1}+2ν_{2}+...+lν_{l}=l} (ν_{1} + … + ν_{l})! ∏_{s=1}^{l} \frac{1}{ν_{s}!}\{(c(m − 1))^{s} ā_{s}\}^{ν_{s}}
= (c(m − 1))^{l} ∑_{ν_{1}+2ν_{2}+...+lν_{l}=l} (ν_{1} + … + ν_{l})! ∏_{s=1}^{l} \frac{1}{ν_{s}!}ā_{s}^{ν_{s}}
= (c(m − 1))^{l} b̄_{l},

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

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

It is sufficient to show that in (9)

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

Let

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

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

γ(z) = ∑_{k=1}^{∞} (∑_{l=0}^{k−1} ā_{l} b̄_{k−l−1}) z^{k} = z ∑_{k=0}^{∞} (∑_{l=0}^{k} ā_{l} b̄_{k−l}) z^{k}
= 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} ∏_{s=1}^{k} \frac{1}{ν_{s}!}γ_{s}^{ν_{s}} ) z^{k} = e^{γ(z)}

and

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

Therefore from (10) we obtain the equation for the generating function

γ(z) = z \frac{e^{γ(z)}}{2 − e^{γ(z)}} , γ(0) = 0. (11)

Denote ϕ(y) = y − ln(2 − e^{y}), |y| < ln 2. (12) Then equation (11) is reduced to the form

γ(z) = z exp{ϕ(γ(z))}. (13)

Here

ϕ(y) = ∑_{k=1}^{∞} α_{k}y^{k}, |y| < ln 2, (14)

where

α_{1} = 2,
α_{k} = ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k}(ν_{1} + … + ν_{k} − 1)!∏_{s=1}^{k} \frac{1}{ν_{s}!} (\frac{1}{s!})^{ν_{s}}, k ≥ 2.

This expansion follows from

ϕ(y) = y − ln (1 − ∑_{k=1}^{∞} \frac{1}{k!}y^{k}) = ∑_{k=1}^{∞} α_{k}y^{k}.

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

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

with γ_{1} = 1 and

γ_{k+1} = \frac{1}{k + 1} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!} ((k + 1)α_{s})^{ν_{s}}, k ≥ 1.

According to (10) - (15) this proves Lemma 1. Now we show that γ_{k} ≤ 10^{k}, k ≥ 1. (16)

Write for all k ≥ 1

γ_{k+1} = \frac{2^{k}}{k + 1} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!} ((k + 1)\frac{α_{s}}{2^{s}} )^{ν_{s}}
≤ 2^{k} ∏_{s=1}^{k} \{ ∑_{ν_{s}=0}^{∞} \frac{1}{ν_{s}!} ((k + 1)\frac{α_{s}}{2^{s}} )^{ν_{s}} \}
= 2^{k} ∏_{s=1}^{k} exp \{(k + 1)\frac{α_{s}}{2^{s}} \}
≤ 2^{k} exp \{(k + 1)ϕ(\frac{1}{2})\}
≤ (\frac{2\sqrt{e}}{2 − \sqrt{e}})^{k+1} ≤ 10^{k+1}.

From (8) and (16) we get the estimate (3). Lemma 2. If 0 ≤ t < (10c(m − 1))^{−1} then the function g_{t}(x) defined in (4) is the solution of the contraction equation (1). Proof. Denote z_{t}(x) = t g_{t}(x) and rewrite the contraction 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_{1})})^{m−1}}. (17)

We must prove that the analytical function

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

satisfies equation (17). The numerator in (17) has the 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 (17) has the expansion

(Ee^{z_{t}(X_{1})})^{−(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_{1})})^{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_{1})})^{m−1}} = ∑_{k=1}^{∞} \{∑_{l=0}^{k−1} a_{l}(x) b_{k−l−1}\}t^{k}. (19)

Comparing (17) - (19) 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_{1})}

and F is the distribution function of X_{1}. 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}.

In the following we will need in the solution of the saddle-point equation

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

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

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

is a convergent power series with π_{1} = 1 and coefficients π_{k}, k ≥ 2 specified at (23). 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})\}}.

With the help of (4) 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 (3)

|d_{k}(h)| ≤ c(10c m)^{k} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!}
≤ c(10c m)^{k} ∏_{s=1}^{k} \{ ∑_{ν_{s}=0}^{∞} \frac{1}{ν_{s}!}\} = c(10ecm)^{k}, 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{c}{mσ^{2}} (10ecm)^{s+1})^{ν_{s}}
= (10ecm)^{k} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k}(ν_{1} + … + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}(\frac{10ec^{2}}{σ^{2}} )^{ν_{s}}
= (10ecm)^{k}(\frac{10ec^{2}}{σ^{2}} )(1 + \frac{10ec^{2}}{σ^{2}} )^{k−1}, k ≥ 1.

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}!}(10ecm)^{sν_{s}}
= (10ecm)^{k} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k}(ν_{1} + … + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}
= (10ecm)^{k}2^{k−1}, k ≥ 1.

Hence the equation (20) is reduced to the form

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

where

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

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

|D_{k}| ≤ 2^{k}(10ecm)^{k}(10e(\frac{c}{σ})^{2})^{k}, k ≥ 1.

By the Lagrange expansion we have the solution of equation (22)

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

where π_{1} = 1 and

π_{k+1} = \frac{1}{k + 1} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!} ((k + 1)D_{s})^{ν_{s}}, k ≥ 1, (23)

and due to (3)

|π_{k+1}| ≤ \frac{1}{k + 1} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!} ((k + 1)(200cm(\frac{ce}{σ})^{2})^{s})^{ν_{s}}
= \frac{1}{k + 1}(400cm(\frac{ce}{σ})^{2})^{k} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} ∏_{s=1}^{k} \frac{1}{ν_{s}!} ((k + 1)(\frac{1}{2})^{s})^{ν_{s}}

≤ \frac{1}{k + 1}(400cm(\frac{ce}{σ})^{2})^{k} ∏_{s=1}^{k} \{ ∑_{ν_{s}=0}^{∞} \frac{1}{ν_{s}!} ((k + 1)(\frac{1}{2})^{s})^{ν_{s}} \}
≤ \frac{1}{k + 1}(400cm(\frac{ce}{σ})^{2})^{k} ∏_{s=1}^{k} exp \{(k + 1)(\frac{1}{2})^{s}\}
≤ \frac{1}{k + 1}(400cm(\frac{ce^{2}}{σ})^{2})^{k}, 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}),
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}}),

g_{t}(x) = E_{t}(h(X_{1}, ⋯, X_{m−1}, X_{m})|X_{m} = x),

where g_{ct} : X^{c} → R, c = 2, ⋯, m, are canonical functions satisfying E_{t}g_{ct}(x_{1}, ⋯, x_{c−1}, X_{c}) = 0, a.s. and X_{1}, X_{2}, ⋯ are independent random variables all with an identical distribution function F_{t} .

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

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})]
(24) = 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)].

Due to (4) we have in (24) the following expansions for sufficiently small t

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

where

G_{k} = ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k} E ∏_{s=1}^{k} \frac{1}{ν_{s}!}c_{s}^{ν_{s}}(X_{1}),

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

and by virtue of (3) for k ≥ 1

|G_{k}| ≤ (10ecm)^{k} and |H_{k}| ≤ (10ecm)^{k}2^{k−1}.

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

ψ(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 (3)

|ψ_{k}| ≤ \frac{1}{2} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})!(20ecm)^{ν_{1}+···+ν_{k}} ∏_{s=1}^{k} \frac{1}{ν_{s}!}((400cm(\frac{ce^{2}}{σ})^{2})^{s})^{ν_{s}}

= \frac{1}{2}(400cm(\frac{ce^{2}}{σ})^{2})^{k} ∑_{ν_{1}+2ν_{2}+...+kν_{k}=k}(ν_{1} + ⋯ + ν_{k})! ∏_{s=1}^{k} \frac{1}{ν_{s}!}(20ecm)^{ν_{s}}

≤ (400cm(\frac{ce^{2}}{σ})^{2})^{k}(20ecm)(1 + 20ecm)^{k−1}, k ≥ 1.

Thus we have established that if g_{t}(x) is the contraction function of the form (4) and t = t (\frac{x}{σ\sqrt{n}}) is the solution of the saddle-point equation (20) then in (24) the following expansion is true

n(ψ(t) − tμ_{t}) = nψ (t (\frac{x}{σ\sqrt{n}})) − mt (\frac{x}{σ\sqrt{n}}) xσ\sqrt{n}
(25)  = −\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 Cramér’s series (7) with the coefficients

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

which satisfy the inequality

|λ_{mk}| ≤ 2 (400em(\frac{ce}{σ})^{3}(1 + 20ecm))^{k+3} .

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

v_{ns}(t) = \frac{(m − 1) ⋯ (m − s + 1)}{(n − 1) … (n − s + 1)} ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}}).

Then

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

Lemma 4. For all integers n ≥ m, m ≥ 2, all distribution functions, F_{t}, and all kernels h such that ∥ h ∥_{∞}≤ c

E_{t} exp{δ|v_{n}(t)|} ≤ d

for some positive constants δ and d depending only on m and c. Proof. Write

E_{t} exp{δ|v_{n}(t)|} ≤ E_{t} ∏_{s=2}^{m} exp{δ|v_{ns}(t)|}
≤ ∑_{s=2}^{m} q_{s}^{−1}E_{t} exp{δq_{s}|v_{ns}(t)|},

since for any x_{i} ∈ R and q_{2}^{−1} + ⋯ + q_{m}^{−1} = 1,

|x_{2} ⋯ x_{m}| ≤ q_{2}^{−1}|x_{2}|^{q_{2}} + ⋯ + q_{m}^{−1}|x_{m}|^{q_{m}}. (26)

By the inequality of Arcones and Giné (1993) for any x > 0 there are constants γ_{i} depending only on s such that for all kernels h with ∥ h ∥_{∞}≤ c

P_{t}(|n^{− \frac{s}{2}} ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}})| > x) ≤ γ_{1} exp(−γ_{2}(x/c)^{2/s}).

Hence,

E_{t} exp{δn^{−1}| ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}})|^{2/s}} ≤ d < ∞,

for some positive constants δ and d. Further, for all s ≥ 2 and n ≥ m

|v_{ns}(t)| ≤ δ(m)|n^{−s+1} ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}})|
= δ(m)[n^{−s+2}| ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}})|^{(s−2)/s}]

× [n^{−1}| ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}})|^{2/s}]

≤ δ_{1}(m)c^{(s−2)/s}[n^{−1}| ∑_{1≤i_{1}<···<i_{s}≤n} g_{st}(X_{i_{1}}, …, X_{i_{s}})|^{2/s}].

This proves the desired result.

Now we will apply Lemma 4 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}, 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).

Further we will use the formula

e^{z} = ∑_{k=0}^{r−1} \frac{z^{k}}{k!} + \frac{z^{r}}{(r − 1)!} ∫_{0}^{1} (1 − u)^{r−1}e^{uz}du, (27)

which is valid for all complex z and positive integers r = 1, 2, …. With the help of (27) 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
(28)  = 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)
(29)  = ∫_{0}^{∞} e^{−x_{t}y}dΦ(y) + ∫_{0}^{∞} e^{−x_{t}y}d(Φ_{n}(y) − Φ(y)).

Here by (4), (21) and (27)

∫_{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}})) . (30)

Then we have in (29)

∫_{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}}, (31)

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

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

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

By applying (4), (21) and (31) we have

a_{t} ≤ 2^{3}c^{3}σ^{−3/2}(1 + t · O(1)),
b_{t} ≤ ∑_{s=2}^{m}(2^{s+1}c)^{δ_{s}}σ^{−δ_{s}}(1 + t · O(1)).

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}}) . (32)

From (29), (30) and (32) we see that

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

Estimate I_{n}(u, t).

First we will prove that for any m ≥ 2

|I_{n}(u, t)| ≤ c_{1}R(t) + c_{2} \frac{1}{\sqrt{n}}, (34)

where

R(t) = E_{t}{e^{c_{3}|v_{n2}(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, since x ≤ exp(x), x > 0,

|I_{n}(u, t)| ≤ c_{1}^{−1}E_{t}{e^{(c_{1}+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 = (c_{1} + t)|r_{n}| and r̃_{n} > −(S̃ + ṽ_{n2}) we get

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

By Hölder’s inequality and Lemma 4

E_{t}\{|r_{n}| exp((c_{1} + t)|v_{n2}(t)| + (c_{1} + 2t)|r_{n}|)\} ≤ (E_{t}r_{n}^{2})^{\frac{1}{2}} \sqrt{d}.

Here

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

Further write

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

Since

(n^{1/2}|r_{n}|)^{2/3} ≤ δ_{2}(m) ∑_{s=3}^{m}(n^{−1}| ∑_{1≤i_{1}<···<i_{s}≤n}g_{st}(X_{i_{1}}, …, X_{i_{s}})|^{2/s})

(34) follows from Lemma 4.

In what follows we shall estimate R(t). We do this by partitioning v_{n2}(t) into separate terms. This leads to the desired estimate

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

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}, (36)

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}, (37) 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}, (38) 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). (39)

Hence by (36) and four applications of the inequality (39)

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). (40)

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

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

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

In (41) each expectation has the same structure. Consider the first expectation in (41). By (26) and (36)

e^{c_{3}|v_{n2}(t)|}[e^{−x_{t}(S̃+ṽ_{n2})}] = e^{c_{3}|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 (41) we obtain

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

where

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

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

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

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

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

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

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

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

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

Q = E_{t}{e^{δ|Δ_{n}|}[e^{−x_{t}(ξ_{n}+η_{n})}I(ξ_{n} + η_{n} > 0)]}, (46) 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 (42) have a simpler form than (46). All expectations (43) - (45) have the structure (46). The following lemma provides a bound for Q in (46). Lemma 5. Under the conditions of Theorem 2

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

for some positive constants c_{4} and c_{5}. 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 (46), since ξ_{n} is independent of Δ_{n} and η_{n} we can write

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

where E^{ξ}{⋯} denotes the expectation with respect to ξ_{n}. Here (see the proof of (33)),

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

In (48)

∫_{−η_{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 (31)

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

Further in (48)

∫_{−η_{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 (47)

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

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

Q ≤ (c_{8} \frac{1}{\sqrt{n}} + c_{9} \frac{1}{x})Ee^{δ|Δ_{n}|+δ^{1}|s_{n}|},

where s_{n} = (σ_{t}\sqrt{|J̄|})^{−1} ∑_{j∈J̄} g_{t}(X_{j}). Here Hölder’s inequality, Lemma 4 and the well known inequality E exp(δ^{1}|s_{n}|) ≤ d_{1} < ∞ for bounded random variables g_{t}(X_{j}), j ∈ J̄ provides the required bound for Q. From (49) and Lemma 4 we obtain the proof of Lemma 5, and hence (35). Combining (24) - (25), (28) and (33) - (35) completes the proof of Theorem 2.

REFERENCES

Aleshkevichiene, A.K. (1990). Probabilities of large deviations for U-statistics and von Mises functionals, Theor.Ver. i Prim. 35, 1-14.

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

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.

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.

Whittaker, E.T. and Watson, G.N. (1927). A Course of Modern Analysis. Cambridge at the 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