Large Deviation Results for a U-statistical Sum

with Product Kernel.

Y. V. Borovskikh  N. C. Weber

9 June 2000

Abstract

Large deviation theorems are proved for non-degenerate U-statistical sums of degree m with kernel h(x_{1}, …, x_{m}) = x_{1} ⋯ x_{m} under the Cramér condition (Theorem 1) and under the Linnik condition (Theorem 2). The method of proof uses truncation and the contraction technique.

AMS 2000 subject classification. 60F10. Key words and phrases. Cramér condition, Large deviations, U-statistics. Running Head: Large deviations for U-statistics

Addresses: Y.V. Borovskikh Department of Applied Mathematics Transport University 190031, St.Petersburg. RUSSIA email: borovski@spb.cityline.ru

N.C. Weber School of Mathematics and Statistics, F07 University of Sydney N.S.W. 2006 AUSTRALIA email: neville@maths.usyd.edu.au

1 Introduction and Theorems

Let X_{1}, ⋯, X_{n} be independent and identically distributed (i.i.d.) random variables with distribution function F. Assume EX_{1} = μ ≠ 0 and 0 < σ^{2} = E(X_{1} −μ)^{2} < ∞. Consider the U-statistic of the form

U_{n} = ( \begin{matrix}n \\ m \end{matrix} )^{−1} ∑_{1≤i_{1}<...<i_{m}≤n} X_{i_{1}} ⋯ X_{i_{m}}.

According to the Hoeffding decomposition

U_{n} − μ^{m} = (1)

∑_{c=1}^{m} \frac{m(m − 1) ⋯ (m − c + 1)}{n(n − 1) ⋯ (n − c + 1)}μ^{m−c} ∑_{1≤i_{1}<...<i_{c}≤n}(X_{i_{1}} − μ) ⋯ (X_{i_{c}} − μ).

For m = 1, U_{n}−μ = n^{−1} ∑_{i=1}^{n}(X_{i}−μ) is the usual sum of i.i.d. random variables. Large deviation results with Cramér series for such sums have been developed in many papers including ([?], [?], [?], [?], [?]), both under the Cramér and Linnik conditions and under violation of these conditions.

Let F_{n}(x) = P (\sqrt{n}(U_{n} − μ^{m})/(mσ|μ|^{m−1}) ≤ x ), x ∈ R. By the central limit theorem for non-degenerate U-statistics, F_{n}(x) → Φ(x) uniformly in x as n → ∞, where Φ(x) denotes the standard normal distribution function. Hence for any fixed m and x

(1 − F_{n}(x)) / (1 − Φ(x)) = (1 + o(1)) , (2)

as n → ∞. We are interested in (2) when x tends to infinity together with n and x = o(\sqrt{n}). All existing large deviation results for U-statistical sums with x in this range require the kernels to be bounded and so they do not apply here. For our special case we have the following result where the coefficients λ_{km} are defined via equation (18).

Theorem 1 Let x = o(\sqrt{n}) and suppose that the Cramér condition

E exp (a|X_{1}|) < ∞ (3)

is satisfied for some a > 0. Then for any fixed m ≥ 1

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

with the Cramér series

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

which converges for 0 ≤ u ≤ ε for some ε > 0.

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

λ_{m}^{[s]}(u) = λ_{0m} + λ_{1m}u + … + λ_{sm}u^{s}.

Theorem 2 Let x = o(n^{α}) and suppose that the Linnik condition

E exp \{a|X_{1}|^{\frac{4α}{2α+1}} \} < ∞ (4)

is satisfied for some a > 0. Then for any fixed m ≥ 1

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

2 Proofs

In the following we can suppose that x ≥ 1. In fact, by Theorem 6.3.2 in [?]

sup_{x} |F_{n}(x) − Φ(x)| ≤ 36 (σ^{−3}E|X_{1} − μ|^{3} + m exp \{2(σ/μ)^{2}\}) \frac{1}{\sqrt{n}}

for all 1 ≤ m ≤ \sqrt{n}. Further 1 − Φ(x) ≥ π^{−2} for 0 ≤ x ≤ 1. Hence for any fixed m ≥ 1 and for 0 ≤ x ≤ 1

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

Proof of Theorem 1. The contraction technique for U-statistics of degree 2, proposed in [?] , was extended in [?] to U-statistics with bounded kernels of any degree. Following their approach we define the operator T_{t}^{m−1}: g → T_{t}^{m−1}g, by

T_{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 …, where g(X_{1}) satisfies the Cramér condition, i.e. E exp (a|g(X_{1})|) < ∞ for some a > 0.

The following lemma shows that under the Cramér condition (3) for sufficiently small t, the contraction equation g = T_{t}^{m−1}g with kernel h(x_{1}, …, x_{m}) = x_{1} ⋯ x_{m}. (5) has a unique solution g_{t}, i.e. g_{t} = T_{t}^{m−1}g_{t}. (6) Lemma 1 If the Cramér condition (3) is satisfied then the function

g_{t}(x) = μ_{m}^{m−1}(t) · x, x ∈ R

is the solution of (6) for kernel (5), where μ_{m}(t) is an analytical function in the region 0 ≤ t ≤ b for some sufficiently small b > 0. Proof. If some function g_{t}(x) is the solution of (6) then we can write

g_{t}(x) = \begin{matrix}(E (e^{tg_{t}(X_{1})}X_{1})) & m−1 \\ (Ee^{tg_{t}(X_{1})}) & m−1 \end{matrix} · x.

Let

μ_{m}(t) = \frac{E (e^{tg_{t}(X_{1})}X_{1})}{Ee^{tg_{t}(X_{1})}}.

Hence, for μ_{m}(t) we obtain the equation

μ_{m}(t) = \frac{E (e^{tμ_{m}^{m−1}(t)X_{1}}X_{1})}{Ee^{tμ_{m}^{m−1}(t)X_{1}}}. (7)

Futher we will prove that this equation has a unique analytical solution for small t. To show this let ξ = tμ_{m}^{m−1}(t). (8) Then (7) can be written as

t = ξ · (\frac{Ee^{ξX_{1}}}{E (X_{1}e^{ξX_{1}})})^{m−1} . (9)

Under condition (3) the functions E exp(ξX_{1}), E (X_{1} exp(ξX_{1})) and E exp(ξX_{1})/E (X_{1} exp(ξX_{1})) are analytic for |ξ| ≤ a/2 and therefore in (9)

t = ξ · ∑_{k=0}^{∞} c_{km}ξ^{k}, (10)

where the power series converges for small |ξ|. For any sufficiently small |t| the equation (10) has a unique real solution ξ = ξ(t), where

ξ(t) = t · ∑_{k=0}^{∞} d_{km}t^{k} (11)

with convergent series for small |t|. From (8) and (11) we obtain

μ_{m}^{m−1}(t) = ∑_{k=0}^{∞} d_{km}t^{k}. (12)

From (12) we see that for any m ≥ 2

μ_{m}(t) = ∑_{k=0}^{∞} μ_{km}t^{k} (13)

where the power series converges for sufficiently small t. This proves Lemma 1.

Let ψ(t) = ln E exp{tg_{t}(X_{1})}, where g_{t}(x) is given in Lemma 1. Define F_{t} by

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

Let P_{t} denote the probability measure under which X_{1}, X_{2}, … are i.i.d. from F_{t} and let E_{t} denote the expectation under P_{t}. Hence, in (7) μ_{m}(t) = E_{t}X_{1}. (14)

Let t = t (\frac{x}{\sqrt{n}}), where t (\frac{x}{\sqrt{n}}) is the solution of the equation

μ_{m}^{m}(t) − μ^{m} = \frac{x}{\sqrt{n}}mσ|μ|^{m−1} (15)

with x n^{−1/2} → 0. The existence of this solution is guaranteed by (13). In fact,

μ_{m}^{m}(t) = μ^{m} + ∑_{k=1}^{∞} β_{km}t^{k},

where the power series converges for sufficiently small t. From (15) we obtain

∑_{k=1}^{∞} β_{km}t^{k} = \frac{x}{\sqrt{n}}mσ|μ|^{m−1}.

By the inversion theorem for analytic functions we get

t (\frac{x}{\sqrt{n}}) = ∑_{k=1}^{∞} t_{km} (\frac{x}{\sqrt{n}})^{k} (16)

with convergent series for small x n^{−1/2}.

Further, let U_{n}(t) denote the U-statistical sum U_{n}, where X_{1}, …, X_{n} are i.i.d. with distribution function F_{t}. By analogy with (1) and by using Lemma 1 we have the Hoeffding decomposition under P_{t}

U_{n}(t) = μ_{m}^{m}(t) + \frac{m}{n} ∑_{i=1}^{n} (g_{t}(X_{i}) − μ_{m}^{m}(t)) +

∑_{c=2}^{m} \frac{m(m − 1) ⋯ (m − c + 1)}{n(n − 1) ⋯ (n − c + 1)}μ_{m}^{m−c}(t) ∑_{1≤i_{1}<...<i_{c}≤n} (X_{i_{1}} − μ_{m}(t)) ⋯ (X_{i_{c}} − μ_{m}(t)) .

Let

σ_{1} = \frac{1}{n} ∑_{j=1}^{n} (g_{t}(X_{j}) − μ_{m}^{m}(t)) and v_{n} = ∑_{c=2}^{m} λ_{c}(t)π_{c},

where

λ_{c}(t) = \frac{(m − 1) ⋯ (m − c + 1)}{(n − 1) ⋯ (n − c + 1)} · n^{c−1}μ_{m}^{−m(c−1)}(t),

and

π_{c} = n^{−c} ∑_{1≤i_{1}<...<i_{c}≤n} (g_{t}(X_{i_{1}}) − μ_{m}^{m}(t)) ⋯ (g_{t}(X_{i_{c}}) − μ_{m}^{m}(t)) .

Then

U_{n}(t) = μ_{m}^{m}(t) + mσ_{1} + mv_{n}.

Hence using (15)

U_{n}(t) − \frac{x}{\sqrt{n}}mσ|μ|^{m−1} = mσ_{1} + mv_{n} + μ^{m}

and

P (U_{n} − μ^{m} > \frac{x}{\sqrt{n}}mσ|μ|^{m−1}) (17)

= ∫ I (U_{n}(y_{1}, …, y_{n}) − μ^{m} > \frac{x}{\sqrt{n}}mσ|μ|^{m−1}) ∏_{i=1}^{n} dF (y_{i})
= ∫ exp \{∑_{i=1}^{n} (ψ(t) − tg_{t}(y_{i}))\} I (U_{n} − μ^{m} > \frac{x}{\sqrt{n}}mσ|μ|^{m−1}) ∏_{i=1}^{n} dF_{t}(y_{i})
= E_{t} [e^{nψ(t)−ntμ_{m}^{m}(t)−tnσ_{1}}I (U_{n}(t) − \frac{x}{\sqrt{n}}mσ|μ|^{m−1} − μ^{m} > 0)]
= e^{nψ(t)−ntμ_{m}^{m}(t)} · J_{n},

where J_{n} = E_{t}e^{−tnσ_{1}}I(σ_{1} + v_{n} > 0).

Using (16) and the definitions of ψ(t) and μ_{m}(t) we have

(18)  nψ(t) − ntμ_{m}^{m}(t) = −\frac{x^{2}}{2} + λ_{0m} \frac{x^{3}}{\sqrt{n}} + λ_{1m} \frac{x^{4}}{n} + …
= −\frac{x^{2}}{2} + \frac{x^{3}}{\sqrt{n}}λ_{m} (\frac{x}{\sqrt{n}}) .

Next we will estimate J_{n}. Let ξ_{j} = g_{t}(X_{j}) − μ_{m}^{m}(t), j = 1, …, n, and introduce the truncated random variables

\overline{ξ}_{j} = ξ_{j}I(|ξ_{j}| ≤ x\sqrt{n}), j = 1, …, n.

Then J_{n} = J_{n}(ξ_{1}, …, ξ_{n}) and \overline{J}_{n} = J_{n}(\overline{ξ}_{1}, …, \overline{ξ}_{n}) = E_{t}e^{−tn\overline{σ}_{1}}I(\overline{σ}_{1} + \overline{v}_{n} > 0). Lemma 2 If x ≥ 1 and x n^{−1/2} → 0 as n → ∞, then

J_{n} = \overline{J}_{n} + e^{x^{2}/2} (1 − Φ(x)) · O (\frac{x}{\sqrt{n}}) .

Proof. Denote

f(ξ_{1}, …, ξ_{n}) = e^{−tnσ_{1}}I(σ_{1} + v_{n} > 0).

Note

J_{n} − \overline{J}_{n} = E_{t} [f(ξ_{1}, …, ξ_{n}) − f(\overline{ξ}_{1}, …, \overline{ξ}_{n})]
= ∑_{j=1}^{n} E_{t} [f(\overline{ξ}_{1}, …, \overline{ξ}_{j−1}, ξ_{j}, …, ξ_{n}) − f(\overline{ξ}_{1}, …, \overline{ξ}_{j}, ξ_{j+1}, …, ξ_{n})]
= ∑_{j=1}^{n} E_{t}I(|ξ_{j}| > x\sqrt{n})[f(\overline{ξ}_{1}, …, \overline{ξ}_{j−1}, ξ_{j}, ξ_{j+1} …, ξ_{n})
−f(\overline{ξ}_{1}, …, \overline{ξ}_{j−1}, 0, ξ_{j+1}, …, ξ_{n})].

Thus

|J_{n} − \overline{J}_{n}| ≤ ∑_{j=1}^{n} E_{t} [I(|ξ_{1}| > x\sqrt{n}) (e^{t|ξ_{1}|} + 1)] (E_{t}e^{tξ_{1}})^{n−j} (E_{t}e^{t\overline{ξ}_{1}})^{j−1} . (19)

Since e^{y} = 1 + y + θy^{2}e^{|y|}, |θ| ≤ 1, y ∈ R (20) under condition (3), E_{t}e^{tξ_{1}} ≤ exp\{c_{1}x^{2}/n\}, E_{t}e^{t\overline{ξ}_{1}} ≤ exp\{c_{1}x^{2}/n\}, and

E_{t}I (|ξ_{1}| > x\sqrt{n}) e^{t|ξ_{1}|} ≤ (E_{t}e^{2t|ξ_{1}|})^{1/2} (P_{t} (|ξ_{1}| > x\sqrt{n}))^{1/2}
≤ exp\{c_{1}x^{2}/n\} (P_{t} (|ξ_{1}| > x\sqrt{n}))^{1/2} ≤ c_{2}e^{−c_{3}x\sqrt{n}}

for some positive constants c_{i} > 0, which do not depend on x and n. Hence in (19)

|J_{n} − \overline{J}_{n}| ≤ 2c_{2}n exp\{c_{1}x^{2} − c_{3}x\sqrt{n}\}
= e^{x^{2}/2} (1 − Φ(x)) O (\frac{x}{\sqrt{n}}) ,

since

e^{x^{2}/2} (1 − Φ(x)) = O (\frac{1}{x}) , x → ∞.

This proves Lemma 2.

Consider \overline{J}_{n}. The second Waring formula gives the following representation for \overline{π}_{c}:

\overline{π}_{c} = ∑_{\{i_{s}≥0:i_{1}+2i_{2}+...+ci_{c}=c\}} ∏_{s=1}^{c}(−1)^{i_{s}−1}(s^{i_{s}}i_{s}!)^{−1} \overline{σ}_{s}^{i_{s}},

where

\overline{σ}_{s} = n^{−s} ∑_{k=1}^{n} \overline{ξ}_{k}^{s}, s = 1, …, c.

Next we introduce the truncated random variables

σ^{∼}_{j}= \overline{σ}_{j}I(|\overline{σ}_{j}| ≤ δ), j = 1, …, m

for some sufficiently small δ > 0. In addition, J^{∼}_{n}, v^{∼}_{n}, π^{∼}_{c} are obtained from \overline{J}_{n}, \overline{v}_{n}, \overline{π}_{c}, respectively, by substituting σ^{∼}_{j} for \overline{σ}_{j}.

Lemma 3 If x ≥ 1 and x n^{−1/2} → 0, then

\overline{J}_{n} =J^{∼}_{n} +e^{x^{2}/2} (1 − Φ(x)) O (\frac{x}{\sqrt{n}}) .

Proof. Denote φ(\overline{σ}_{1}, …, \overline{σ}_{m}) = e^{−tn\overline{σ}_{1}}I(\overline{σ}_{1} + \overline{v}_{n} > 0).

Arguing as in the proof of Lemma 2

\overline{J}_{n} − J̃_{n} = E_{t} [φ(\overline{σ}_{1}, …, \overline{σ}_{m}) − φ(σ̃_{1}, …, σ̃_{m})]
= ∑_{k=1}^{m} E_{t}I(|\overline{σ}_{k}| > δ)[φ(σ̃_{1}, …, σ̃_{k−1}, \overline{σ}_{k}, \overline{σ}_{k+1}, …, \overline{σ}_{m}) −
φ(σ̃_{1}, …, σ̃_{k−1}, 0, \overline{σ}_{k+1}, …, \overline{σ}_{m})]

from which we obtain

|\overline{J}_{n}− J^{∼}_{n} | ≤ 2 ∑_{k=1}^{m} E_{t}I(|\overline{σ}_{k}| > δ)e^{tn|\overline{σ}_{1}|}
≤ 2 ∑_{k=1}^{m} (E_{t}e^{2tn|\overline{σ}_{1}|})^{1/2} · (P_{t}(|\overline{σ}_{k}| > δ))^{1/2} .

Here

E_{t}e^{2tn|\overline{σ}_{1}|} ≤ E_{t}e^{2tn\overline{σ}_{1}} + E_{t}e^{−2tn\overline{σ}_{1}}
= (E_{t}e^{2t\overline{ξ}_{1}})^{n} + (E_{t}e^{−2t|\overline{ξ}_{1}|})^{n} ≤ c_{4}e^{c_{5}x^{2}}

and

(21) P_{t}(|\overline{σ}_{k}| > δ) ≤ e^{−δx\sqrt{n}}E_{t} exp \{x\sqrt{n}|\overline{σ}_{k}|\}
≤ e^{−δx\sqrt{n}}E_{t} exp \{x\sqrt{n}\overline{σ}_{k}\} + e^{−δx\sqrt{n}}E_{t} exp \{−x\sqrt{n}\overline{σ}_{k}\} .

Now

E_{t} exp \{x\sqrt{n}\overline{σ}_{k}\} = (E_{t} exp \{\frac{x\sqrt{n}}{n^{k}} \overline{ξ}_{1}^{k}\})^{n} ,

and using (20)

E_{t} exp \{\frac{x\sqrt{n}}{n^{k}} \overline{ξ}_{1}^{k}\} ≤ 1 + \frac{x\sqrt{n}}{n^{k}}E_{t}\overline{ξ}_{1}^{k} + \frac{x^{2}}{n^{2k−1}} E_{t} (\overline{ξ}_{1}^{2k} exp \{\frac{x\sqrt{n}}{n^{k}}|\overline{ξ}_{1}^{k}|\}) . (22)

For k = 1, |E_{t}\overline{ξ}_{1}| ≤ c_{6}(x\sqrt{n})^{−1}, and

E_{t}\overline{ξ}_{1}^{2} exp \{\frac{x}{\sqrt{n}}|\overline{ξ}_{1}|\} ≤ (E_{t}\overline{ξ}_{1}^{4})^{1/2} (E_{t} exp \{\frac{2x}{\sqrt{n}}|\overline{ξ}_{1}|\})^{1/2} ≤ c_{7}.

Hence E_{t} exp \{x\sqrt{n}\overline{σ}_{1}\} ≤ exp\{c_{6} + c_{7}x^{2}\}. (23) Now consider (22) when k ≥ 2. In this case |E_{t}\overline{ξ}_{1}^{k}| ≤ c_{8}, and

E_{t} (\overline{ξ}_{1}^{2k} exp \{\frac{x\sqrt{n}}{n^{k}}|\overline{ξ}_{1}^{k}|\}) ≤ (E_{t}\overline{ξ}_{1}^{4k})^{1/2} (E_{t} exp \{\frac{2x\sqrt{n}}{n^{k}}|\overline{ξ}_{1}^{k}|\})^{1/2}
≤ (E_{t}\overline{ξ}_{1}^{4k})^{1/2} (E_{t} exp \{2(\frac{x}{\sqrt{n}})^{k}|\overline{ξ}_{1}^{k}|\})^{1/2} ≤ c_{9}.

Hence for k ≥ 2,

E_{t} exp \{x\sqrt{n}\overline{σ}_{k}\} ≤ exp \{c_{8} \frac{x}{\sqrt{n}} + c_{9} (\frac{x}{n^{k−1}} )^{2}\} (24)

for some positive constants c_{i}. These estimates combined with (21) prove Lemma 3. Next we will estimate J̃_{n}.

Lemma 4 If x ≥ 1 and x = o(\sqrt{n}), n → ∞, then

J̃_{n} = e^{\frac{x^{2}}{2}} (1 − Φ(x)) (1 + O (\frac{x}{\sqrt{n}})) .

Proof. Write

π̃_{c} = σ̃_{1} · α_{c} + β_{c}, c ≥ 2

where

α_{c} = ∑ ; \begin{matrix}i_{1} + 2i_{2} + … + ci_{c} = c \\ i_{1} ≥ 1, i_{s} ≥ 0, s = 2, …, c \end{matrix} (∏_{s=1}^{c}(−1)^{i_{s}−1}(s^{i_{s}}i_{s}!)^{−1}) σ̃_{1}^{i_{1}−1}σ̃_{2}^{i_{2}} ⋯ σ̃_{c}^{i_{c}},
β_{c} = ∑_{2i_{2}+...+ci_{c}=c}(−1)^{c+i_{2}+...+i_{c}} (∏_{s=2}^{c}(s^{i_{s}}i_{s}!)^{−1}) σ̃_{2}^{i_{2}} ⋯ σ̃_{c}^{i_{c}}.

Then ṽ_{n} = σ̃_{1}α + β, (25) where

α = ∑_{c=2}^{m} λ_{c}(t)α_{c} and β = ∑_{c=2}^{m} λ_{c}(t)β_{c}.

Note that |α| ≤ a_{1} · δ ≤ 1/2 for some constant a_{1} > 0 and sufficiently small δ. Further, taking account of (25) we have

J̃_{n} = E_{t}e^{−tnσ̃_{1}}I(σ̃_{1} + ṽ_{n} > 0) = E_{t}e^{−tnσ̃_{1}}I (σ̃_{1} > −\frac{β}{1 + α}) = ∑_{i=1}^{5} Δ_{i},

where

Δ_{1} = E_{t}e^{−tnσ_{1}}I(σ_{1} > 0),
Δ_{2} = E_{t}e^{−tn\overline{σ}_{1}}I(\overline{σ}_{1} > 0) − E_{t}e^{−tnσ_{1}}I(σ_{1} > 0),
Δ_{3} = E_{t}e^{−tnσ̃_{1}}I(σ̃_{1} > 0) − E_{t}e^{−tn\overline{σ}_{1}}I(\overline{σ}_{1} > 0),
Δ_{4} = E_{t}e^{−tnσ̃_{1}}I (σ̃_{1} > −\frac{β}{1 + α}) I (\frac{|β|}{1 + α} ≤ \frac{1}{n}) − E_{t}e^{−tnσ̃_{1}}I(σ̃_{1} > 0),
Δ_{5} = E_{t}e^{−tnσ̃_{1}}I (σ̃_{1} > −\frac{β}{1 + α}) I (\frac{|β|}{1 + α} > \frac{1}{n}) .

Estimate Δ_{1}. Let σ_{t}^{2} = E_{t} (g_{t}(X_{1}) − μ_{m}^{m}(t))^{2}, x_{t} = \sqrt{n}tσ_{t},

S = \frac{1}{σ_{t}\sqrt{n}} ∑_{i=1}^{n} (g_{t}(X_{1}) − μ_{m}^{m}(t)) , and Φ_{n}(y) = P_{t}(S ≤ y), y ∈ R.

Note that by Lemma 1, (15) and (16)

σ_{t} = σ|μ|^{m−1} + O (\frac{x}{\sqrt{n}}) , t = \frac{x}{σ|μ|^{m−1}\sqrt{n}} (1 + O (\frac{x}{\sqrt{n}})) , and

x_{t} = x + \frac{x^{2}}{\sqrt{n}}O(1). (26)

By definition

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

Recall e^{z} = 1 + z ∫_{0}^{1} e^{uz}du, z ∈ R, so using (26) we have

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

Here

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

and

\frac{x^{2}}{\sqrt{n}} ∫_{0}^{∞} y exp \{−xy − \frac{x^{2}}{\sqrt{n}}yuO(1)\} dΦ(y)

≤ \frac{x^{2}}{\sqrt{n}} ∫_{0}^{∞} y exp \{−xy − \frac{x^{2}}{\sqrt{n}}yuO(1)\} dy
= \frac{x^{2}}{\sqrt{n}} (x + \frac{x^{2}}{\sqrt{n}}uO(1))^{−2}
= e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) .

Consequently,

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

Further, in (27)

∫_{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 Berry-Esseen theorem (see, for example, [?])

sup_{y} |Φ_{n}(y) − Φ(y)| ≤ σ_{t}^{−3}E|g_{t}(X_{1}) − μ_{m}^{m}(t)|^{3} \frac{1}{\sqrt{n}}.

Hence,

|∫_{0}^{∞} e^{−x_{t}y}d(Φ_{n}(y) − Φ(y))| ≤ 2σ_{t}^{−3}E|g_{t}(X_{1}) − μ_{m}^{m}(t)|^{3} \frac{1}{\sqrt{n}}
= e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) ,

and so we have

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

Estimate Δ_{2}. Let Ψ(ξ_{1}, …, ξ_{n}) = e^{−tnσ_{1}}I(σ_{1} > 0). Then

Δ_{2} = E_{t} [Ψ(\overline{ξ}_{1}, …, \overline{ξ}_{n}) − Ψ(ξ_{1}, …, ξ_{n})]
= ∑_{j=1}^{n} E_{t}I(|ξ_{j}| > x\sqrt{n}) [Ψ(\overline{ξ}_{1}, …, \overline{ξ}_{j−1}, 0, ξ_{j+1}, …, ξ_{n}) − Ψ(\overline{ξ}_{1}, …, \overline{ξ}_{j−1}, ξ_{j}, ξ_{j+1}, …, ξ_{n})]

and therefore

|Δ_{2}| ≤ 2 ∑_{j=1}^{n} E_{t}I(|ξ_{j}| > x\sqrt{n}) = 2nP_{t}(|ξ_{1}| > x\sqrt{n}) ≤ 2E_{t}ξ_{1}^{4}n^{−1}.

Hence,

Δ_{2} = e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) .

Estimate Δ_{3}. By definition, Δ_{3} = E_{t}I(|\overline{σ}_{1}| > δ) (1 − e^{−tn\overline{σ}_{1}}I(\overline{σ}_{1} > 0)) and so from (21) and (23) we have

Δ_{3} = e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) .

Estimate Δ_{4}. Clearly

−E_{t}e^{−tnσ̃_{1}}I (0 ≤ σ̃_{1} ≤ \frac{1}{n}) ≤ Δ_{4} ≤ E_{t}e^{−tnσ̃_{1}}I (−\frac{1}{n} ≤ σ̃_{1} ≤ 0) .

That is,

(28) |Δ_{4}| ≤ e^{t}E_{t}I (|σ̃_{1}| ≤ n^{−1})
= e^{t}[E_{t}I(|\overline{σ}_{1}| ≤ δ)I (|σ̃_{1}| ≤ n^{−1}) + E_{t}I(|\overline{σ}_{1}| > δ)I (|σ̃_{1}| ≤ n^{−1})]
≤ e^{t}[P_{t} (|\overline{σ}_{1}| ≤ n^{−1}) + P_{t} (|\overline{σ}_{1}| > δ)].

But

P_{t} (|\overline{σ}_{1}| > δ) ≤ e^{−δx\sqrt{n}}E_{t}e^{x\sqrt{n}|\overline{σ}_{1}|}.

and so from (21) and (23)

P_{t} (|\overline{σ}_{1}| > δ) = e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) . (29)

Further in (28)

P_{t} (|\overline{σ}_{1}| ≤ \frac{1}{n}) = P_{t}(x_{n} ≤ \overline{s} ≤ y_{n}),

where x_{n} = −(1 + nE_{t}\overline{ξ}_{1})/(\overline{σ}_{t}\sqrt{n}), y_{n} = (1 − nE_{t}\overline{ξ}_{1})/(\overline{σ}_{t}\sqrt{n}),

\overline{s} = ∑_{i=1}^{n}(\overline{ξ}_{i} − E_{t}\overline{ξ}_{1})/(\overline{σ}_{t}\sqrt{n}), and \overline{σ}_{t}^{2} = E_{t}(\overline{ξ}_{1} − E_{t}\overline{ξ}_{1})^{2}.

Let \overline{Φ}_{n}(y) = P (\overline{s} ≤ y). Then

(30)  P_{t} (|\overline{σ}_{1}| ≤ \frac{1}{n}) ≤ 2 sup_{y} |\overline{Φ}_{n}(y) − Φ(y)| + Φ(y_{n}) − Φ(x_{n})
≤ 2E_{t}|\overline{ξ}_{1} − E_{t}\overline{ξ}_{1}|^{3}/(\overline{σ}_{t}^{3}\sqrt{n}) + 2(\overline{σ}_{t}\sqrt{n})^{−1}
= e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) .

Hence, from (28)–(30) we find

Δ_{4} = e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) .

Estimate Δ_{5}. Since |α| ≤ 1/2, then

Δ_{5} ≤ E_{t}e^{2tn|β|}I(2n|β| ≥ 1).

By Hölder’s inequality Δ_{5} ≤ (E_{t}e^{4tn|β|})^{1/2} (P_{t}(2n|β| ≥ 1))^{1/2} . (31) Using the inequality

|y_{1} … y_{m}| ≤ q_{1}^{−1}|y_{1}|^{q_{1}} + ⋯ + q_{m}^{−1}|y_{m}|^{q_{m}}, q_{1}^{−1} + ⋯ + q_{m}^{−1} = 1, y_{i} ∈ R we obtain

E_{t}e^{4tn|β|} ≤ a_{2} ∑_{c=2}^{m} ∑_{2i_{2}+···+ci_{c}=c} E_{t} exp \{a_{3}x\sqrt{n}|σ̃_{2}^{i_{2}} ⋯ σ̃_{c}^{i_{c}}|\} (32)

for some positive constants a_{i}. Without loss of generality we can suppose that in (32) all i_{s} ≥ 1, s = 2, …, m. Otherwise, if i_{k} = 0 for some k ≥ 2 then σ̃_{k}^{i_{k}} = 1. Hence, in (32), if δ < 1,

E_{t} exp \{a_{3}x\sqrt{n}|σ̃_{2}^{i_{2}} ⋯ σ̃_{c}^{i_{c}}|\} ≤ E_{t} exp \{a_{3}x\sqrt{n}δ^{i_{2}+···+i_{c}−1}|σ̃_{j}|\}
≤ E_{t} exp \{a_{3}x\sqrt{n}|σ̃_{j}|\} , j = 2, …, c,

and so using (24) we get

E_{t}e^{4tn|β|} ≤ c_{10}.

Further in (31) we have for any integer l ≥ 8

P_{t}(2n|β| ≥ 1) ≤ (2n)^{l}E_{t}|β|^{l} ≤ (2m)^{l} ∑_{c=2}^{m} |λ_{c}(t)|^{l}{n^{l}E_{t}|β_{c}|^{l}}. (33)

Let r_{j} ≥ 1, j = 1, …, p, be the non-zero terms in the solution of the equation 2i_{2} + ⋯ + ci_{c} = c, c ≥ 2. Hence i_{k_{1}} = r_{1}, …, i_{k_{p}} = r_{p} for some sequence k_{1}, …, k_{p} with k_{j} ≥ 2. Then in (33)

E_{t}|β_{c}|^{l} ≤ c_{11} ∑_{(r_{1},...,r_{p})} E_{t} (|σ̃_{k_{1}}|^{lr_{1}} ⋯ |σ̃_{k_{p}}|^{lr_{p}}) ≤ c_{11} ∑_{(r_{1},...,r_{p})} ∑_{s=1}^{p} E_{t}|\overline{σ}_{k_{s}}|^{plr_{s}}.

It is easy to see that

n^{l}E_{t}|\overline{σ}_{k_{s}}|^{plr_{s}} ≤ c_{12}n^{−l/2}, s = 1, …, p.

Hence in (33), P_{t}(2n|β| ≥ 1) ≤ c_{13}n^{−1}. Substituting into (31) gives

Δ_{5} = e^{x^{2}/2}(1 − Φ(x))O (\frac{x}{\sqrt{n}}) .

Combining the bounds for the Δ_{i} completes the proof of Lemma 4.

Theorem 1 follows from (17), (18) and Lemmas 2,3,4. Proof of the Theorem 2. At first we introduce the truncated random variables

\overline{X}_{j} = X_{j}I(|X_{j}| ≤ n^{1/2+α}), j = 1, …, n

and define the U-statistic \overline{U}_{n} = U_{n}(\overline{X}_{1}, …, \overline{X}_{n}). The proof of Theorem 2 follows from Lemmas 5 and 6 below.

Lemma 5 Assume condition (4) holds. Then for 1 ≤ x ≤ o(n^{α})

|P (U_{n} − μ^{m} > \frac{x}{\sqrt{n}}mσ|μ|^{m−1}) − P (\overline{U}_{n} − \overline{μ}^{m} > \frac{x}{\sqrt{n}}m\overline{σ}|\overline{μ}|^{m−1})|

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

where \overline{μ} = μ(\overline{X}_{1}) = E\overline{X}_{1}, \overline{σ}^{2} = σ^{2}(\overline{X}_{1}) = E(\overline{X}_{1} − \overline{μ})^{2}.

Proof. By analogy with the proof of Lemma 2 we can write the inequality

|P (U_{n} − μ^{m} > \frac{x}{\sqrt{n}}mσ|μ|^{m−1}) − P (\overline{U}_{n} − \overline{μ}^{m} > \frac{x}{\sqrt{n}}m\overline{σ}|\overline{μ}|^{m−1})| ≤ 2nP (|X_{1}| > n^{\frac{1}{2} +α}).

Here

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

Since x ≥ 1 and x n^{−α} → 0 as n → ∞ then

e^{−an^{2α}} = e^{− \frac{a}{2} n^{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^{− \frac{a}{2} n^{2α}} exp \{\frac{x^{3}}{\sqrt{n}}λ_{m}^{[s]} (\frac{x}{\sqrt{n}})\} (1 − Φ(x))O(1),

completing the proof of Lemma 5.

Lemma 6 If 1 ≤ x ≤ o(n^{α}) and condition (4) is satisfied then

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

Proof. We will apply Theorem 1. In the following \overline{μ}, \overline{σ}, \overline{t}, \overline{ψ}, … denote μ, σ, t, ψ, … respectively, where, instead of X_{1}, we substitute \overline{X}_{1}. For example, \overline{μ} = E\overline{X}_{1}, \overline{σ}^{2} = E(\overline{X}_{1} − \overline{μ})^{2}. At first we note that for |z| ≤ \frac{1}{2}an^{− \frac{1}{2} +α},

E exp(z\overline{X}_{1}) ≤ E exp \{a|X_{1}|^{\frac{4α}{2α+1}} \} ,
|E exp(z\overline{X}_{1})\overline{X}_{1}|^{2} ≤ EX_{1}^{2}E exp \{a|X_{1}|^{\frac{4α}{2α+1}} \} .

Hence, given condition (4), the function E exp(z\overline{X}_{1})/E exp(z\overline{X}_{1})\overline{X}_{1} in (9) is majorized by an analytic function uniformly in n for |z| ≤ \frac{1}{2}an^{− \frac{1}{2} +α}. Further, by analogy with (18)

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

Therefore, under condition (4), applying Theorem 1 for 1 ≤ x ≤ o(n^{α})

P (\overline{U}_{n} − \overline{μ}^{m} > \frac{x}{\sqrt{n}}m\overline{σ}|\overline{μ}|^{m−1}) = (1 − Φ(x)) exp \{\frac{x^{3}}{\sqrt{n}}\overline{λ}_{m} (\frac{x}{\sqrt{n}})\} (1 + O (\frac{x}{\sqrt{n}})) ,

with Cramér series

\overline{λ}_{m}(u) = ∑_{k=0}^{∞} \overline{λ}_{km}u^{k} (34)

which converges for 0 ≤ u ≤ εn^{− \frac{1}{2} +α} and sufficiently small ε > 0. The coefficients \overline{λ}_{km} = λ_{km}(\overline{X}_{1}) depend on the moments of the truncated random variable \overline{X}_{1}.

Let

\overline{λ}_{m}(u) = ∑_{k=0}^{s} \overline{λ}_{km}u^{k} + ρ(u),

where ρ(u) = ∑_{k=s+1}^{∞} \overline{λ}_{km}u^{k}. Note s + 1 ≥ 4α/(1 − 2α) and in (34) the series is convergent and uniformly bounded. Hence for x = o(n^{α})

\frac{x^{3}}{\sqrt{n}}ρ (\frac{x}{\sqrt{n}}) = O(1)\frac{x^{3}}{\sqrt{n}} (\frac{x}{\sqrt{n}})^{s+1} = O (\frac{x}{\sqrt{n}}) .

Moreover

∑_{k=0}^{s} \overline{λ}_{km} (\frac{x}{\sqrt{n}})^{k} = λ_{m}^{[s]} (\frac{x}{\sqrt{n}}) + O (\frac{1}{n}) .

Thus

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

This proves Lemma 6.

References

[1] H. Cramér, ‘Sur un nouveaux théorème limit de la théorie des probabilités’, Actualités Scientifiques et Industrielles, 736 (1938), 5–23.

[2] Y.V. Borovskikh, U-statistics in Banach Spaces (VSP, Utrecht, The Netherlands, 1996).

[3] Y.V. Borovskikh and N.C. Weber, ‘On large deviations of U-statistics’, Technical Report 00-4 (2000), School of Mathematics and Statistics, University of Sydney.

[4] I.A. Ibragimov and Y.V. Linnik, Independent and Stationary Sequence of Random Variables (Wolters-Noordhoff Publishing, Groningen, The Netherlands, 1971).

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

[6] Y.V. Linnik, The Collected Works. Probability Theory (Nauka Publishers, Leningrad, 1981).

[7] V.V. Petrov, Sums of Independent Random Variables (Springer- Verlag, Berlin, Heidelberg, New York, 1975).

[8] L. Saulis and V. Statulevicius, Limit Theorems on Large Deviations (Mokslas Publishers, Vilnius, 1989).