An estimate on the supremum of a nice class of stochastic integrals and U-statistics. Péter Major Alfréd Rényi Mathematical Institute of the Hungarian Academy of Sciences Budapest, P.O.B. 127 H–1364, Hungary, e-mail: major@renyi.hu

Summary: Let a sequence of iid. random variables ξ_{1}, …, ξ_{n} be given on a space (X, X) with distribution μ together with a nice class F of functions f(x_{1}, …, x_{k}) of k variables on the product space (X^{k}, X^{k}). For all f ∈ F we consider the random integral J_{n,k}(f) of the function f with respect to the k-fold product of the normalized signed measure \sqrt{n}(μ_{n} − μ), where μ_{n} denotes the empirical measure defined by the random variables ξ_{1}, …, ξ_{n} and

investigate the probabilities P (sup_{f∈F} |J_{n,k}(f)| > x) for all x > 0. We show

that for nice classes of functions, for instance if F is a Vapnik–Červonenkis class, an almost as good bound can be given for these probabilities as in the case when only the random integral of one function is considered. A similar result holds for degenerate U-statistics, too.

1. Introduction. Formulation of the main results

In some investigations about non-parametric maximum likelihood estimates (see [10] or [11]) I met the problem how to give a good estimate about the distribution of the supremum of appropriate classes of multiple integrals with respect to a normalized empirical measure. This problem is closely related to the study of the supremum of good classes of degenerate U-statistics. Hence, it is natural to study these two problems simultaneously. This will be done in the present paper. To formulate its main results first I introduce some notations and recall some definitions.

Let a probability measure μ be given on a measurable space (X, X), take a sequence ξ_{1}, …, ξ_{n} of independent, identically distributed (X, X) valued random variables with distribution μ, and define the empirical measure μ_{n},

μ_{n}(A) = \frac{1}{n}#\{j: ξ_{j} ∈ A, 1 ≤ j ≤ n\}, A ∈ X ,  (1.1)

of the sample ξ_{1}, …, ξ_{n}. Let us take a nice set F of measurable functions f(x_{1}, …, x_{k}) on the k-fold product space (X^{k}, X^{k}) and define the integrals J_{n,k}(f) of the functions f ∈ F with respect to the k-fold product of the normalized empirical measure \sqrt{n}(μ_{n}−μ) by the formula

J_{n,k}(f) = \frac{n^{k/2}}{k!} ∫ ′ f(x_{1}, …, x_{k})(μ_{n}( dx_{1}) − μ( dx_{1})) … (μ_{n}( dx_{k}) − μ( dx_{k})),

where the prime in ∫′ means that the diagonals x_{j} = x_{l}, 1 ≤ j < l ≤ k,

are omitted from the domain of integration.  (1.2)

I try to give a good estimate on the probabilities P (sup_{f∈F} |J_{n,k}(f)| > x) for all x > 0.

To formulate the result in this direction first I introduce the following definition.

Definition of L_{p}-dense classes of functions. Let us have a measurable space (Y, Y) and a set G of Y-measurable functions on this space. We call G an L_{p}-dense class with parameter D and exponent L if for all numbers 1 ≥ ε > 0 and probability measures ν on the space (Y, Y) there exists a finite ε-dense subset G_{ε,ν} = {g_{1}, …, g_{m}} ⊂ G in the space L_{p}(Y, Y, ν) consisting of m ≤ Dε^{−L} elements, i.e. there is such a set G_{ε,ν} ⊂ G for which inf_{g_{j}∈G_{ε,ν}} ∫ |g − g_{j}|^{p} dν < ε^{p} for all functions g ∈ G. (Here the set G_{ε,ν} may depend

on the measure ν, but its cardinality is bounded by a number depending only on ε.)

In this paper we shall work with such classes of functions F which contain only functions with absolute value less than or equal to 1. In this case F is an L_{p}-dense class of functions for all 1 ≤ p < ∞ (with an exponent and a parameter depending on p) if there is a number 1 ≤ p < ∞ for which it is L_{p}-dense. We shall formulate our statements mainly for L_{p}-dense classes of functions with the parameter p = 2, since this seems to be the most convenient choice. Our main result is the following

Theorem 1. Let us have a non-atomic measure μ on the space (X, X) together with an L_{2}-dense class F of functions f = f(x_{1}, …, x_{k}) of k variables with some parameter D > 0 and exponent L ≥ 1 on the product space (X^{k}, X^{k}) which consists of at most countably infinite functions, and satisfies the conditions

∥f∥_{∞} = sup_{x_{j}∈X, 1≤j≤k} |f(x_{1}, …, x_{k})| ≤ 1,  for all f ∈ F  (1.3)

and

∥f∥_{2}^{2} = Ef^{2}(ξ_{1}, …, ξ_{k}) = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2} for all f ∈ F

(1.4)

with some constant 0 < σ ≤ 1. Then there exist some constants C = C(k) > 0, α = α(k) > 0 and M = M(k) > 0 depending only on the parameter k such that the supremum of the random integrals J_{n,k}(f), f ∈ F, defined by formula (1.2) satisfies the inequality

P (sup_{f∈F} |J_{n,k}(f)| ≥ x) ≤ CD exp \{−α (\frac{x}{σ} )^{2/k}\}

if nσ^{2} ≥ (\frac{x}{σ} )^{2/k} ≥ M(L + β)^{3/2} log \frac{2}{σ} ,

(1.5)

where β = max (\frac{log D}{log n} , 0), and the numbers D and L in formula (1.5) are the parameter and exponent of the L_{2}-dense class F.

Theorem 1 has a natural counterpart about degenerate U-statistics formulated in Theorem 2 below. Before its formulation I recall the definition of U-statistics and degenerate U-statistics.

Let us have a sequence of independent and identically distributed random variables ξ_{1}, ξ_{2}, … with distribution μ on a measurable space (X, X) together with a function f = f(x_{1}, …, x_{k}) on the k-th power (X^{k}, X^{k}) of the space (X, X). We define with their help the U-statistic I_{n,k}(f) of order k, as

I_{n,k}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f (ξ_{j_{1}}, …, ξ_{j_{k}}) .  (1.6)

(The function f in this formula will be called the kernel function of the U-statistic.)

A real valued function f = f(x_{1}, …, x_{k}) on the k-th power (X^{k}, X^{k}) of a space (X, X) is called a canonical kernel function (with respect to the probability measure μ on the space (X, X)) if

∫ f(x_{1}, …, x_{j−1}, u, x_{j+1}, …, x_{k})μ( du) = 0 for all 1 ≤ j ≤ k and x_{s} ∈ X, s ≠ j.

I also introduce the notion of canonical functions in a more general case, because this notion appears later in Proposition 5 of this paper. We call a function f(x_{1}, …, x_{k}) on the k-fold product (X_{1} × ⋯ × X_{k}, X_{1} × ⋯ × X_{k}, μ_{1} × ⋯ × μ_{k}) of k not necessarily identical probability spaces (X_{j}, X_{j}, μ_{j}), 1 ≤ j ≤ k, canonical if

∫ f(x_{1}, …, x_{j−1}, u, x_{j+1}, …, x_{k})μ_{j}( du) = 0 for all 1 ≤ j ≤ k and x_{s} ∈ X_{s}, s ≠ j.

A U-statistic with a canonical kernel function is called degenerate. Now I formulate Theorem 2.

Theorem 2. Let us have a probability measure μ on a space (X, X), a sequence of independent and μ distributed random variables ξ_{1}, …, ξ_{n} together with an L_{2}-dense class F of canonical (with respect to the measure μ) kernel functions f = f(x_{1}, …, x_{k}) with some parameter D > 0 and exponent L ≥ 1 on the product space (X^{k}, X^{k}) which consists of at most countably infinite functions, and satisfies conditions (1.3) and (1.4) with some 0 < σ ≤ 1. Then there exist some numbers C = C(k) > 0, M = M(k) > 0 α = α(k) > 0 depending only on the order k of the U-statistics we consider such that the degenerate U-statistics I_{n,k}(f), f ∈ F, defined in (1.6) satisfy the inequality

P (sup_{f∈F} |n^{−k/2}I_{n,k}(f)| ≥ x) ≤ CD exp \{−α (\frac{x}{σ} )^{2/k}\}

if nσ^{2} ≥ (\frac{x}{σ} )^{2/k} ≥ M(L + β)^{3/2} log \frac{2}{σ} ,

(1.7) where β = max (\frac{log D}{log n} , 0).

To understand the relation between Theorems 1 and 2 let us observe that the definition of the U-statistics in (1.6) can be rewritten as

I_{n,k}(f) = \frac{n^{k}}{k!} ∫ ′ f(x_{1}, …, x_{k})μ_{n}( dx_{1}) … μ_{n}( dx_{k})  (1.8)

if the distribution μ of the random variables ξ_{1}, …, ξ_{n} is non-atomic. (The non-atomic property is needed to guarantee that the random variables ξ_{1}, …, ξ_{n} take different values with probability 1.) The difference between the random integrals J_{n,k}(f) and the random integral representation (1.8) of U-statistics I_{n,k}(f) is (beside the different norming constant) that in formula (1.8) we integrate with respect to the empirical measure μ_{n} and not with respect to its normalized version μ_{n} − μ. As a consequence, we can get a good estimate for U-statistics only under some restriction. In Theorem 2 we had to impose the condition that the functions of the class F are canonical, while no similar condition was needed in Theorem 1. Hence Theorem 1 can be better applied in statistical problems. On the other hand, the proof of Theorem 2 is simpler. But Theorem 1 can be deduced from it by means of a good representation of multiple random integrals J_{n,k}(f) as a linear combination of degenerate U-statistics. In this work the following approach will be followed. In the main text Theorem 2 will be proved. The Appendix contains the proof of the above mentioned representation of random integrals which enables us to deduce Theorem 1 from Theorem 2.

Let us discuss the conditions of Theorems 1 and 2. We have assumed that F contains at most countably infinite functions. This condition, which is too restrictive for statistical applications can be weakened. The introduction of the following definition seems to be useful.

Definition of countable approximability. A class of functions F is countably approximable in the space (X^{k}, X^{k}, μ^{k}) if there exists a countable subset F′ ⊂ F such that for all numbers x > 0 the sets A(x) = {ω: sup_{f∈F} |J_{n,k}(f)(ω)| ≥ x} and B(x) =

{ω: sup_{f∈F′} |J_{n,k}(f)(ω)| ≥ x} satisfy the identity P (A(x) \ B(x)) = 0.

Clearly, B(x) ⊂ A(x). In the above definition we demanded that for all x > 0 the set B(x) is almost as large as A(x). The following corollary of Theorems 1 and 2 holds.

Corollary of Theorem 1 or 2. Let a class of functions F satisfy the conditions of Theorem 1 or 2 with the only exception that instead of the condition about the countable cardinality of F it is assumed that F is countably approximable in the space (X^{k}, X^{k}, μ^{k}). Then F satisfies Theorem 1 or 2.

In Theorems 1 and 2 we have imposed the condition that the class of functions F is countable to avoid some unpleasant measure theoretical difficulties. Otherwise we should have to work with possibly non-measurable sets. On the other hand, I have the impression that Corollary 1 can be applied in all statistical problems where we have to work with the supremum of multiple random integrals or U-statistics. It is not difficult to prove that Corollary 1 follows from Theorem 1 or 2. We have to show that if F is an L_{2}-dense class with some parameter D and exponent L, and F′ ⊂ F, then F′ is also an L_{2}-dense class with the same exponent L, only with a possibly different parameter D′.

To prove this statement let us choose for all numbers 1 ≥ ε > 0 and probability measures ν on (Y, Y) some functions f_{1}, …, f_{m} ∈ F with m ≤ D (\frac{ε}{2})^{−L} elements, such

that the sets U_{j} = \{f: ∫ |f − f_{j}|^{2} dν ≤ (\frac{ε}{2})^{2}\} satisfy the relation ⋃_{j=1}^{m} U_{j} = Y. For all

sets U_{j} for which U_{j} ∩ F′ is non-empty choose a function f′_{j} ∈ U_{j} ∩ F′. In such a way we get a collection of functions f′_{j} from the class F′ containing at most 2^{L}Dε^{−L} elements which satisfy the condition imposed for L_{2}-dense classes with exponent L and parameter 2^{L}D for this number ε and measure ν.

In Theorems 1 and 2 we have considered the supremum of multiple random integrals and U-statistics of order k for a nice class of functions. It was shown that if the variances of the random integrals or U-statistics we have considered are less than some number 0 < σ^{2} ≤ 1, (formula (1.4) was a condition about these variances in an implicit way) then under some additional conditions this supremum takes a value larger than x with a probability less than P (Cση^{k} > x), where η is a standard normal random variable, and C = C(k) > 0 is a universal constant depending only on the multiplicity k of the random integrals. This is the sharpest estimate we can expect. Moreover, this estimate seems to be sharp also in that respect that the conditions imposed for its validity cannot be considerably weakened. If condition (1.3) does not hold or nσ^{2} < (\frac{x}{σ} )^{2/k}, then the estimate of Theorem 1 or 2 may not hold any longer even if the class of functions F contains only one function. In such cases there exist examples for which the probability P (J_{n,k}(f) > x) is too large. In [8] I gave such examples (Examples 3.2 and 8.6). Here I do not discuss them in detail.

If the other inequality is violated in the conditions of formula (1.5) or (1.7), i.e. if (\frac{x}{σ} )^{2/k} < M log \frac{2}{σ} with a not too large number M > 0, then the estimate of Theorem 1 or 2 may not hold for a different reason. The supremum of many small random variables may be large, and inequalities (1.5) or (1.7) may loose their validity for this reason. To understand this let us consider the following analogous problem. Take a Wiener process W (t), 0 ≤ t ≤ 1, and consider the supremum of the expressions W (t) − W (s) = ∫ f_{s,t}(u)W ( du) = J̄(f_{s,t}), with the functions f_{s,t}(·) on the interval [0, 1] defined by the formula f_{s,t}(u) = 1 if s ≤ u ≤ t, f_{s,t}(u) = 0 if 0 ≤ u < s or t < u ≤ 1. If we consider the class of functions F_{σ} = {f_{s,t}: ∫ f_{s,t}^{2}(u) du = t − s ≤ σ^{2}}, then it is natural to expect

that P ( sup_{f_{s,t}∈F_{σ}} J̄(f_{s,t}) > x) ≤ e^{−const. (x/σ)^{2}}. However, this relation does not hold if

x = x(σ) < (1−ε)\sqrt{2 log \frac{1}{σ}} σ with some ε > 0. In such cases P ( sup_{f_{s,t}∈F_{σ}} J̄(f_{s,t}) > x) →

1, as σ → 0. This can be proved relatively simply with the help of the estimate P (J̄(f_{s,t}) > x(σ)) ≥ const. σ^{1−ε} if |t − s| = σ^{2} and the independence of the random integrals J̄(f_{s,t}) if the functions f_{s,t} are indexed by such pairs (s, t) for which the intervals (s, t) are disjoint.

Some additional work would show that a similar picture arises if we integrate with respect to the normalized empirical measure of a sample with uniform distribution on the interval [0, 1] instead of a Wiener process. This yields an example for an L_{2}-dense class of functions in the case k = 1 for which the estimate of Theorem 1 does not hold any longer if (\frac{x}{σ} )^{2/k} < M log \frac{2}{σ} with some M < \sqrt{2}. Similar example can be constructed also in the case of Theorem 2. At a heuristic level it is clear that such an example can be given also for k > 1, and the number M in condition (1.5) or (1.7) has to be chosen larger if we want that Theorem 1 or Theorem 2 hold also for an L_{2}-dense class of functions F with a large exponent L. (In this paper I did not try to find the best possible condition of Theorem 1 or 2 in the right-hand side inequality of (1.5) or (1.7).)

One would like to see some interesting examples when Theorem 1 or 2 is applicable and to have some methods to check their conditions. It is useful to know that if F is a Vapnik–Červonenkis class of functions whose absolute values are bounded by 1, then F is an L_{2}-dense class.

To formulate the above statement more explicitly let us recall that a class of subsets D of a set S is a Vapnik–Červonenkis class if there exist some constants B > 0 and K > 0 such that for all integers n and sets S_{0}(n) = {x_{1}, …, x_{n}} ⊂ S of cardinality n the collection of sets of the form S_{0}(n) ∩ D, D ∈ D, contains no more than Bn^{K} subsets of S_{0}(n). A class of real valued functions F on a space (Y, Y) is a Vapnik– Červonenkis class if the graphs of these functions is a Vapnik–Červonenkis class, i.e. if the sets A(f) = {(y, t): y ∈ Y, min(0, f(y)) ≤ t ≤ max(0, f(y))}, f ∈ F, constitute a Vapnik–Červonenkis class of sets on the product space Y × R^{1}.

An important result of Dudley states that a Vapnik–Červonenkis class of functions whose absolute values are bounded by 1 is an L_{1}-dense class. The parameter and exponent of this L_{1}-dense class can be bounded by means of the constants B and K appearing in the definition of Vapnik–Červonenkis classes. Beside this, an L_{1}-dense class of functions bounded by 1 is also an L_{2}-dense class (with possibly different exponent and parameter), since ∫ |f − g|^{2} dν ≤ 2 ∫ |f − g| dν in this case. Dudley’s result, whose proof can be found e.g. in Chapter II of Pollard’s book [9] (the 25^{∘} approximation lemma contains this result in a slightly more general form) is useful for us, because there are results which enable us to prove that certain classes of functions constitute a Vapnik–Červonenkis class.

I found some results similar to that of this paper in the work of Arcones and Gine [3], where the tail-behaviour of the supremum of degenerate U-statistics was investigated if the kernel functions of these U-statistics constitute a Vapnik–Červonenkis class. But the bounds of that paper do not give a better estimate if we have the additional information that the variances of the U-statistics we consider are small. The main goal of the present paper was to prove such estimates which take into account the bound we have on the variance of the random integrals J_{n,k}(f) or U-statistics I_{n,k}(f) we consider.

In the investigation of this work Alexander’s paper [1] played an essential role. In Alexander’s work a similar problem was considered in the special case k = 1. It was interesting for me first of all, because I learned some ideas from it which I strongly needed in the present work. On the other hand, I also needed some new arguments, because in the study of multiple stochastic integrals or U-statistics some new difficulties had to be overcome.

This paper consists of six sections and an Appendix. In Section 2 Theorems 1 and 2 are reduced to two simpler statements formulated in Propositions 2 and 3. Section 3 contains some important results needed in the proof of Proposition 2, and the main ideas of its proof are explained there. It is shown that Proposition 2 follows from another statement formulated in Proposition 4. Proposition 4 is proved together with another result described in Proposition 5. To make the proof more transparent first I explain it in the special case k = 1 in Section 4. Sections 5 and 6 contain the proof of Propositions 4 and 5 in the general case. In Section 5 it is shown how a symmetrization argument can be applied to prove Propositions 4 and 5, and finally the proof is completed in Section 6. The Appendix contains the proof about a result of an expansion of multiple random integrals in the form of a linear combination of degenerate U-statistics formulated in Proposition 3. This result enables us to deduce Theorem 1 from Theorem 2.

2. Reduction of Theorems 1 and 2 to some simpler results

First I prove with the help of a natural argument, called the Chaining argument in the literature, and the multi-dimensional generalization of Bernstein’s inequality (see [2], Proposition 2.3(c)) a result that yields a reduction of Theorem 2 we shall need later. I shall apply the following consequence of this result (which is actually equivalent to it).

If U_{n,k}(f) is a degenerate U-statistic of order k with a (canonical) kernel function f which satisfies relations (1.3) and (1.4) (formally the class of functions F consisting only of the function f satisfies these relations) with some number 0 < σ ≤ 1 and the distribution μ of the iid. sequence of the random variables ξ_{1}, …, ξ_{n} taking part in the definition of the U-statistic U_{n,k}(f), then there exist some constants C = C(k) > 0 and α = α(k) > 0 depending only on the order k of this U-statistic such that

P (n^{−k/2}|I_{n,k}(f)| > x) ≤ C exp \{−α (\frac{x}{σ} )^{2/k}\} for 0 ≤ x ≤ n^{k/2}σ^{k+1}.  (2.1)

Now I formulate the following result.

Proposition 1. Let us fix some number Ā ≥ 2^{k}, and assume that a class of functions F satisfies the conditions of Theorem 2 with an appropriately chosen number M in these conditions which may depend also on Ā. Then a number σ̄, 0 ≤ σ̄ ≤ σ ≤ 1, and a collection of functions Fσ̄ = {f_{1}, …, f_{m}} ⊂ F with m ≤ Dσ̄^{−L} elements can be chosen in such a way that the sets D_{j} = {f: f ∈ F, ∫ |f − f_{j}|^{2} dμ ≤ σ̄^{2}}, 1 ≤ j ≤ m, satisfy the

relation ⋃_{j=1}^{m} D_{j} = F, and

P ( sup_{f∈Fσ̄} n^{−k/2}|I_{n,k}(f)| ≥ \frac{x}{Ā}) ≤ 2CD exp \{−α (\frac{x}{10Āσ} )^{2/k}\}  (2.2)

if nσ^{2} ≥ (\frac{x}{σ} )^{2/k} ≥ ML log \frac{2}{σ}

with the constants α = α(k), C = C(k) appearing in formula (2.1) and the exponent L and parameter D of the L_{2}-dense class F if the constant M = M(k, Ā) is chosen sufficiently large. Beside this, also the inequalities 4 (\frac{x}{Āσ̄} )^{2/k} ≥ nσ̄^{2} ≥ \frac{1}{64} (\frac{x}{Āσ} )^{2/k} and

nσ̄^{2} ≥ \frac{M^{2/3}(L+β) log n}{1000Ā^{4/3}} hold, provided that nσ^{2} ≥ (\frac{x}{σ} )^{2/k} ≥ M(L + β)^{3/2} log \frac{2}{σ} with

β = max (\frac{log D}{log n} , 0).

Remark: The introduction of the number Ā ≥ 2^{k} in Proposition 1 may seem a bit artificial. Its role is to guarantee that such a number σ̄ could be defined in Proposition 1 which satisfies the inequality (\frac{x}{σ̄} )^{2/k} ≥ Anσ̄^{2} with a sufficiently large previously fixed constant A = A(k).

Proof of Proposition 1. For all p = 0, 1, 2, … choose a set F_{p} = {f_{p,1}, …, f_{p,m_{p}}} ⊂ F with m_{p} ≤ D 2^{2pL}σ^{−L} elements in such a way that inf_{1≤j≤m_{p}} ∫ (f − f_{p,j})^{2} dμ ≤ 2^{−4p}σ^{2} for

all f ∈ F. For all pairs (j, p), p = 1, 2, …, 1 ≤ j ≤ m_{p}, choose a predecessor (j′, p − 1), j′ = j′(j, p), 1 ≤ j′ ≤ m_{p−1}, in such a way that the functions f_{j,p} and f_{j′,p−1} satisfy

the relation ∫ |f_{j,p} − f_{j′,p−1}|^{2} dμ ≤ σ^{2}2^{−4(p−1)}. Then we have ∫ (\frac{f_{j,p}−f_{j′,p−1}}{2} )^{2} dμ ≤

4σ^{2}2^{−4p} and sup_{x_{j}∈X, 1≤j≤k} |\frac{f_{j,p}(x_{1},...,x_{k})−f_{j′,p−1}(x_{1},...,x_{k})}{2} | ≤ 1. Inequality (2.1) yields that

P (A(j, p)) = P (n^{−k/2}|I_{n,k}(f_{j,p} − f_{j′,p−1})| ≥ \frac{2^{−(1+p)}x}{Ā}) ≤ C exp \{−α (\frac{2^{p}x}{8Āσ} )^{2/k}\}

if nσ^{2}2^{−4p} ≥ (\frac{2^{p}x}{8Āσ} )^{2/k} , 1 ≤ j ≤ m_{p}, p = 1, 2, …,  (2.3)

and

\begin{aligned}P (B(s)) & = P (n^{−k/2}|I_{n,k}(f_{0,s})| ≥ \frac{x}{2Ā}) ≤ C exp \{−α (\frac{x}{2Āσ} )^{2/k}\} , 1 ≤ s ≤ m, \\ & if nσ^{2} ≥ (\frac{x}{2Āσ} )^{2/k} . \end{aligned}

(2.4)

Choose an integer R, R ≥ 0, in such a way that 2^{(4+2/k)(R+1)} (\frac{x}{Āσ} )^{2/k} ≥ 2^{2+6/k}nσ^{2} ≥

2^{(4+2/k)R} (\frac{x}{Āσ} )^{2/k}, and define σ̄^{2} = 2^{−4R}σ^{2} and Fσ̄ = F_{R}. (As nσ^{2} ≥ (\frac{x}{σ} )^{2/k} and Ā ≥ 2^{k} by our conditions, there exists such a non-negative number R.) Then the

cardinality m of the set Fσ̄ is clearly not greater than Dσ̄^{−L}, and ⋃_{j=1}^{m} D_{j} = F. Beside

this, the number R was chosen in such a way that inequalities (2.2) and (2.3) can be applied for 1 ≤ p ≤ R. Hence the definition of the predecessor of a pair (j, p) implies that

P ( sup_{f∈Fσ̄} n^{−k/2}|I_{n,k}(f)| ≥ \frac{x}{Ā}) ≤ P ( ⋃_{p=1}^{R} ⋃_{j=1}^{m_{p}} A(j, p) ∪ ⋃_{s=1}^{m} B(s))

≤ ∑_{p=1}^{R} ∑_{j=1}^{m_{p}} P (A(j, p)) + ∑_{s=1}^{m} P (B(s)) ≤ ∑_{p=1}^{∞} CD 2^{2pL}σ^{−L} exp \{−α (\frac{2^{p}x}{8Āσ} )^{2/k}\}

+ CDσ^{−L} exp \{−α (\frac{x}{2Āσ} )^{2/k}\} .

If the condition (\frac{x}{σ} )^{2/k} ≥ ML^{3/2} log \frac{2}{σ} holds with a sufficiently large constant M (depending on Ā), then the inequalities

2^{2pL}σ^{−L} exp \{−α (\frac{2^{p}x}{8Āσ} )^{2/k}\} ≤ 2^{−p} exp \{−α (\frac{2^{p}x}{10Āσ} )^{2/k}\}

hold for all p = 1, 2, …, and

σ^{−L} exp \{−α (\frac{x}{2Āσ} )^{2/k}\} ≤ exp \{−α (\frac{x}{10Āσ} )^{2/k}\} .

Hence the previous estimate implies that

P ( sup_{f∈Fσ̄} n^{−k/2}|I_{n,k}(f)| ≥ \frac{x}{Ā}) ≤ ∑_{p=1}^{∞} CD2^{−p} exp \{−α (\frac{2^{p}x}{10Āσ} )^{2/k}\}

+ CD exp \{−α (\frac{x}{10Āσ} )^{2/k}\} ≤ 2CD exp \{−α (\frac{x}{10Āσ} )^{2/k}\} ,

and relation (2.2) holds. We have

nσ̄^{2} = 2^{−4R}nσ^{2} ≤ 2^{−4R} · 2^{(4+2/k)(R+1)−2−6/k} (\frac{x}{Āσ} )^{2/k} = 2^{2−4/k} · 2^{2R/k} (\frac{x}{Āσ} )^{2/k}

= 2^{2−4/k} · (\frac{σ}{σ̄} )^{1/k} (\frac{x}{Āσ} )^{2/k} = 2^{2−4/k} · (\frac{σ̄}{σ} )^{1/k} (\frac{x}{Āσ̄} )^{2/k} ,

hence nσ̄^{2} ≤ 4 (\frac{x}{Āσ̄} )^{2/k}. Beside this, as nσ^{2} ≥ 2^{(4+2/k)R−2−6/k} (\frac{u}{Āσ} )^{2/k}, R ≥ 1,

nσ̄^{2} = 2^{−4R}nσ^{2} ≥ 2^{−2−6/k} · 2^{2R/k} (\frac{x}{Āσ} )^{2/k} ≥ \frac{1}{64} (\frac{x}{Āσ} )^{2/k} .

It remained to show that nσ̄^{2} ≥ \frac{M^{2/3}(L+β) log n}{1000A^{4/3}}.

This inequality clearly holds under the conditions of Proposition 1 if σ ≤ n^{−1/3}, since in this case log \frac{2}{σ} ≥ \frac{log n}{3}, and nσ̄^{2} ≥ \frac{1}{64} (\frac{x}{Āσ} )^{2/k} ≥ \frac{1}{64} Ā^{−2/k}M(L + β)^{3/2} log \frac{2}{σ} ≥

\frac{1}{192} Ā^{−2/k}M(L + β) log n ≥ \frac{M^{2/3}(L+β) log n}{1000A^{4/3}} if M = M(Ā, k) is chosen sufficiently large.

If σ ≥ n^{−1/3}, then the inequality 2^{(4+2/k)R} (\frac{x}{Āσ} )^{2/k} ≤ 2^{2+6/k}nσ^{2} holds. Hence

2^{−4R} ≥ 2^{−4(2+6/k))/(4+2/k)} [\frac{(\frac{x}{Āσ} )2/k}{nσ^{2}} ]^{4/(4+2/k)}, and

nσ̄^{2} = 2^{−4R}nσ^{2} ≥ \frac{2^{−16/3}}{Ā^{4/3}} (nσ^{2})^{1−γ} [(\frac{x}{σ} )^{2/k}]^{γ} with γ = \frac{4}{4 + \frac{2}{k}} ≥ \frac{2}{3}.

Since nσ^{2} ≥ (\frac{x}{σ})^{2/k} ≥ \frac{M}{3} (L + β)^{3/2}, and nσ^{2} ≥ n^{1/3}, the above estimates yield that

nσ̄^{2} ≥ \frac{Ā^{−4/3}}{50} (nσ^{2})^{1/3} [(\frac{x}{σ} )^{2/k}]^{2/3} ≥ \frac{Ā^{−4/3}}{50} n^{1/9} (\frac{M}{3} )^{2/3} (L + β) ≥ \frac{M^{2/3}(L+β) log n}{1000Ā^{4/3}}.

Now I formulate Proposition 2 and show that Theorem 2 follows from Propositions 1 and 2.

Proposition 2. Let us have a probability measure μ on a space (X, X) together with a sequence of independent and μ distributed random variables ξ_{1}, …, ξ_{n} and an L_{2}-dense class F of canonical kernel functions f = f(x_{1}, …, x_{k}) (with respect to the measure μ) with some parameter D > 0 and exponent L ≥ 1 on the product space (X^{k}, X^{k}) which consists of at most countably many functions, and satisfies conditions (1.3) and (1.4) with some 0 < σ ≤ 1. Let nσ^{2} > K(L + β) log n with β = max (\frac{log D}{log n} , 0) and a

sufficiently large constant K = K(k). Then there exist some numbers C̄ = C̄(k) > 0, γ = γ(k) > 0 and threshold index A_{0} = A_{0}(k) > 0 depending only on the order k of the U-statistics we consider such that the degenerate U-statistics I_{n,k}(f), f ∈ F, defined in (1.6) satisfy the inequality

P (sup_{f∈F} |n^{−k/2}I_{n,k}(f)| ≥ An^{k/2}σ^{k+1}) ≤ C̄e^{−γA^{1/2k}nσ^{2}} if A ≥ A_{0}.  (2.5)

In the proof of Theorem 2 with the help of Propositions 1 and 2 we exploit our freedom in the choice of the parameters in these results. Let us choose a number Ā_{0} such that Ā_{0} ≥ A_{0} and γĀ_{0}^{1/2k} ≥ \frac{1}{K} with the numbers A_{0}, K and γ in Proposition 2. We shall apply Proposition 1 with the choice Ā = max(2^{k+2}Ā_{0}, 2^{k}). Then by Proposition 1 and the choice of the numbers Ā and Ā_{0} also the inequality (\frac{x}{σ̄} )^{2/k} ≥ \frac{Ā^{2/k}}{4} nσ̄^{2} ≥ (4Ā_{0})^{2/k}nσ̄^{2} holds, hence x ≥ 4Ān^{k/2}σ̄^{k+1} with the number σ̄ in Proposition 1. This implies that (\frac{1}{2} − \frac{1}{2Ā}) x ≥ \frac{x}{4} ≥ Ān^{k/2}σ̄^{k+1}, and Ā ≥ A_{0}. The numbers x considered in

these estimations satisfy the condition nσ^{2/k} ≥ (\frac{x}{σ} )^{2/k} ≥ M(L + β)^{3/2} log \frac{2}{σ} imposed in Proposition 1 with some appropriately chosen constant M. Choose the number M ≥ M(Ā, k) in Proposition 1 (which also can be chosen as the number M in formula (1.7) of Theorem 2) in such a way that it also satisfies the inequality \frac{M^{2/3}(L+β) log n}{1000Ā^{4/3}} ≥ K(L+ β) log n with the number K appearing in the conditions of Proposition 2. With such a choice the inequality nσ̄^{2} ≥ \frac{M^{2/3}(L+β) log n}{1000Ā^{4/3}} ≥ K(L + β) log n holds, and Proposition 2 can be applied with the choice σ̄ defined in Proposition 1 for the parameter σ, the number (\frac{1}{2} − \frac{1}{2Ā}) x as the number A in this result, together with the classes of functions

D̄_{j} = \{g = \frac{f−f_{j}}{2} , f ∈ D_{j}\}, 1 ≤ j ≤ m, where the classes of functions D_{j} and functions f_{j}, 1 ≤ j ≤ m, are defined in Proposition 1.

Then Propositions 1 and 2 together with the above observations yield that

P (sup_{f∈F} n^{−k/2}|I_{n,k}(f)| ≥ x) ≤ P ( sup_{f∈Fσ̄} n^{−k/2}|I_{n,k}(f)| ≥ \frac{x}{Ā})

+ ∑_{j=1}^{m} P ( sup_{g∈D_{j}} n^{−k/2} |I_{n,k} (\frac{f_{j} − g}{2} )| ≥ (\frac{1}{2} − \frac{1}{2Ā}) x)  (2.6)

≤ 2CD exp \{−α (\frac{x}{10Āσ} )^{2/k}\} + C̄Dσ̄^{−L}e^{−γĀ^{1/2k}nσ̄^{2}}.

To get the result of Theorem 2 from inequality (2.6) we have to replace its second term at the right-hand side with a more appropriate expression where, in particular, we get rid of the coefficient σ̄^{−L}. The condition nσ̄^{2} ≥ K(L + β) log n implies that σ̄ ≥ n^{−1/2}, and by our choice of Ā_{0} we have γĀ_{0}^{1/2k}nσ̄^{2} ≥ \frac{1}{K} nσ̄^{2} ≥ L log n ≥ 2L log \frac{1}{σ̄}, i.e. σ̄^{−L} ≤

e^{γĀ_{0}^{1/2k}nσ̄^{2}/2}. By the estimates of Proposition 1 nσ̄^{2} ≥ \frac{1}{64} (\frac{x}{Āσ} )^{2/k}. The above relations

imply that σ̄^{−L}e^{−γĀ_{0}^{1/2k}nσ̄^{2}} ≤ e^{−γĀ_{0}^{1/2k}nσ̄^{2}/2} ≤ exp \{−\frac{γ}{128} Ā_{0}^{1/2k}Ā^{−2/k} (\frac{u}{σ})^{2/k}\}. Hence relation (2.6) yields that

P (sup_{f∈F} n^{−k/2}|I_{n,k}(f)| ≥ x)

≤ 2CD exp \{−\frac{α}{(10Ā)^{2}} (\frac{x}{σ} )^{2/k}\} + C̄D exp \{−\frac{γ}{128}Ā_{0}^{1/2k}Ā^{−2/k} (\frac{x}{σ} )^{2/k}\} ,

and this estimate implies Theorem 2 with some new appropriately defined constants α > 0 and C > 0.

Thus I have reduced the proof of Theorem 2 to that of Proposition 2. I also show in this section that the proof of Theorem 1 can be reduced to that of Theorem 2 and a decomposition result of random integrals J_{n,k}(f) formulated in Proposition 3 below whose proof will be given in the Appendix. Proposition 3 gives the representation of a random integral J_{n,k}(f) in the form of a linear combination of degenerate Ustatistics. To get this representation we can observe that a random integral J_{n,k}(f) can be rewritten in the form of a sum of U-statistics. By applying an important result, called Hoeffding’s decomposition, we can write a general U-statistic in the form of a sum of degenerate U-statistics of different order. Proposition 3 contains the result we get by carrying out this procedure. Let us recall that we have integrated with respect to the signed measure μ_{n} − μ in the definition (1.3) of the random integrals J_{n,k}(f). This has a very strong cancellation effect, and the main content of Proposition 3 is that this implies that the representation of J_{n,k}(f) in the form of a linear combination of degenerate U-statistics contains small coefficients.

Beside Proposition 3 we need another result to deduce Theorem 1 from Theorem 2. We must have some control on the exponent and parameter of the classes of functions appearing in the Hoeffding decomposition of the class of functions we consider together with a good L_{2}-norm of these functions. Hoeffding’s decomposition is made with the help of certain projections introduced in formulas (2.7) and (2.8) below. In Lemma 1 I prove the properties of these projections I shall need later. I shall need Lemma 1 also in the proof of Proposition 2, since Hoeffding’s decomposition is applied in it.

Let some measurable spaces (Y_{1}, Y_{1}), (Y_{2}, Y_{2}) and (Z, Z) be given together with a probability measure μ on the space (Z, Z). Consider a function f(y_{1}, z, y_{2}) on the product space (Y_{1} × Z × Y_{2}, Y_{1} × Z × Y_{2}), y_{1} ∈ Y_{1}, z ∈ Z, y_{2} ∈ Y_{2}, and define their projections

P_{μ}f(y_{1}, y_{2}) = ∫ f(y_{1}, z, y_{2})μ( dz), y_{1} ∈ Y_{1}, y_{2} ∈ Y_{2},  (2.7)

and

\begin{aligned}Q_{μ}f(y_{1}, z, y_{2}) & = (I − P_{μ})f(y_{1}, z, y_{2}) \\ & = f(y_{1}, z, y_{2}) − P_{μ}f(y_{1}, z, y_{2}), y_{1} ∈ Y_{1}, z ∈ Z, y_{2} ∈ Y_{2}, \end{aligned}  (2.8)

where P_{μ}f(y_{1}, z, y_{2}) = P_{μ}f(y_{1}, y_{2}), i.e. I have introduced a fictive argument z of the function P̄_{μ}f in formula (2.8) to make it meaningful. Now I formulate the following

Lemma 1. Let us have some measurable spaces (Y_{1}, Y_{1}), (Y_{2}, Y_{2}) and (Z, Z), a probability measure μ on the space (Z, Z) and a probability measure ρ on the product space (Y_{1} × Y_{2}, Y_{1} × Y_{2}). The transformations P_{μ} and Q_{μ} defined in (2.7) and (2.8) are contractions from the space L_{2}(Y_{1} × Z × Y_{2}, ρ × μ) to the spaces L_{2}(Y_{1} × Y_{2}, ρ) and L_{2}(Y_{1} × Z × Y_{2}, ρ × μ) respectively, i.e.

\begin{aligned}∥P_{μ}f∥_{L_{2},ρ}^{2} & = ∫ P_{μ}f(y_{1}, z, y_{2})^{2}ρ( dy_{1}, dy_{2}) \\ & ≤ ∥f∥_{L_{2},ρ×μ}^{2} = ∫ f(y_{1}, z, y_{2})^{2}ρ( dy_{1}, dy_{2})μ( dz), \end{aligned}  (2.9)

and

\begin{aligned}∥Q_{μ}f∥_{L_{2},ρ}^{2} & = ∫ Q_{μ}f(y_{1}, z, y_{2})^{2}ρ( dy_{1}, dy_{2}) \\ & = ∫ (f(y_{1}, z, y_{2}) − P_{μ}f(y_{1}, z, y_{2}))^{2} ρ( dy_{1}, dy_{2})μ( dz) \\ & ≤ ∥f∥_{L_{2},ρ×μ}^{2} = ∫ f(y_{1}, z, y_{2})^{2}ρ( dy_{1}, dy_{2})μ( dz). \end{aligned}  (2.9′)

Also the inequalities

sup_{y_{1},y_{2}} |P_{μ}f(y_{1}, y_{2})| ≤ sup_{y_{1},z,y_{2}} |f(y_{1}, z, y_{2})|  (2.10)
sup_{y_{1},z,y_{2}} |Q_{μ}f(y_{1}, z, y_{2})| ≤ 2 sup_{y_{1},z,y_{2}} |f(y_{1}, z, y_{2})|  (2.10′)

hold. If F is an L_{2}-dense class of functions f(y_{1}, z, y_{2}) on the product space (Y_{1} × Z × Y_{2}, Y_{1} × Z × Y_{2}), y_{1} ∈ Y_{1}, z ∈ Z, y_{2} ∈ Y_{2} with parameter D and exponent L, then also the classes F_{μ} = {P_{μ}f,: f ∈ F} with the functions P_{μ}f defined in formulas (2.7) are L_{2}-dense classes with parameter D and exponent L in the space (Y_{1} × Y_{2}, Y_{1} × Y_{2}). Beside this, the class of functions G_{μ} = \{\frac{1}{2}Q_{μ}f = \frac{1}{2}(f − P_{μ}f), f ∈ F\} is also an L_{2}-dense class with exponent L and parameter D.

Proof of Lemma 1. The Schwarz inequality yields that P_{μ}(f)^{2} ≤ ∫ f(y_{1}, z, y_{2})^{2}μ( dz), and the inequality ∫ [f(y_{1}, z, y_{2})−P_{μ}f(y_{1}, z, y_{2})]^{2}μ(dz) ≤ ∫ f(y_{1}, z, y_{2})^{2}μ( dz) also holds. Integrating these inequalities with respect to the probability measure ρ( dy_{1}, dy_{2}) we get formulas (2.9) and (2.9′). The proof of relations (2.10) and (2.10′) is self-evident.

Let us consider an arbitrary probability measure ρ on the space (Y_{1} × Y_{2}, Y_{1} × Y_{2}). To prove that F_{μ} is an L_{2}-dense class with exponent L and parameter D we have to find m ≤ Dε^{L} functions f_{j} ∈ F_{μ}, 1 ≤ j ≤ m, such that inf_{1≤j≤m} ∫ (f_{j} − f)^{2} dρ ≤ ε^{2} for

all f ∈ F_{μ}. We can find such a sequence, since a similar statement holds for the class of functions F in the space Y_{1} × Z × Y_{2} with the probability measure ρ × μ. This fact together with the L_{2} contraction property of P_{μ} formulated in (2.9) imply that F_{μ} is an L_{2}-dense class.

The L_{2}-density property of the set G_{μ} under the appropriate conditions can be deduced from the following observation. For any probability measure ρ on the space Y_{1} × Z × Y_{2} and pair of functions f and g such that ∫ (f − g)^{2} \frac{1}{2} ( dρ + dρ̄ × du) ≤ ε^{2}, where ρ̄ is the projection of the measure ρ to the space Y_{1} × Y_{2}, i.e. ρ̄(A) = ρ(A × Z) for all A ∈ Y_{1} × Y_{2}, the inequality ∫ ((f − P_{μ}f) − (g − P_{μ}g))^{2} dρ ≤ 2 ∫ (f − g)^{2} dρ + 2 ∫ (P_{μ}f − P_{μ}g)^{2} dρ ≤ 2 ∫ (f − g)^{2} dρ + 2 ∫ (f − g)^{2} dρ̄× dμ ≤ 4ε^{2} holds. This means that if {f_{1}, …, f_{m}} is an ε-dense subset of F in the space L_{2}(Y_{1} ×Z ×Y_{2}, Y_{1} ×Z ×Y_{2}, ρ̃) with ρ̃ = \frac{1}{2}(ρ+ρ̄×μ), then \{Q_{μ}f_{1}, …, Q_{μ}f_{m}\} is a 2ε-dense subset of 2G_{μ} = \{f −P_{μ}f: f ∈ F\} in the space L_{2}(Y_{1} × Z × Y_{2}, Y_{1} × Z × Y_{2}, ρ). Hence, if {f_{1}, …, f_{m}} is an ε-dense subset with respect to the measure ρ̃ = \frac{1}{2} (ρ + ρ̄ × μ), then \{\frac{1}{2}Q_{μ}f_{1}, …, \frac{1}{2}Q_{μ}f_{m}\} is an ε-dense subset of G_{μ} in the space L_{2}(Y_{1} × Z × Y_{2}, Y_{1} × Z × Y_{2}, ρ) space.

To formulate Proposition 3 first I introduce the following notation. Given a function f(x_{1}, …, x_{k}) of k variables on (X^{k}, X^{k}) together with some probability measure μ let us introduce for all sets V ⊂ {1, …, k} the function f_{V} depending on the arguments x_{j}, j ∈ V by the formulas

f_{V} (x_{s}, s ∈ V) = ( ∏_{s∈{1,...,k}\V} P_{μ,s} ∏_{s∈V} Q_{μ,s}) f(x_{1}, …, x_{k}),  (2.11)

where P_{μ,s} and Q_{μ,s} denote the operators P_{μ} and Q_{μ} defined in formulas (2.7) and (2.8) in the space (Y_{1} × Z × Y_{2}, Y_{1} × Z × Y_{2}), where (Y_{1}, Y_{1}) the product of the first s − 1, (Y_{2}, Y_{2}) the product of the last k − s coordinates, and (Z, Z) is the s-th coordinate of the product space (X^{k}, X^{k}). The function f_{V} depends only on the coordinates x_{s}, s ∈ V, because at the application of the operator P_{μ,s} the s-th coordinate disappears. It can be shown that the function f_{V} is canonical. To see this we have to observe that the canonical property of the function f_{V} can be reformulated as P_{μ,s}f_{V} ≡ 0 for all s ∈ V. Beside this, the operator P_{μ,s} or Q_{μ,s} is exchangeable with P_{μ,s′} or Q_{μ,s′} if s ≠ s′, and P_{μ,s}Q_{μ,s} = P_{μ,s} − P_{μ,s}^{2} = 0. The functions f_{V} defined in (2.11) appear in the Hoeffding decomposition of a U-statistic with kernel function f.

Now I formulate Proposition 3 which will be proved in the Appendix.

Proposition 3. Let us have a non-atomic measure μ on a measurable space (X, X) together with a sequence of independent, μ-distributed random variables ξ_{1}, …, ξ_{n}, and take a function f(x_{1}, …, x_{k}) of k variables on the space (X^{k}, X^{k}) such that

∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) < ∞.

Let us consider the empirical distribution function μ_{n} of the sequence ξ_{1}, …, ξ_{n} introduced in (1.1) together with the k-fold random integral J_{n,k}(f) of the function f defined in (1.2). The identity

J_{n,k}(f) = ∑_{V ⊂{1,...,k}} C(n, k, V)n^{−|V |/2}I_{n,|V |}(f_{V}),  (2.12)

holds with the canonical (with respect to the measure μ) functions f_{V} (x_{j}, j ∈ V) defined in (2.11) and appropriate real numbers C(n, k, V), V ⊂ {1, …, k}, where I_{n,|V |}(f_{V}) is the (degenerate) U-statistic with kernel function f_{V} and random sequence ξ_{1}, …, ξ_{n} defined in (1.6). The constants C(n, k, V) in (2.12) satisfy the relations |C(n, k, V)| ≤ C(k) with some constant C(k) depending only on the order k of the integral J_{n,k}(f), lim_{n→∞} C(n, k, V) = C(k, V) with some constant C(k, V) < ∞ for all V ⊂ {1, …, k}, and C(n, k, {1, …, k}) = 1 for V = {1, …, k}.

Theorem 1 can be simply deduced from Theorems 2, Proposition 3 and Lemma 1. Indeed, Lemma 1 together with formula (2.11) imply that if F is an L_{2}-dense class of functions with exponent L and parameter D, and the elements of F satisfy relations (1.3) and (1.4) with some σ > 0, then for all V ⊂ {1, …, k} the class of functions F_{V} = {2^{−|V |}f_{V}: f ∈ F}, where f_{V} is defined in (2.11), and |V | denotes the cardinality of the set V is again L_{2}-dense with exponent L and parameter D, whose elements satisfy relations (1.3) and (1.4) with parameter 2^{−|V |}σ. Beside this, the elements of F_{V} are canonical functions. Hence, by Proposition 3 we can write

P (sup_{f∈F} |J_{n,k}(f)| > x) ≤ ∑_{V ⊂\{1,...,k\}} P (sup_{f∈F} n^{−|V |/2}|I_{n,|V |}(f_{V})| > \frac{x}{2^{k}C(k)}) (2.13)

with a constant C(k) satisfying the inequality C(n, k, |V |) ≤ C(k) for all coefficients C(n, k, |V |) in (2.12), and each term at the right-hand side of (2.13) can be estimated by means of Theorem 2 if F satisfies the conditions of Theorem 1.

Theorem 1 with appropriate universal constants M > 0, C > 0 and α > 0 can be proved with the help of some calculation if we bound each probability on the right-hand side of (2.13) by means of Theorem 2. Let me remark that Theorem 1 implicitly contains the condition that nσ^{2} ≥ M(L + β)^{3/2} log \frac{2}{σ}, which means that the set of numbers x which satisfy the condition in relation (1.5) is not empty. Hence we may assume that nσ^{2} ≥ 1. We need this observation to check that under the conditions of Theorem 1 nσ^{2} ≥ (\frac{x}{σ} )^{2/l} for all l ≤ k, and we can apply Theorem 1 for each term V ⊂ \{1, …, k\} in the estimation of the right-hand side of (2.13).

3. Some basic tools of the proof of Proposition 2

I shall prove Proposition 2 by means of some symmetrization procedure. The proof becomes simpler with the help of a decoupling argument. This means the introduction of decoupled U-statistics and the proof of a version of Proposition 2 about decoupled U-statistics. It can be shown with the help of some known results that this statement implies Proposition 2 in its original form. To carry out such a program first I recall the definition of decoupled U-statistics.

Definition of decoupled U-statistics. Let k independent copies ξ_{1,s}, …, ξ_{n,s}, 1 ≤ s ≤ k, of a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} with distribution μ be given on a measurable space (X, X) together with a function f = f(x_{1}, …, x_{k}) on the k-th power (X^{k}, X^{k}) of the space (X, X). We define with their help the decoupled U-statistic Ī_{n,k}(f) of order k with kernel function f by the formula

Ī_{n,k}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f (ξ_{j_{1},1}, …, ξ_{j_{k},k}) .  (3.1)

A decoupled U-statistic is called degenerate if its kernel function is canonical.

I shall prove the following version of Proposition 2.

Proposition 2′. Let us have a probability measure μ on a space (X, X) together with k independent copies ξ_{1,s}, …, ξ_{n,s}, 1 ≤ s ≤ k, of a sequence of independent and μ distributed random variables ξ_{1}, …, ξ_{n} and a countable L_{2}-dense class F of canonical kernel functions f = f(x_{1}, …, x_{k}) (with respect to the measure μ) with some parameter D > 0 and exponent L ≥ 1 on the product space (X^{k}, X^{k}) which satisfies conditions (1.3) and (1.4) with some 0 < σ ≤ 1. Let nσ^{2} > K(L+β) log n with β = max (\frac{log D}{log n} , 0) and a sufficiently large constant K = K(k). There exists some threshold index A_{0} = A_{0}(k) > 0 such that the decoupled U-statistics Ī_{n,k}(f), f ∈ F, defined in (3.6) satisfy the inequality

P (sup_{f∈F} |n^{−k/2}Ī_{n,k}(f)| ≥ An^{k/2}σ^{k+1}) ≤ e^{−A^{1/2k}nσ^{2}} if A ≥ A_{0}.  (3.2)

Proposition 2 follows from Proposition 2′ and the following Proposition A.

Proposition A. Let us consider a countable sequence f_{l}(x_{1}, …, x_{k}), l = 1, 2, …, of functions on the k-fold product (X^{k}, X^{k}) of some space (X, X) together with some probability measure μ on the space (X, X). Given a sequence of independent and identically distributed random variables ξ_{1}, ξ_{2}, … with distribution μ on (X, X) together with k independent copies ξ_{1,s}, ξ_{2,s}, …, 1 ≤ s ≤ k, of it we can define the U-statistics I_{n,k}(f_{l}) and decoupled U-statistics Ī_{n,k}(f_{l}) for all l = 1, 2, … and n = 1, 2, . . .. They satisfy the inequality

P ( sup_{1≤l<∞} |I_{n,k}(f_{l})| > x) ≤ AP ( sup_{1≤l<∞} |Ī_{n,k}(f_{l})| > γx)  (3.3)

for all x ≥ 0 with some constants A = A(k) > 0 and γ = γ(k) > 0 depending only on the order k of the U-statistics.

Proposition A can be deduced from Theorem 1 in paper [6] of de la Peña and Montgomery–Smith which compares the distribution of a single U-statistic with its decoupled U-statistic counterpart. It holds for U-statistics with a kernel function taking values in a general separable Banach space, and it compares the distribution of the norm of a Ustatistic with its decoupled counterpart. This result states that formula (3.3) remains valid if we fix a function f of k-variables taking values in a separable Banach space and replace sup |I_{n,k}(f_{l})| by ∥I_{n,k}(f)∥ and sup |Ī_{n,k}(f_{l})| by ∥Ī_{n,k}(f)∥. Moreover, the universal constants A and γ do not depend on the Banach space, where the function f takes its values. In the proof of Proposition A we exploit our freedom to work in an arbitrary separable Banach space.

The proof of Proposition A (with the help of paper [6].) Let us fix an arbitrary positive integer N, and apply the first part of Theorem 1 of [6] in the Banach space ℓ_{∞}^{N} consisting of the sequences x = (x_{1}, …, x_{N}) of length N of real numbers with norm ∥x∥ = sup_{1≤l<N}|x_{l}|

for the U-statistic and degenerate U-statistic with kernel functions f_{j_{1},...,j_{k}}(x_{1}, …, x_{k}) = f̄(x_{1}, …, x_{k}), f̄ = (f_{1}, …, f_{N}), with the functions f_{l}, 1 ≤ l ≤ N, in Proposition A, which maps the space (X^{k}, X^{k}) into the space ℓ_{∞}^{N}. (Here we do not exploit that in the result of [6] the kernel functions may depend on the indices (j_{1}, …, j_{k}).) The first part of Theorem 1 in [6] states that

\begin{matrix}P (∥  ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f̄(ξ_{j_{1}}, …, ξ_{j_{k}})∥ > x) \\ ≤ AP (∥  ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f̄(ξ_{j_{1},1}, …, ξ_{j_{k},k})∥ > γx) \end{matrix}  (3.4)

with some universal constants A = A(k) > 0 and γ = γ(k) > 0, and this statement is equivalent to a weaker version of relation (3.3), where sup_{1≤l<∞} is replaced by sup_{1≤l≤N}.

We get relation (3.3) from relation (3.4) by letting N → ∞ (and exploiting that the constants A and γ in formula (3.4) do not depend on the number N.)

Remark: I have introduced the number N in the above proof instead of working in the space of infinite sequences with L_{∞} norm to avoid the difficulty which would arise if we had to work in non-separable Banach spaces.

Thus I have reduced the proof of Theorem 2 to that of Proposition 2′. It will be proved by means of a symmetrization argument. To apply this argument I shall need two auxiliary results, the multi-dimensional version of Hoeffding’s inequality and an appropriate generalization of a well-known symmetrization lemma. First I discuss the multi-dimensional version of Hoeffding’s inequality.

Lemma 2. (The multi-dimensional version of Hoeffding’s inequality.) Let ε_{1}, …, ε_{n} be independent random variables, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n. Fix a positive integer k, and define the random variable

Z = ∑_{(j_{1},...,j_{k}):1≤j_{l}≤n for all 1≤l≤k j_{l}≠j_{l′} if l≠l′} a(j_{1}, …, j_{k})ε_{j_{1}} ⋯ ε_{j_{k}}  (3.5)

with the help of some real numbers a(j_{1}, …, j_{k}) which are given for all sets of indices such that 1 ≤ j_{l} ≤ n, 1 ≤ l ≤ k, and j_{l} ≠ j_{l′} if l ≠ l′. Put

S^{2} = ∑_{(j_{1},...,j_{k}):1≤j_{l}≤n for all 1≤l≤k j_{l}≠j_{l′} if l≠l′} a^{2}(j_{1}, …, j_{k}).  (3.6)

Then

P (|Z| > x) ≤ C exp \{−B (\frac{x}{S} )^{2/k}\} for all x ≥ 0  (3.7)

with some constants B > 0 and C > 0 depending only on the parameter k. Relation (3.5) holds for instance with the choice B = \frac{k}{2e(k!)^{1/k}} and C = e^{k}.

Lemma 2 is a relatively simple consequence of an important result of the probability theory, the hypercontractive inequality for Rademacher functions (see e.g. [4] or [5]). It yields some moment inequalities that imply Lemma 2. Such an inequality is formulated e.g. in Theorem 3.2.2 of [5]. It states (with the choice p = 2 in this result and the observation EZ^{2} ≤ k!S^{2}) that

E|Z|^{q} ≤ (q − 1)^{kq/2}(k!S^{2})^{q/2}  for q ≥ 2.  (3.8)

Here I used the notation of Lemma 2.

The Markov inequality and inequality (3.8) imply that

P (|Z| > x) ≤ (q^{k/2} \frac{\sqrt{k!}S}{x} )^{q} for all x > 0 and q ≥ 2.

Choose the number q as the solution of the equation q (\frac{\sqrt{k!}S}{x} )^{2/k} = \frac{1}{e}. Then we get that

P (|Z| > x) ≤ exp \{−B (\frac{x}{S} )^{2/k}\} with B = \frac{k}{2e(k!)^{1/k}}, provided that q = \frac{1}{ek!^{1/k}} (\frac{x}{S} )^{2/k} ≥

2, i.e. B (\frac{x}{S} )^{2/k} ≥ k. By multiplying the above upper bound with C = e^{k} we get such an estimate for P (|Z| > x) which holds for all x > 0. In such a way we get the proof of Lemma 2.

Remark: The parameter B given in Lemma 2 is not sharp. In paper [9] I have shown that the right choice of B in formula (3.7) is B = \frac{1}{2}.

The second result I need is a slight generalization of a simple lemma that can be found for instance in Pollard’s book [12] (8^{∘} Symmetrization Lemma) or Lemma 2.5 in [7]. In this paper I need the result given in Lemma 3 below to carry out my arguments. Its proof consists of a slight modification of the method in [7] or [12].

Lemma 3. (Symmetrization Lemma) Let Z(n) and Z̄(n), n = 1, 2, …, be two sequences of random variables on a probability space (Ω, A, P). Let a σ-algebra B ⊂ A be given on the probability space (Ω, A, P) together with a B measurable set B and two numbers α > 0 and β > 0 such that the random variables Z_{n}, n = 1, 2, …, are B measurable, and the inequality

P (|Z̄_{n}| ≤ α|B)(ω) ≥ β for all n = 1, 2, … if ω ∈ B  (3.9)

holds. Then

P ( sup_{1≤n<∞} |Z_{n}| > α + x) ≤ \frac{1}{β} P ( sup_{1≤n<∞} |Z_{n} − Z̄_{n}| > x) + (1 − P (B)) for all x > 0.

(3.10)

In particular, if the sequences Z_{n}, n = 1, 2, …, and Z̄_{n}, n = 1, 2, …, are two independent sequences of random variables, and P (|Z̄_{n}| ≤ α) ≥ β for all n = 1, 2, …, then

P ( sup_{1≤n<∞} |Z_{n}| > α + x) ≤ \frac{1}{β} P ( sup_{1≤n<∞} |Z_{n} − Z̄_{n}| > x) .  (3.10′)

Proof of Lemma 3. Put τ = min{n: |Z_{n}| > α + x} if there exists such an n, and τ = 0 otherwise. Then

P (\{τ = n\} ∩ B) ≤ \frac{1}{β} ∫_{\{τ=n\}∩B} P (|Z̄_{n}| ≤ α|B) dP = \frac{1}{β} P (\{τ = n\} ∩ \{|Z̄_{n}| ≤ α\} ∩ B)

≤ \frac{1}{β} P (\{τ = n\} ∩ \{|Z_{n} − Z̄_{n}| > x\}) for all n = 1, 2, ….

Hence

P ( sup_{1≤n<∞} |Z_{n}| > α + x) − (1 − P (B)) ≤ P ({ sup_{1≤n<∞} |Z_{n}| > α + x} ∩ B)

= ∑_{n=1}^{∞} P (\{τ = n\} ∩ B) ≤ \frac{1}{β} ∑_{n=1}^{∞} P (\{τ = n\} ∩ \{|Z_{n} − Z̄_{n}| > x\})

≤ \frac{1}{β} P ( sup_{1≤n<∞} |Z_{n} − Z̄_{n}| > x) .

Thus formula 3.10 is proved. If Z_{n} and Z̄_{n} are two independent sequences, and P (|Z̄_{n}| ≤ α) ≥ β for all n = 1, 2, …, and we define B as the σ-algebra generated by the random variables Z_{n}, n = 1, 2, …, then condition (3.9) is satisfied also with B = Ω. Hence relation (3.10′) holds in this case. Lemma 3 is proved.

Before turning to the proof of Proposition 2′ I explain the main ideas of its proof. These ideas are taken from the paper [1] of Alexander.

Let us restrict our attention to the case k = 1. In this case a probability of the form

P (n^{−1/2} sup_{f∈F} | ∑_{j=1}^{n} f(ξ_{j})| > x) has to be estimated. By taking an independent copy of

the sequence ξ_{n} (which disappears at the end of the of the calculation) a symmetrization argument can be applied which reduces the problem to the estimation of the probability

P (n^{−1/2} sup_{f∈F} | ∑_{j=1}^{n} ε_{j}f(ξ_{j})| > x̄), where the random variables ε_{j}, P (ε_{j} = 1) = P (ε_{j} =

−1) = \frac{1}{2}, j = 1, …, n, are independent, and they are independent also of the random variables ξ_{j}. Beside this, the number x̄ is only slightly smaller than the number x/2. Let us bound the conditional probability of the event we have just introduced if the values random variables ξ_{j} are prescribed in it. This conditional probability can be bounded by means of the one-dimensional version of Lemma 2, and the estimate we get in such a way is useful if the conditional variance of the random variable we have to handle has a good upper bound. Such a bound exists, and some calculation reduces the original

problem to the estimation of the probability P (n^{−1/2} sup_{f∈F′} | ∑_{j=1}^{n} f(ξ_{j})| > x^{1+α}) with

some new nice class of functions F′ and number α > 0. This problem is very similar to the original one, but it is simpler, since the number x is replaced by a larger number x^{1+α} in it. By repeating this argument successively, in finitely many steps we get to an inequality that clearly holds.

The above sketched argument suggests a backward induction procedure to prove Proposition 2′. To carry out such a program I shall prove a result formulated in Proposition 4. First I introduce the following notion.

Definition of good tail behaviour for a class of U-statistics. Let us have some measurable space (X, X) and a probability measure μ on it. Let us consider some class F of functions f(x_{1}, …, x_{k}) on the k-fold product (X^{k}, X^{k}) of the space (X, X). Fix some positive integer n and positive number σ > 0, and take k independent copies ξ_{1,s}, …, ξ_{n,s}, 1 ≤ s ≤ k, of a sequence of independent μ-distributed random variables ξ_{1}, …, ξ_{n}. Let us introduce with the help of these random variables the decoupled Ustatistics Ī_{n,k}(f), f ∈ F. Given some real number T > 0 we say that the set of decoupled U-statistics determined by the class of functions F has a good tail behaviour at level T if the following inequality holds:

P (sup_{f∈F} |n^{−k/2}Ī_{n,k}(f)| ≥ An^{k/2}σ^{k+1}) ≤ exp {−A^{1/2k}nσ^{2}} for all A ≥ T. (3.11)

Now I formulate Proposition 4 which enables us to make the inductive procedure leading to the proof of Proposition 2′.

Proposition 4. Let us fix a positive integer n, real number 0 < σ ≤ 2^{−(k+1)} and a probability measure μ on a measurable space (X, X) together with a countable L_{2}- dense class F of canonical kernel functions f = f(x_{1}, …, x_{k}) (with respect to the measure μ) on the k-fold product space (X^{k}, X^{k}) with some exponent L ≥ 1 and parameter D > 0. Let us also assume that all functions f ∈ F satisfy the con-

ditions sup_{x_{j}∈X,1≤j≤k} |f(x_{1}, …, x_{k})| ≤ 2^{−(k+1)}, ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2},

and nσ^{2} > K(L + β) log n with a sufficiently large fixed number K = K(k) and β = max (\frac{log D}{log n} , 0).

There exists some real number A_{0} = A_{0}(k) > 1 such that for all classes of functions F which satisfy the above conditions of Proposition 4 the set of decoupled U-statistics determined by the functions f ∈ F have a good tail behaviour at level T for some T ≥ A_{0}, provided that for all classes of functions F with such properties the set of decoupled Ustatistics with kernel functions f ∈ F have a good tail behaviour at level T^{4/3}.

It is not difficult to deduce Proposition 2′ from Proposition 4. Indeed, let us observe that the set of (decoupled) U-statistics determined by a class of functions F satisfying the conditions of Proposition 4 has a good tail-behaviour at level T_{0} = σ^{−(k+1)}, since the probability at the left-hand side of (3.11) equals zero for x > σ^{−(k+1)}. Then we get from Proposition 4 by induction with respect to the number j that all sets of U-statistics Ī_{n,k}(f), f ∈ F, with a class of functions F satisfying the conditions of Proposition 4 have a good tail-behaviour also for T ≥ T_{0}^{(3/4)^{j}} = σ^{−(3/4)^{j}(k+1)} for all j = 1, 2, … such that σ^{−(3/4)^{j}(k+1)} ≥ A_{0}. This implies that if a class of functions F satisfies the conditions of Proposition 4, then the set of U-statistics determined by this class of functions has a good tail-behaviour at level T = A_{0}^{4/3}, i.e. at a level which depends only on the order k of the (decoupled) U-statistics. This result implies Proposition 2′, only we have to apply it not directly for the class of functions F appearing in Proposition 2′, but these functions have to be multiplied by a sufficiently small positive number depending only on k.

Thus to complete the proof of Theorem 2 it is enough to prove Proposition 4. I describe its proof in the special case k = 1 in the next section. This case is considered separately, because it may help to understand the ideas of the proof in the general case.

The main difficulty in the proof of Proposition 4 is related to a symmetrization procedure which is an essential part of the proof. I want to apply some randomization with the help of a symmetrization argument, and this requires a special justification. It is not difficult to justify the right for this randomization in the case k = 1, when it simply follows from Lemma 3 and a (simple) estimation of the variance of an appropriate U-statistic, but it becomes hard for k ≥ 2. In this case we have to give a good estimate on certain conditional variances of some (decoupled) U-statistics with respect to some appropriate conditions. To overcome this difficulty I formulate a result in Proposition 5 and prove Propositions 4 and 5 simultaneously. Their proof follows the following line.

First Proposition 4 and Proposition 5 will be proved for k = 1. Then, if Propositions 4 and 5 are already proven for all k′ < k, then first I prove Proposition 4 for k, and then Proposition 5 for the same k. Proposition 5 has a structure similar to that of Proposition 4. Before its formulation I introduce the following definition.

Definition of good tail behaviour for a class of integrals of U-statistics. Let us have a product space (X^{k} × Y, X^{k} × Y) with some product measure μ^{k} × ρ, where (X^{k}, X^{k}, μ^{k}) is the k-fold product of some probability space (X, X , μ), and (Y, Y, ρ) is some other probability space. Fix some positive integer n and positive number σ > 0, and consider some class F of functions f(x_{1}, …, x_{k}, y) on the product space (X^{k} × Y, X^{k} × Y, μ^{k} × ρ). Take k independent copies ξ_{1,s}, …, ξ_{n,s}, 1 ≤ s ≤ k, of a sequence of independent, μ-distributed random variables ξ_{1}, …, ξ_{n}. For all f ∈ F and y ∈ Y let us define the decoupled U-statistics Ī_{n,k}(f, y) by means of these random variables ξ_{1,s}, …, ξ_{n,s}, 1 ≤ s ≤ k, and the kernel function f_{y}(x_{1}, …, x_{k}) = f(x_{1}, …, x_{k}, y) in formula (3.1). Define with the help of these U-statistics Ī_{n,k}(f, y) the random integrals

H_{n,k}(f) = ∫ Ī_{n,k}(f, y)^{2}ρ( dy), f ∈ F.  (3.12)

Choose some real number T > 0. We say that the set of random integrals H_{n,k}(f), f ∈ F, have a good tail behaviour at level T if

P (sup_{f∈F} n^{−k}H_{n,k}(f) ≥ A^{2}n^{k}σ^{2k+2}) ≤ exp {−A^{1/(2k+1)}nσ^{2}} for A ≥ T. (3.13)

Proposition 5. Fix some positive integer n and real number 0 < σ ≤ 2^{−(k+1)}, and let us have a product space (X^{k} × Y, X^{k} × Y) with some product measure μ^{k} × ρ, where (X^{k}, X^{k}, μ^{k}) is the k-fold product of some probability space (X, X , μ), and (Y, Y, ρ) is some other probability space. Let us have a countable L_{2}-dense class F of canonical functions f(x_{1}, …, x_{k}, y) on the product space (X^{k} × Y, X^{k} × Y, μ^{k} × ρ) with some exponent L ≥ 1 and parameter D > 0. Let us also assume that the functions f ∈ F satisfy the conditions

sup_{x_{j}∈X,1≤j≤k,y∈Y} |f(x_{1}, …, x_{k}, y)| ≤ 2^{−(k+1)}

and

∫ f^{2}(x_{1}, …, x_{k}, y)μ( dx_{1}) … μ( dx_{k})ρ( dy) ≤ σ^{2} for all f ∈ F.

Let the inequality nσ^{2} > K(L + β) log n hold with a sufficiently large fixed number K = K(k).

There exists some number A_{0} = A_{0}(k) > 1 such that for all classes of functions F which satisfy the conditions of Proposition 5 the random integrals H_{n,k}(f), f ∈ F, defined in (3.9) have a good tail behaviour at level T, provided that the random integrals H_{n,k}(f), f ∈ F, of all classes F with such properties have a good tail behaviour at level T^{(2k+1)/2k}.

Similarly to the argument formulated after Proposition 4 an inductive procedure yields the following corollary of Proposition 5.

Corollary of Proposition 5. If the class of functions F satisfies the conditions of Proposition 5, then there exists a constant Ā_{0} = Ā_{0}(k) > 0 depending only on k such that the integrals H_{n,k}(f) determined by the class of functions F have a good tail behaviour at level Ā_{0}.

4. The proof of Proposition 4 in the case k = 1

In this section Proposition 4 is proved in the special case k = 1. In this case we have to show that

P (\frac{1}{\sqrt{n}} sup_{f∈F} |∑_{j=1}^{n} f(ξ_{j})| ≥ An^{1/2}σ^{2}) ≤ e^{−A^{1/2}nσ^{2}} if A ≥ T  (4.1)

if we know the same estimate for A > T^{4/3} and all classes of functions satisfying the conditions of Proposition 4. This statement will be proved by means of the following symmetrization argument.

Lemma 4. Let the class of functions F satisfy the conditions of Proposition 4 for k = 1. Let ε_{1}, …, ε_{n} be a sequence of independent random variables, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, independent also of the μ distributed random variables ξ_{1}, …, ξ_{n}. Then

P (\frac{1}{\sqrt{n}} sup_{f∈F} |∑_{j=1}^{n} f(ξ_{j})| ≥ An^{1/2}σ^{2})

≤ 4P (\frac{1}{\sqrt{n}} sup_{f∈F} |∑_{j=1}^{n} ε_{j}f(ξ_{j})| ≥ \frac{A}{3}n^{1/2}σ^{2}) if A ≥ T.

(4.2)

There are several similar results in the literature. Lemma 4 follows simply from Part b) of Lemma 2.7 in [7] with the choice t = Anσ^{2}. (The quantity α in this result agrees with our σ.) It is enough to check that t ≥ 2^{1/2}n^{1/2}σ and (t − 2^{1/2}n^{1/2}σ)/2 ≥ \frac{A}{3}nσ^{2} if A ≥ T ≥ A_{0} is chosen sufficiently large, since under the conditions of Proposition 4 (if the parameter K is sufficiently large in Proposition 4) nσ^{2} ≥ 1.

To prove Proposition 4 for k = 1 let us investigate the conditional probability

P (f, A|ξ_{1}, …, ξ_{n}) = P ( \frac{1}{\sqrt{n}} |∑_{j=1}^{n} ε_{j}f(ξ_{j})| ≥ \frac{A}{6}\sqrt{n}σ^{2}| ξ_{1}, …, ξ_{n})

for all functions f ∈ F, A ≥ T and values (ξ_{1}, …, ξ_{n}). By Lemma 2 (with k = 1) we can write

P (f, A|ξ_{1}, …, ξ_{n}) ≤ C exp \{−\frac{\frac{B}{36}A^{2}nσ^{4}}{S^{2}(f, ξ_{1}, …, ξ_{n})}\}  (4.3)

with

S^{2}(f, x_{1}, …, x_{n}) = \frac{1}{n} ∑_{j=1}^{n} f^{2}(x_{j}), f ∈ F.

Let us introduce the set

H = H(A) = {(x_{1}, …, x_{n}): sup_{f∈F} S^{2}(f, x_{1}, …, x_{n}) ≥ (1 + A^{4/3}) σ^{2}} .  (4.4)

I claim that

P ((ξ_{1}, …, ξ_{n}) ∈ H) ≤ e^{−A^{2/3}nσ^{2}} if A ≥ T.  (4.5)

To prove relation (4.5) let us consider the functions f̄ = f̄(f) for all f ∈ F defined by the formula f̄(x) = f^{2}(x) − ∫ f^{2}(x)μ( dx), and introduce the class of functions F′ = {f̄(f): f ∈ F}. Let us show that the class of functions F′ satisfies the conditions of Proposition 4. By the assumption of Proposition 4 this implies that the estimate (3.11) with k = 1, i.e. the estimate (4.1) holds for the class of functions F′ if the condition A ≥ T is replaced by A ≥ T^{4/3} in it.

Relation ∫ f̄(x)μ( dx) = 0 clearly holds. (In the case k = 1 this means that f̄ is a canonical function.) The condition sup |f̄(x)| ≤ \frac{1}{8} < \frac{1}{4} also holds if sup |f(x)| ≤ \frac{1}{4}, and ∫ f̄^{2}(x)μ( dx) ≤ ∫ f^{4}(x)μ( dx) ≤ \frac{1}{4} ∫ f^{2}(x) μ( dx) ≤ \frac{σ^{2}}{4} < σ^{2} if f ∈ F. It remained to show that F′ is an L_{2}-dense class with exponent L and parameter D.

To show this observe that ∫ (f̄(x) − ḡ(x))^{2}ρ( dx) ≤ 2 ∫ (f^{2}(x) − g^{2}(x))^{2}ρ( dx) + 2 ∫ (f^{2}(x) − g^{2}(x))^{2}μ( dx) ≤ 2(sup(|f(x)| + |g(x)|)^{2} (∫ (f(x) − g(x))^{2}(ρ( dx) + μ( dx)) ≤ ∫ (f(x) − g(x))^{2}ρ̄( dx) for all f, g ∈ F, f̄ = f̄(f), ḡ = ḡ(g) and probability measure ρ, where ρ̄ = \frac{ρ+μ}{2}. This means that if \{f_{1}, …, f_{m}\} is an ε-dense subset of F in the space L_{2}(X, X , ρ̄), then {f̄_{1}, …, f̄_{m}} is an ε-dense subset of F′ in the space L_{2}(X, X , ρ), and not only F, but also F′ is an L_{2}-dense class with exponent L and parameter D.

We get, by applying formula (4.1) for the number A^{4/3} ≥ T^{4/3} and the class of functions F′ that

P ((ξ_{1}, …, ξ_{n}) ∈ H) = P (sup_{f∈F} (\frac{1}{n} ∑_{j=1}^{n} f̄(ξ_{j}) + \frac{1}{n} ∑_{j=1}^{n} Ef^{2}(ξ_{j})) ≥ (1 + A^{4/3}) σ^{2})

≤ P (sup_{f∈F} \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f̄(ξ_{j}) ≥ A^{4/3}n^{1/2}σ^{2}) ≤ e^{−A^{2/3}nσ^{2}},

i.e. relation (4.5) holds.

Formula (4.3) and the definition (4.4) of the set H yield the estimate

P (f, A|ξ_{1}, …, ξ_{n}) ≤ Ce^{−BA^{2/3}nσ^{2}/40} if (ξ_{1}, …, ξ_{n}) ∉ H  (4.6)

for all f ∈ F and A ≥ T for the conditional probability P (f, A|ξ_{1}, …, ξ_{n}). Let us introduce the conditional probability

P (F, A|ξ_{1}, …, ξ_{n}) = P ( sup_{f∈F} \frac{1}{\sqrt{n}} |∑_{j=1}^{n} ε_{j}f(ξ_{j})| ≥ \frac{A}{3}\sqrt{n}σ^{2}| ξ_{1}, …, ξ_{n})

for all (ξ_{1}, …, ξ_{n}) and A ≥ T. We shall estimate this conditional probability with the help of relation (4.6) if (ξ_{1}, …, ξ_{n}) ∉ H. Given some set of n points (x_{1}, …, x_{n}) in the space (X, X) let us introduce the measure ν = ν(x_{1}, …, x_{n}) on (X, X) in such a way that ν is concentrated in the points x_{1}, …, x_{n}, and ν(\{x_{j}\}) = \frac{1}{n}. If ∫ f^{2}(x)ν( dx) ≤ δ^{2}

for a function f, then |\frac{1}{\sqrt{n}} ∑_{j=1}^{n} ε_{j}f(x_{j})| ≤ n^{1/2} ∫ |f(x)|ν( dx) ≤ n^{1/2}δ. Since we have

assumed that nσ^{2} ≥ 1, this estimate implies that if f and g are two functions such that

∫ (f − g)^{2}ν( dx) ≤ δ^{2} with δ = \frac{A}{6n}, then |\frac{1}{\sqrt{n}} ∑_{j=1}^{n} ε_{j}f(x_{j}) − \frac{1}{\sqrt{n}} ∑_{j=1}^{n} ε_{j}g(x_{j})| ≤ \frac{A}{6\sqrt{n}} ≤

\frac{A}{6} \sqrt{n}σ^{2}.

Given some (random) point (ξ_{1}, …, ξ_{n}) ∈ H let us consider the measure ν = ν(ξ_{1}, …, ξ_{n}) corresponding to it, and choose a δ̄-dense subset {f_{1}, …, f_{m}} of F in the space L_{2}(X, X , ν) with δ̄ = \frac{1}{6n} ≤ δ = \frac{A}{6n}, whose cardinality m satisfies the inequality m ≤ Dδ̄^{−L}. This is possible because of the L_{2}-dense property of the class F. (This is the point where the L_{2}-dense property of the class of functions F is exploited in its full

strength.) The above facts imply that P (F, A|ξ_{1}, …, ξ_{n}) ≤ ∑_{l=1}^{m} P (f_{l}, A|ξ_{1}, …, ξ_{n}) with

these functions f_{1}, …, f_{m}. Hence relation (4.6) yields that

P (F, A|ξ_{1}, …, ξ_{n}) ≤ CD(6n)^{L}e^{−BA^{2/3}nσ^{2}/40} if (ξ_{1}, …, ξ_{n}) ∉ H and A ≥ T.

This inequality together with Lemma 4 and estimate (4.5) imply that

P (\frac{1}{\sqrt{n}} sup_{f∈F} |∑_{j=1}^{n} f(ξ_{j})| ≥ An^{1/2}σ^{2}) ≤ 4P (\frac{1}{\sqrt{n}} sup_{f∈F} |∑_{j=1}^{n} ε_{j}f(ξ_{j})| ≥ \frac{A}{3}n^{1/2}σ^{2})

≤ 4CD(6n)^{L}e^{−BA^{2/3}nσ^{2}/40} + 4e^{−A^{2/3}nσ^{2}} if A ≥ T.

(4.7)

Since we have a better power of A in the exponent at the right-hand side of formula (4.7) than we need, the relation nσ^{2} ≥ K(L + β) log n holds, and we have the right to choose the constants K and A_{0}, A ≥ A_{0}, sufficiently large, it is not difficult to deduce relation (4.1) from relation (4.7). Indeed, the expression in the exponent at the righthand side of (4.7) satisfies the inequality \frac{B}{40}A^{2/3}nσ^{2} ≥ A^{1/2}nσ^{2} + K(L + β) log n if A_{0} is sufficiently large, and

P (\frac{1}{\sqrt{n}} sup_{f∈F} |∑_{j=1}^{n} f(ξ_{j})| ≥ An^{1/2}σ^{2})

≤ 4C(6n)^{β+L}e^{−K}n^{−K(L+β)}e^{−A^{1/2}nσ^{2}} + 4e^{−A^{2/3}nσ^{2}} ≤ e^{−A^{1/2}nσ^{2}}

if A ≥ T, and the constants A_{0} and K are chosen sufficiently large.

5. The symmetrization argument

In the proof of Propositions 4 and 5 we need two symmetrization results for all k ≥ 1 which play the same role as Lemma 4 in the case k = 1. These results are described in Lemmas 5A and 5B. In this section these results are formulated and proved. The proofs go by induction with respect to k. During the proof of Propositions 4 and 5 for k we may assume that they hold for k′ < k.

Lemma 5A. Let F be a class of functions on the space (X^{k}, X^{k}) which satisfies the conditions of Proposition 4 with some probability measure μ. Let us have k independent copies ξ_{1,s}, …, ξ_{n,s}, 1 ≤ s ≤ k, of a sequence of independent μ distributed random variables ξ_{1}, …, ξ_{n}, and a sequence of independent random variables ε = (ε_{1}, …, ε_{n}), P (ε_{s} = 1) = P (ε_{s} = −1) = \frac{1}{2}, which is independent also of the random variables ξ_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k. Consider the decoupled U-statistics Ī_{n,k}(f), f ∈ F, defined from these random variables by formula (3.1) and their randomized version

Ī_{n,k}^{ε}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ε_{j_{1}} ⋯ ε_{j_{k}}f (ξ_{j_{1},1}, …, ξ_{j_{k},k}) , f ∈ F.  (5.1)

There exists some constant A_{0} = A_{0}(k) such that the inequality

\begin{aligned}P (sup_{f∈F} n^{−k/2} |Ī_{n,k}(f)| > An^{k/2}σ^{k+1}) & < 2^{k+1}P (sup_{f∈F} |Ī_{n,k}^{ε}(f)| > 2^{−(k+1)}An^{k}σ^{k+1}) \\ & + 2^{k}n^{k−1}e^{−A^{1/(2k−1)}nσ^{2}/k} \end{aligned}

(5.2)

holds for all A ≥ A_{0}.

Before formulating Lemma 5B needed in the proof of Proposition 5 I introduce some notations. Some of them will be needed later.

Let us consider a set F of functions f(x_{1}, …, x_{k}, y) ∈ F on a space (X^{k} × Y, X^{k} × Y, μ^{k} × ρ) which satisfies the conditions of Proposition 5. Let us choose 2k independent copies ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)}, ξ_{1,s}^{(−1)}, …, ξ_{n,s}^{(−1)}, 1 ≤ s ≤ k, of a sequence of independent μ distributed random variables ξ_{1}, …, ξ_{n} together with a sequence of independent random variables (ε_{1}, …, ε_{n}), P (ε_{s} = 1) = P (ε_{s} = −1) = \frac{1}{2}, 1 ≤ s ≤ n, which are independent of them. For all subsets V ⊂ {1, …, k} of the set {1, …, k} let |V | denote the cardinality of this set, and define for all functions f(x_{1}, …, x_{k}, y) ∈ F and V ⊂ {1, …, k} the decoupled U-statistics

Ī_{n,k}^{V}(f, y) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f (ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y) , f ∈ F,  (5.3)

where δ_{s} = ±1, 1 ≤ s ≤ k, δ_{s} = 1 if s ∈ V, and δ_{s} = −1 if s ∉ V, together with the random variables

H_{n,k}^{V}(f) = ∫ Ī_{n,k}^{V}(f, y)^{2}ρ( dy), f ∈ F.  (5.3′)

Put

Ī_{n,k}(f, y) = Ī_{n,k}^{{1,...,k}}(f, y), H_{n,k}(f) = H_{n,k}^{{1,...,k}}(f),  (5.3′′)

i.e. these random variables agree with those defined in (5.3) and (5.3′) with the choice V = {1, …, k}.

Let us also define the ‘randomized version’ of the random variables Ī_{n,k}^{V}(f, y) and H_{n,k}^{V}(f) as

Ī_{n,k}^{(V,ε)}(f, y) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ε_{j_{1}} ⋯ ε_{j_{k}}f (ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y) , f ∈ F,  (5.4)

where δ_{s} = 1 if s ∈ V, and δ_{s} = −1 if s ∉ V, and

H_{n,k}^{(V,ε)}(f) = ∫ Ī_{n,k}^{(V,ε)}(f, y)^{2}ρ( dy), f ∈ F.  (5.4′)

Let us also introduce the random variables

W̄ (f) = ∫ [ ∑_{V ⊂{1,...,k}}(−1)^{|V |}Ī_{n,k}^{(V,ε)}(f, y)]^{2} ρ( dy), f ∈ F.  (5.5)

Now I formulate the symmetrization result applied in the proof of Proposition 5.

Lemma 5B. Let F be a set of functions on (X^{k} × Y, X^{k} × Y) which satisfies the conditions of Proposition 5 with some probability measure μ^{k} × ρ. Let us have 2k independent copies ξ_{1,s}^{±1}, …, ξ_{n,s}^{±1}, 1 ≤ s ≤ k, of a sequence of independent μ distributed random variables together with a sequence of independent random variables ε_{1}, …, ε_{n}, P (ε_{s} = 1) = P (ε_{s} = −1) = \frac{1}{2}, 1 ≤ s ≤ n, which is independent of them.

There exists some A_{0} = A_{0}(k) such that if the integrals H_{n,k}(f), f ∈ F, determined by this class of functions F have a good tail behaviour at level T^{(2k+1)/2k} for some T ≥ A_{0}, (this property was defined at the end of Section 3), then the inequality

\begin{aligned}P (sup_{f∈F} H_{n,k}(f) > A^{2}n^{2k}σ^{2(k+1)}) & < 2P (sup_{f∈F} |W̄ (f)| > \frac{A^{2}}{2} n^{2k}σ^{2(k+1)}) \\ & + 2^{2k+1}n^{k−1}e^{−A^{1/2k}nσ^{2}/k} \end{aligned}  (5.6)

holds with the random variables H_{n,k}(f) and W̄ (f) defined in formulas (5.3′′) and (5.5) for all A ≥ T.

Let us observe that in the symmetrization argument of Lemma 5B we have applied the randomization Ī_{n,k}^{(V,ε)}(f, y) of Ī_{n,k}^{(V)}(f, y), (compare formulas (5.3) and (5.4)), and compared the integral of the square of the random function Ī_{n,k}(f, y) with the integral of the square of a linear combination of the random functions Ī_{n,k}^{(V,ε)}(f, y). After this integration the effect of the ‘randomizing factors’ ε_{j} will be weaker. Nevertheless, also such an estimate will be sufficient for us. But the effect of this symmetrization procedure has to be followed more carefully. Hence a corollary of Lemma 5B will be presented which can be better applied than the original lemma. We get it by rewriting the random variable W̄ (f) defined in (5.5) in another form with the help of some diagrams introduced below.

Let G = G(k) denote the set of all diagrams consisting of two rows such that both rows are the set {1, …, k} and the diagrams of G contain some edges (l_{1}, l′_{1}), …, (l_{s}, l′_{s}), 0 ≤ s ≤ k connecting some points (vertices) of the first row with some points of the second row. The vertices l_{1}, …, l_{s} in the first row are all different, and the same relation holds also for the vertices l′_{1}, …, l′_{s} in the second row. For each diagram G ∈ G let us define e(G) = {(l_{1}, l′_{1}) …, (l_{s}, l′_{s})}, the set of its edges, v_{1}(G) = {l_{1}, …, l_{s}}, the set of vertices in the first row and v_{2}(G) = {l′_{1}, …, l′_{s}}, the set of vertices in the second row of G from which an edge starts.

Given some diagram G ∈ G and two sets V_{1}, V_{2} ⊂ {1, …, k}, we define with the help of the random variables ξ_{s,1}^{(1)}, …, ξ_{s,n}^{(1)}, ξ_{s,1}^{(−1)}, …, ξ_{s,n}^{(−1)}, 1 ≤ s ≤ k, and ε = (ε_{1}, …, ε_{n}) taking part in the definition of the expressions W̄ (f), f ∈ F, the random variables H_{n,k}(f|G, V_{1}, V_{2}):

H_{n,k}(f|G, V_{1}, V_{2}) = ∑_{(j_{1},...,j_{k}, j′_{1},...,j′_{k}) 1≤j_{s}≤n, j_{s}≠j_{s′} if s≠s′, 1≤s,s′≤k, 1≤j′_{s}≤n, j′_{s}≠j′_{s′} if s≠s′, 1≤s,s′≤k, j_{s}=j′_{s′} if (s,s′)∈e(G), j_{s}≠j′_{s′} if (s,s′)∉e(G)} ∏_{s∈{1,...,k}\v_{1}(G)}ε_{j_{s}} ∏_{s∈{1,...,k}\v_{2}(G)}ε_{j′_{s}}

\frac{1}{k!^{2}} ∫ f(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)f(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y)ρ( dy), f ∈ F, (5.7)

where δ_{s} = 1 if s ∈ V_{1}, δ_{s} = −1 if s ∉ V_{1}, and δ̄_{s} = 1 if s ∈ V_{2}, δ̄_{s} = −1 if s ∉ V_{2}.

With the help of these random variables we can write that

W̄ (f) = ∑_{G∈G, V_{1},V_{2}⊂{1,...,k}}(−1)^{|V_{1}|+|V_{2}|}H_{n,k}(f|G, V_{1}, V_{2}) for all f ∈ F,

because

∫ Ī_{n,k}^{(V_{1},ε)}(f, y)Ī_{n,k}^{(V_{2},ε)}(f, y)ρ( dy) = ∑_{G∈G} H_{n,k}(f|G, V_{1}, V_{2}), for all V_{1}, V_{2} ⊂ {1, …, k}.

Since the number of terms in this sum is less than 2^{4k}k!, it implies that Lemma 5B has the following corollary:

Corollary of Lemma 5B. Let a set of functions F satisfy the conditions of Proposition 5. Then there exists some A_{0} = A_{0}(k) such that if the integrals H_{n,k}(f), f ∈ F, determined by this class of functions F have a good tail behaviour at level T^{(2k+1)/2k} for some T ≥ A_{0}, then the inequality

P (sup_{f∈F} H_{n,k}(f) > A^{2}n^{2k}σ^{2(k+1)})

≤ 2 ∑_{G∈G, V_{1},V_{2}∈\{1,...,k\}} P (sup_{f∈F} |H_{n,k}(f|G, V_{1}, V_{2})| > \frac{A^{2}}{2^{4k+1}k!}n^{2k}σ^{2(k+1)})

+ 2^{2k+1}n^{k−1}e^{−A^{1/2k}nσ^{2}/k}  (5.8)

holds with the random variables H_{n,k}(f) and H_{n,k}(f|G, V_{1}, V_{2}) defined in formulas (5.3′′) and (5.7) for all A ≥ T.

The proof of Lemmas 5A and 5B uses the result of the following Lemma 6 which states that certain random vectors have the same distribution.

Lemma 6. Let ε = (ε_{1}, …, ε_{n}) be a sequence of independent random variables, P (ε_{s} = 1) = P (ε_{s} = −1) = \frac{1}{2}, 1 ≤ s ≤ n, which is independent also of 2k fixed independent copies ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)} and ξ_{1,s}^{(−1)}, …, ξ_{n,s}^{(−1)}, 1 ≤ s ≤ k, of a sequence ξ_{1}, …, ξ_{n} of independent μ distributed random variables.

a) Let F be a class of functions which satisfies the conditions of Proposition 4. With the help of the above random variables introduce the decoupled U-statistic

Ī_{n,k}^{V}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f (ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}) , f ∈ F,  (5.9)

for all sets V ⊂ {1, …, k} and functions f ∈ F together with its ‘randomized version’

Ī_{n,k}^{(V,ε)}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ε_{j_{1}} ⋯ ε_{j_{k}}f (ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}) , f ∈ F,  (5.9′)

where δ_{s} = ±1, 1 ≤ s ≤ k, δ_{s} = 1 if s ∈ V, and δ_{s} = −1 if s ∉ V.

Then the sets of random variables

S(f) = ∑_{V ⊂{1,...,k}}(−1)^{|V |}Ī_{n,k}^{V}(f), f ∈ F,  (5.10)

and sets of random variables

S̄(f) = ∑_{V ⊂{1,...,k}}(−1)^{|V |}Ī_{n,k}^{(V,ε)}(f), f ∈ F,  (5.10′)

have the same joint distribution.

b) Let F be a class of functions satisfying Proposition 5. For all functions f ∈ F and V ⊂ {1, …, k} consider the decoupled U-statistics Ī_{n,k}^{V}(f, y) determined by the

random variables ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)} and ξ_{1,s}^{(−1)}, …, ξ_{n,s}^{(−1)}, 1 ≤ s ≤ k, by formula (5.3), and define with their help the random variables

W (f) = ∫ [ ∑_{V ⊂{1,...,k}}(−1)^{|V |}Ī_{n,k}^{V}(f, y)]^{2} ρ( dy), f ∈ F.  (5.11)

Then the random vectors {W (f): f ∈ F} defined in (5.11) and {W̄ (f): f ∈ F} defined in (5.5) have the same distribution.

Proof of Lemma 6. Let us consider Part a) of Lemma 6. I claim that for all M ∈ {1, …, n} the conditional distribution of the random vector in (5.10′) under the condition that ε_{j} = 1 if j ∈ M and ε_{j} = −1 if ε_{j} ∈ {1, …, n}\M agrees with the distribution of the vector in (5.10). Since the distribution of the vector in (5.10) does not change if we exchange the random variables ξ_{j,s}^{(1)} and ξ_{j,s}^{(−1)} in it for j ∉ M, 1 ≤ s ≤ k, and do not exchange them otherwise, it is enough to understand that the random vector we get from the vector in (5.10) after this transformation agrees with the random vector in (5.10′) if we write ε_{j} = 1 for j ∈ M and ε_{j} = −1 for j ∉ M in it. These random vectors really agree (not only in distribution) since for all functions f ∈ F both vectors have a component which is the sum of terms of the form f(ξ_{j_{1},1}^{(δ_{j_{1}} )}, …, ξ_{j_{k},k}^{(δ_{j_{k}})}), δ_{j_{s}} = ±1, 1 ≤ s ≤ k, multiplied with an appropriate power of −1, and this power equals the number of −1 components in the sequence δ_{j_{1}}, …, δ_{j_{k}} plus the cardinality of the set {j_{1}, …, j_{k}} ∩ M.

Part b) of Lemma 6 can be proved in the same way, hence it is omitted.

Lemma 5A will be proved with the help of part a) of Lemma 6 and the following Lemma 7A.

Lemma 7A. Let us consider a class of functions F satisfying the conditions of Proposition 4 and the random variables Ī_{n,k}^{V}(f), f ∈ F, V ⊂ {1, …, k}, defined in for-

mula (5.1). Let B = B(ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)}; 1 ≤ s ≤ k) denote the σ-algebra generated by the random variables ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)} , 1 ≤ s ≤ k, taking part in the definition of the random variables Ī_{n,k}^{V}(f). For all V ⊂ {1, …, k}, V ≠ {1, …, k}, there exists a number A_{0} = A_{0}(k) > 0 such that the inequality

P (sup_{f∈F} E (Ī_{n,k}^{V}(f)^{2}| B) > 2^{−(3k+3)}A^{2}n^{2k}σ^{2k+2}) < n^{k−1}e^{−A^{1/(2k−1)}nσ^{2}/k} (5.12)

holds for all A ≥ A_{0}.

Proof of Lemma 7A. Let us first consider the case V = ∅. We have E (Ī_{n,k}^{∅}(f)^{2}| B) =

E (Ī_{n,k}^{∅}(f)^{2}) ≤ \frac{n!}{k!}σ^{2} ≤ n^{2k}σ^{2k+2} for all f ∈ F. In the above calculation we exploited that the functions f ∈ F are canonical, and this implies certain orthogonalities, and beside this the inequality nσ^{2} ≥ 1 holds. The above relation implies inequality (5.12) for V = ∅ for all ω ∈ Ω if the number A_{0} is chosen sufficiently large.

To avoid some complications in the notation let us restrict our attention to the sets V = {1, …, u}, 1 ≤ u < k, and prove relation (5.12) for such sets. For this goal let us introduce the random variables

Ī_{n,k}^{V}(f, j_{u+1}, …, j_{k}) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,u \\ j_{s}≠j_{s′} if s≠s′, 1≤s,s′≤k \end{matrix}} f (ξ_{j_{1},1}^{(1)}, …, ξ_{j_{u},u}^{(1)}, ξ_{j_{u+1},u+1}^{(−1)}, …, ξ_{j_{k},k}^{(−1)}) ,

for all f ∈ F, i.e. we fix some indices j_{u+1}, …, j_{k}, 1 ≤ j_{s} ≤ n, u + 1 ≤ s ≤ k, j_{s} ≠ j_{s′} if s ≠ s′, and sum up only those terms in the sum defining Ī_{n,k}^{V}(f) which contain

ξ_{j_{u+1},u+1}^{(−1)}, …, ξ_{j_{k},k}^{(−1)} in their last k − u coordinates. Then we can write

\begin{aligned}E (Ī_{n,k}^{V}(f)^{2}| B) & = E ((  ∑_{\begin{matrix}1≤j_{s}≤n s=u+1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} Ī_{n,k}^{V}(f, j_{u+1}, …, j_{u_{k}}))^{2}| B) \\ & = ∑_{\begin{matrix}1≤j_{s}≤n s=u+1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} E (Ī_{n,k}^{V}(f, j_{u+1}, …, j_{u_{k}})^{2}| B) . \end{aligned}  (5.13)

The last relation follows from the identity

E (Ī_{n,k}^{V}(f, j_{u+1}, …, j_{u_{k}})Ī_{n,k}^{V}(f, j′_{u+1}, …, j′_{u_{k}})| B) = 0

if (j_{u+1}, …, j_{k}) ≠ (j′_{u+1}, …, j′_{k}), which relation holds, since f is a canonical function. It follows from relation (5.13) that

{ω: sup_{f∈F} E (Ī_{n,k}^{V}(f)^{2}| B) (ω) > 2^{−(3k+3)}A^{2}n^{2k}σ^{2k+2}}

⊂ ⋃_{\begin{matrix}1≤j_{s}≤n s=u+1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} \{ω: sup_{f∈F} E (Ī_{n,k}^{V}(f, j_{u+1}, …, j_{u_{k}})^{2}| B) (ω) > \frac{A^{2}n^{2k}σ^{2k+2}}{2^{(3k+3)}n^{k−u}} \} .

(5.14)

The probability of the events in the union at the right-hand side of (5.14) can be estimated with the help of the corollary of Proposition 5 with parameter u < k instead of k. (We may assume that Proposition 5 holds for u < k.) This corollary yields that

P (sup_{f∈F} E (Ī_{n,k}^{V}(f, j_{u+1}, …, j_{u_{k}})^{2}| B) > \frac{A^{2}σ^{2k+2}n^{k+u}}{2^{(3k+3)}} ) ≤ e^{−A^{−1/(2u+1)}(n−u)σ^{2}}. (5.15)

Indeed, the expression E (Ī_{n,k}^{V}(f, j_{u+1}, …, j_{u_{k}})^{2}| B) can be calculated in the following way: Take the decoupled U-statistic

Ī_{n,k}^{V}(f, x_{u+1}, …, x_{k}) = \frac{1}{k!} ∑_{\begin{matrix}j_{s}∈\{1,...,n\}\\{j_{u+1},...,j_{k}\}, \\ s=1,...,u, j_{s}≠j_{s′} if s≠s′ \end{matrix}} f (ξ_{j_{1},1}^{(1)}, …, ξ_{j_{u},u}^{(1)}, x_{u+1}, …, x_{k})

(5.16)

of order u with sample size n − k + u, and integrate the square of this function with respect to the variables x_{u+1}, …, x_{k} by the measure μ^{k−u}. The expression at the left-hand side of (5.15) can be bounded by means of Proposition 5 if we apply it for our class of functions F considering them as functions on (X^{u} × Y, X^{u} × Y, μ^{u} × ρ) with (Y, Y, ρ) = (X^{k−u}, X^{k−u}, μ^{k−u}). (A small inaccuracy was committed in the above statement because to define the expression in (5.16) as a U-statistic we should have divided by u! instead of k!. But this causes no real problem.)

We get inequality (5.15) from Proposition 5 by replacing the level \frac{A^{2}σ^{2k+2}n^{k+u}}{2^{(3k+3)}} in the probability at the left-hand side by A^{2}(n − u)^{2u}σ^{2u+2} < \frac{A^{2}σ^{2k+2}n^{k+u}}{2^{(2k+2)}} . The last inequality really holds if the constant K is chosen sufficiently large in the condition nσ^{2} > K log n of Proposition 4.

Relations (5.14) and (5.15) imply that

P (sup_{f∈F} E (Ī_{n,k}^{V}(f)^{2}| B) (ω) > 2^{−(3k+3)}A^{2}n^{2k}σ^{2k+2}) ≤ n^{k−u}e^{−A^{−1/(2u+1)}(n−u)σ^{2}},

and u ≤ k − 1. Hence also inequality (5.12) holds.

Now I prove Lemma 5A.

Proof of Lemma 5A. I show with the help of Lemma 3 and Lemma 7A that

\begin{aligned}P (sup_{f∈F} n^{−k/2} |Ī_{n,k}(f)| > An^{k/2}σ^{k+1}) & < 2P (sup_{f∈F} |S(f)| > \frac{A}{2}n^{k}σ^{k+1}) \\ & + 2^{k}n^{k−1}e^{−A^{1/(2k−1)}nσ^{2}/k} \end{aligned}  (5.17)

with the function S(f) defined in (5.10). To prove relation (5.17) introduce the random

variables Z(f) = (−1)^{k}Ī_{n,k}^{{1,...,k}}(f) and Z̄(f) = ∑_{V ⊂{1,...,k}, V ≠{1,...,k}}(−1)^{|V |+1}Ī_{n,k}^{V}(f) for

all f ∈ F, the σ-algebra B considered in Lemma 7A and the set

B = ⋂_{\begin{matrix}V ⊂\{1,...,k\} \\ V ≠\{1,...,k\} \end{matrix}} \{ω: sup_{f∈F} E (Ī_{n,k}^{V}(f)^{2}| B) (ω) ≤ 2^{−(3k+3)}A^{2}n^{2k}σ^{2k+2}\} .

Observe that S(f) = Z(f) − Z̄(f), f ∈ F, B ∈ B, and by Lemma 7A the inequality 1 − P (B) ≤ 2^{k}n^{k−1}e^{−A^{1/(2k−1)}nσ^{2}/k} holds. Hence to prove relation (5.17) as a consequence of Lemma 3 it is enough to show that

P (|Z̄(f)| > \frac{A}{2}n^{k}σ^{k+1}| B) (ω) ≤ \frac{1}{2} for all f ∈ F if ω ∈ B.  (5.18)

But P (|Ī_{n,k}^{V}(f)| > 2^{−(k+1)}An^{k}σ^{k+1}|F) (ω) ≤ 2^{−(k+1)} for all f ∈ F, V ⊂ {1, …, k}, V ≠ {1, …, k} if ω ∈ B by the ‘conditional Chebishev inequality’, hence relation (5.18) holds.

Lemma 5A follows from relation (5.17), part a) of Lemma 6 and the observation that the random vectors {Ī_{n,k}^{(V,ε)}(f), f ∈ F}, defined in (5.9′) have the same distribution for all V ⊂ {1, …, k} as the random vector {Ī_{n,k}^{ε}(f), f ∈ F}, considered in the formulation of Lemma 5A. Hence

P (sup_{f∈F} |S(f)| > \frac{A}{2}n^{k}σ^{k+1}) ≤ 2^{k}P (sup_{f∈F} |Ī_{n,k}^{ε}(f)| > 2^{−(k+1)}An^{k}σ^{k+1}) .

In the proof of Lemma 5B I apply the following Lemma 7B which is a version of Lemma 7A.

Lemma 7B. Let us consider a class of functions F satisfying the conditions of Proposition 5 and the random variables Ī_{n,k}^{V}(f, y), f ∈ F, V ⊂ {1, …, k}, defined in for-

mula (5.3). Let B = B(ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)}; 1 ≤ s ≤ k) denote the σ-algebra generated by the random variables ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)}, 1 ≤ s ≤ k, taking part in the definition of the random variables Ī_{n,k}^{V}(f, y) and H_{n,k}^{V}(f).

a) For all V ⊂ {1, …, k}, V ≠ {1, …, k}, there exists a number A_{0} = A_{0}(k) > 0 such that the inequality

P (sup_{f∈F} E(H_{n,k}^{V}(f)|B) > 2^{−(4k+4)}A^{(2k−1)/k}n^{2k}σ^{2k+2}) < n^{k−1}e^{−A^{1/2k}nσ^{2}/k} (5.19)

holds for all A ≥ A_{0}.

b) Given two subsets V_{1}, V_{2} ⊂ {1, …, k} of the set {1, …, k} define the random integrals

H_{n,k}^{(V_{1},V_{2})}(f) = ∫ |Ī_{n,k}^{V_{1}}(f, y)Ī_{n,k}^{V_{2}}(f, y)|ρ( dy), f ∈ F,

with the help of the functions Ī_{n,k}^{V}(f, y) defined in (5.3). If at least one of the sets V_{1} and V_{2} is not the set {1, …, k}, then there exists some number A_{0} = A_{0}(k) > 0 such that if the integrals H_{n,k}(f), f ∈ F, determined by this class of functions F have a good tail behaviour at level T^{(2k+1)/2k} for some T ≥ A_{0}, then the inequality

P (sup_{f∈F} E(H_{n,k}^{(V_{1},V_{2})}(f)|B) > 2^{−(2k+2)}A^{2}n^{2k}σ^{2k+2}) < 2n^{k−1}e^{−A^{1/2k}nσ^{2}/k} (5.20)

holds for all A ≥ T.

Proof of Lemma 7B. The proof of part a) of Lemma 7B is similar to that of Lemma 7A, only the formulas applied in it become a little bit more complicated. Hence I omit it. (The difference between the power of the parameter A at the right-hand side of formulas (5.19) and (5.12) appear, since the left-hand side of (5.19) contains the term A^{(2k−1)/2k} and not A^{2}.) Part b) will be proved with the help of Part a) and the inequality

sup_{f∈F} E(H_{n,k}^{(V_{1},V_{2})}(f)|B) ≤ (sup_{f∈F} E(H_{n,k}^{V_{1}}(f)|B))^{1/2} (sup_{f∈F} E(H_{n,k}^{V_{2}}(f)|B))^{1/2}

which follows from the Schwarz inequality applied for integrals with respect to conditional distributions. Let us assume that V_{1} ≠ {1, …, k}. Then the last inequality implies that

P (sup_{f∈F} E(H_{n,k}^{(V_{1},V_{2})}(f)|B) > 2^{−(2k+2)}A^{2}n^{2k}σ^{2k+2})

≤ P (sup_{f∈F} E(H_{n,k}^{V_{1}}(f)|B) > 2^{−(4k+4)}A^{(2k−1)/k}n^{2k}σ^{2k+2})

+ P (sup_{f∈F} E(H_{n,k}^{V_{2}}(f)|B) > A^{(2k+1)/k}n^{2k}σ^{2k+2}) .

Hence the estimate (5.19) for V = V_{1} together with the inequality

P (sup_{f∈F} E(H_{n,k}^{V_{2}}(f)|B) > A^{(2k+1)/k}n^{2k}σ^{2k+2}) ≤ n^{k−1}e^{−A^{1/2k}nσ^{2}/k}

which follows from Part a) if V_{2} ≠ {1, …, n} (in this case the level A^{(2k+1)/k}n^{2k}σ^{2k+2} can be replaced by 2^{−(4k+4)}A^{(2k−1)/k}n^{2k}σ^{2k+2} in the probability we consider) and from the conditions of Part b) if V_{2} = {1, …, k} imply relation (5.20).

Now I prove Lemma 5B.

Proof of Lemma 5B. By Part b) of Lemma 6 it is enough to prove that relation (5.6) holds if the random variables W̄ (f) are replaced in it by the random variables W (f) defined in formula (5.11). We shall prove this by applying Lemma 3 with the choice of Z(f) = H_{n,k}^{(V̄ ,V̄)}(f), V̄ = {1, …, k}, Z̄(f) = W (f) − Z(f), f ∈ F, B = B(ξ_{1,s}^{(1)}, …, ξ_{n,s}^{(1)}; 1 ≤ s ≤ k), and the set

B = ⋂_{\begin{matrix}(V_{1},V_{2}):V_{j}⊂\{1,...,k\}, j=1,2 \\ V_{1}≠\{1,...,k\} or V_{2}≠\{1,...,k\} \end{matrix}} \{ω: sup_{f∈F} E(H_{n,k}^{(V_{1},V_{2})}(f)|B)(ω) ≤ 2^{−(2k+2)}A^{2}n^{2k}σ^{2k+2}\} .

By Lemma 7B 1 − P (B)) ≤ 2^{2k+1}n^{k−1}e^{−A^{1/2k}nσ^{2}/k}, and to prove Lemma 5B with the help of Lemma 3 it is enough to show that

P (|Z̄(f)| > \frac{A^{2}}{2} n^{2k}σ^{2(k+1)}| B) (ω) ≤ \frac{1}{2} for all f ∈ F if ω ∈ B.

To prove this relation observe that

E(|Z̄(f)||B) ≤ ∑_{\begin{matrix}(V_{1},V_{2}):V_{j}⊂\{1,...,k\}, j=1,2 \\ V_{1}≠\{1,...,k\} or V_{2}≠\{1,...,k\} \end{matrix}} E(H_{n,k}^{(V_{1},V_{2})}(f)|B) ≤ \frac{A^{2}}{4} n^{2k}σ^{2k+2} if ω ∈ B

for all f ∈ F. Hence the ‘conditional Markov inequality’ implies that

P (|Z̄(f)| > \frac{A^{2}}{2} n^{2k}σ^{2k+2}| B) ≤ \frac{1}{2} if ω ∈ B and f ∈ F.

Lemma 5B is proved.

6. The proof of Propositions 4 and 5

The proof of Propositions 4 and 5 for general k ≥ 1 with the help of the symmetrization lemmas 5A and 5B is similar to the proof of Proposition 4 in the case k = 1 presented in Section 4. The proof applies an induction procedure with respect to the parameter k. In the proof of Proposition 4 for parameter k we may assume that Propositions 4 and 5 hold for k′ < k. In the proof of Proposition 5 we may also assume that Proposition 4 holds for the parameter k.

In the proof of Proposition 4 let us introduce (with the notation of this proposition) the functions

S_{n,k}^{2}(f)(x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) = \frac{1}{k!} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f^{2} (x_{j_{1},1}, …, x_{j_{k},k}) , f ∈ F,

(6.1)

where x_{j,s} ∈ X, 1 ≤ j ≤ n, 1 ≤ s ≤ k. Fix some number A > T, and define the set H

\begin{aligned}H = H(A) & = \{(x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k), \\ & sup_{f∈F} S_{n,k}^{2}(f)(x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) > 2^{k}A^{4/3}n^{k}σ^{2}\}. \end{aligned}  (6.2)

We want to show that

P ({ω: (ξ_{j,s}(ω), 1 ≤ j ≤ n, 1 ≤ s ≤ k) ∈ H}) ≤ 2^{k}e^{−A^{2/3k}nσ^{2}} if A ≥ T.  (6.3)

Relation (6.3) will be proved by means of the Hoeffding decomposition of the Ustatistics with kernel functions f^{2}(x_{1}, …, x_{k}), f ∈ F, and by the estimation of the sum this decomposition yields. More explicitly, write

f^{2}(x_{1}, …, x_{k}) = ∑_{V ⊂{1,...,k}} f_{V} (x_{s}, s ∈ V)  (6.4)

with

f_{V} (x_{s}, s ∈ V) = ∏_{s∉V} P_{μ,s} ∏_{s∈V} Q_{μ,s}f^{2}(x_{1}, …, x_{k}),  (6.5)

where P_{μ,s} and Q_{μ,s} are the operators P_{μ} and Q_{μ} defined in formulas (2.7) and (2.8) if (Y_{1} × Z × Y_{2}, Y_{1} × Z × Y_{2}) is the k-fold product (X^{k}, X^{k}) of the measurable space (X, X) in these definitions, Y_{1} is the product of the first s − 1 components, Z is the s-th component and Y_{2} is the product of the last k − s components in this product space.

(Relation (6.4) follows from the identity f^{2} = ∏_{s=1}^{k}(P_{μ,s} + Q_{μ,s})f^{2} if the multiplications

are carried out in this formula. In the calculation we exploit that the operators P_{μ,s} and P_{μ,s′} are commutative if s ≠ s′, and the same relation holds for the pairs P_{μ,s} and Q_{μ,s′} or Q_{μ,s} and P_{μ,s′} or Q_{μ,s} and Q_{μ,s′}.)

The identity S_{n,k}^{2}(f)(ξ_{j,r} 1 ≤ j ≤ n, 1 ≤ r ≤ k) = k!I_{n,k}(f^{2}) holds for all f ∈ F, and by writing the (Hoeffding type) decomposition (6.4) for each term f^{2}(ξ_{j_{1},1} …, ξ_{j_{k},k}) in the expression I_{n,k}(f^{2}) we get that

\begin{matrix}P (sup_{f∈F} S_{n,k}^{2}(f)(ξ_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) > 2^{k}A^{4/3}n^{k}σ^{2}) \\ ≤ ∑_{V ⊂\{1,...,k\}} P (sup_{f∈F} n^{k−|V |}|Ī_{n,|V |}(f_{V})| > A^{4/3}n^{k}σ^{2}) \end{matrix}  (6.6)

with the functions f_{V} defined in (6.5). We want to give a good estimate for all terms in the sum at the right-hand side in (6.6). For this goal we show that the classes of functions F_{V} = {f_{V}: f ∈ F} satisfy the conditions of Proposition 4 for all V ⊂ {1, …, k}.

The functions f_{V} are canonical for all V ⊂ {1, …, k}. (This follows from the commutativity relations between the operators P_{μ,j} and Q_{μ,j} mentioned before, the identity P_{μ,j}Q_{μ,j} = 0 and the fact that the canonical property of the function can be expressed in the form P_{μ,j}f_{V} = 0 for all j ∈ V.) We have |f^{2}(x_{1}, …, x_{k})| ≤ 2^{−2(k+1)}. The norm of Q_{μ,j} as a map from the L_{∞} space to L_{∞} space is less than 2, the norm

of P_{μ,j} is less than 1, hence | sup_{x_{j}∈X,j∈V} f_{V} (x_{j}, j ∈ V)| ≤ 2^{−(k+2)} ≤ 2^{−(k+1)} for all V ⊂

{1, …, k}. We have ∫ f^{4}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ 2^{−(k+1)}σ^{2}, hence ∫ f_{V}^{2} (x_{j}, j ∈ V) ∏_{j∈V} μ( dx_{j}) ≤ 2^{−(k+1)}σ^{2} ≤ σ^{2} for all V ⊂ {1, …, k} by Lemma 1. Finally, to check

that the class of functions F_{V} = {f_{V}: f ∈ F} is L_{2}-dense with exponent L and parameter D observe that for all probability measures ρ on (X^{k}, X^{k}) and pairs of functions f, g ∈ F ∫ (f^{2}−g^{2})^{2} dρ ≤ 2^{−2k} ∫ (f −g)^{2} dρ. This implies that if {f_{1}, …, f_{m}}, m ≤ Dε^{−L}, is an εdense subset of F in the space L_{2}(X^{k}, X^{k}, ρ), then the set of functions {2^{k}f_{1}^{2}, …, 2^{k}f_{m}^{2}} is an ε-dense subset of the class of functions F′ = {2^{k}f^{2}: f ∈ F} in the same space. Then by Lemma 1 and formula (6.5) the set of functions {(f_{1})_{V} , …, (f_{m})_{V}) is an ε-dense subset of the class of functions F_{V} in the space L_{2}(X^{k}, X^{k}, ρ) for all V ⊂ {1, …, k}. This means that F_{V} is also L_{2}-dense with exponent L and parameter D.

For V = ∅ the relation f_{V} = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2} holds, and I_{|V |}(f_{|V |})| = f_{V} ≤ σ^{2}. Therefore the term corresponding to V = ∅ in the sum at the right-hand side of (6.6) equals zero if A_{0} ≥ 1 in the conditions of Proposition 4. The terms corresponding to sets V, 1 ≤ |V | ≤ k, in these sums satisfy the inequality

P (sup_{f∈F} |Ī_{n,|V |}(f_{V})| > A^{4/3}n^{|V |}σ^{2})

≤ P (sup_{f∈F} |Ī_{n,|V |}(f_{V})| > A^{4/3}n^{|V |}σ^{|V |+1}) ≤ e^{−A^{2/3k}nσ^{2}} if 1 ≤ |V | ≤ k.

This inequality follows from the inductive hypothesis if |V | < k, and in the case V = {1, …, k} from the inequality A ≥ T and the assumption that U-statistics determined by a class of functions satisfying the conditions of Proposition 4 have a good tail behaviour at level T^{4/3}. The last relation together with formula (6.6) imply relation (6.3).

By conditioning the probability P (|Ī_{n,k}^{ε}(f)| > 2^{−(k+2)}An^{k/2}σ^{k+1}) with respect to the random variables ξ_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k, we get with the help of Lemma 2 that

P (|Ī_{n,k}^{ε}(f)| > 2^{−(k+2)}An^{k}σ^{k+1}| ξ_{j,s}(ω) = x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k)

≤ C exp \{−B (\frac{A^{2}n^{2k}σ^{2(k+1)}}{2^{2k+4}S_{n,k}^{2}(x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k)})^{1/k}\}  (6.7)

≤ Ce^{−2^{−3−4/k}BA^{2/3k}nσ^{2}} for all f ∈ F if {x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k} ∉ H.

Given some points x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k, define the probability measures ρ_{s}, 1 ≤ s ≤ k, uniformly distributed on the set x_{j,s}, 1 ≤ j ≤ s, i.e. ρ_{s}(x_{j,s}) = \frac{1}{n}, 1 ≤ j ≤ n, and their product ρ = ρ_{1} × ⋯ × ρ_{k}. If f is a function on (X^{k}, X^{k}) such that ∫ f^{2} dρ ≤ δ^{2} with some δ > 0, then |f(x_{j,s})| ≤ δn^{k/2} for all 1 ≤ s ≤ k, 1 ≤ j ≤ n, and P (|Ī_{n,k}^{ε}(f)| > δn^{3k/2}| ξ_{j,s} = x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) = 0. Choose the numbers

δ̄ = An^{−k/2}2^{−(k+2)}σ^{k+1} and δ = 2^{−(k+2)}n^{−k−1/2} ≤ δ̄. (The inequality δ ≤ δ̄ holds, since A ≥ A_{0} ≥ 1, and σ ≥ n^{−1/2}.) Choose a δ-dense set {f_{1}, …, f_{m}} in the L_{2}(X^{k}, X^{k}, ρ) space with m ≤ Dδ^{−L} ≤ 2^{(k+2)L}n^{β+(k+1/2)L} elements. Then formula (6.7) implies that

P (sup_{f∈F} |Ī_{n,k}^{ε}(f)| > 2^{−(k+1)}An^{k}σ^{k+1}| ξ_{j,s}(ω) = x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k)

≤ ∑_{j=1}^{m} P (|Ī_{n,k}^{ε}(f_{j})| > 2^{−(k+2)}An^{k}σ^{k+1}| ξ_{j,s}(ω) = x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) (6.8)

≤ C2^{(k+2)L}n^{β+(k+1/2)L}e^{−2^{−3−4/k}BA^{2/3k}nσ^{2}} if {x_{j,s}, 1 ≤ j ≤ n, 1 ≤ s ≤ k} ∉ H.

Relations (6.3) and (6.8) imply that

\begin{matrix}P (sup_{f∈F} |Ī_{n,k}^{ε}(f)| > 2^{−(k+1)}An^{k}σ^{k+1}) \\ ≤ C2^{(k+2)L}n^{β+(k+1/2)L}e^{−2^{−3−4/k}BA^{2/3k}nσ^{2}} + 2^{k}e^{−A^{2/3k}nσ^{2}} if A ≥ T. \end{matrix} (6.9)

Proposition 4 follows from the estimates (5.2) and (6.9) if the constants A_{0} and K in the condition nσ^{2} ≥ K(L + β) log n are chosen sufficiently large. In this case the upper bound these estimates yield for the probability at the left-hand side of (3.11) is smaller than e^{−A^{2/k}nσ^{2}}.

Let us turn to the proof of Proposition 5. By formula (5.8) it is enough to show that

P (sup_{f∈F} |H_{n,k}(f|G, V_{1}, V_{2})| > \frac{A^{2}}{2^{4k+1}k!}n^{2k}σ^{2(k+1)}) ≤ e^{−A^{1/2k}nσ^{2}}

for all G ∈ G and V_{1}, V_{2} ∈ {1, …, k} if A ≥ A_{0}

(6.10) with the random variables H_{n,k}(f|G, V_{1}, V_{2}) defined in formula (5.7). Let us first prove (6.10) in the case when |e(G)| = k, i.e. if all vertices of the diagram G are an end-point of some edge, and the expression H_{n,k}(f|G, V_{1}, V_{2}) contains no ‘symmetryzing term’ ε_{j}. By the Schwarz inequality

\begin{aligned}|H_{n,k}(f|G, V_{1}, V_{2})| & ≤ (  ∑_{\begin{matrix}j_{1},...,j_{k},1≤j_{s}≤n, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ∫ f^{2}(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)ρ( dy))^{1/2} \\ & (  ∑_{\begin{matrix}j_{1},...,j_{k},1≤j_{s}≤n, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ∫ f^{2}(ξ_{j_{1},1}^{(δ̄_{1})}, …, ξ_{j_{k},k}^{(δ̄_{k})}, y)ρ( dy))^{1/2} , \end{aligned} (6.11)

for such diagrams G, where δ_{s} = 1 if s ∈ V_{1}, δ_{s} = −1 if s ∉ V_{1}, and δ̄_{s} = 1 if s ∈ V_{2}, δ̄_{s} = −1 if s ∉ V_{2}. Hence

\{ω: sup_{f∈F} |H_{n,k}(f|G, V_{1}, V_{2})(ω)| > \frac{A^{2}}{2^{4k+1}k!}n^{2k}σ^{2(k+1)}\}

⊂ \{ω: sup_{f∈F} ∑_{\begin{matrix}j_{1},...,j_{k},1≤j_{s}≤n, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ∫ f^{2}(ξ_{j_{1},1}^{(δ_{1})}(ω), …, ξ_{j_{k},k}^{(δ_{k})}(ω), y)ρ( dy) > \frac{A^{2}n^{2k}σ^{2(k+1)}}{2^{4k+1}k!} \}

∪ \{ω: sup_{f∈F} ∑_{\begin{matrix}j_{1},...,j_{k},1≤j_{s}≤n, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ∫ f^{2}(ξ_{j_{1},1}^{(δ̄_{1})}(ω), …, ξ_{j_{k},k}^{(δ̄_{k})}(ω), y)ρ( dy) > \frac{A^{2}n^{2k}σ^{2(k+1)}}{2^{4k+1}k!} \} .

The last relation implies that

P (sup_{f∈F} |H_{n,k}(f|G, V_{1}, V_{2})| > \frac{A^{2}}{2^{4k+1}k!}n^{2k}σ^{2(k+1)})

≤ 2P (sup_{f∈F} ∑_{\begin{matrix}j_{1},...,j_{k},1≤j_{s}≤n, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} h_{f}(ξ_{j_{1},1}, …, ξ_{j_{k},k}) > \frac{A^{2}n^{2k}σ^{2(k+1)}}{2^{4k+1}k!} ) (6.12)

with the function h_{f}(x_{1}, …, x_{k}) = ∫ f^{2}(x_{1}, …, x_{k}, y)ρ( dy), f ∈ F. (In this upper bound we could get rid of the terms δ_{j} and δ̄_{j}, i.e. on the dependence of the expression H_{n,k}(f|G, V_{1}, V_{2}) on the sets V_{1} and V_{2}, since the probability of the events in the previous formula do not depend on these terms.)

I claim that

P (sup_{f∈F} |Ī_{n,k}(h_{f})| ≥ An^{k}σ^{2}) ≤ 2^{k}e^{−A^{1/2k}nσ^{2}} for A ≥ A_{0}  (6.13)

if the constant A_{0} and K are chosen sufficiently large in Proposition 5. Relation (6.13) together with the relation \frac{n^{2k}σ^{2(k+1)}}{2^{4k+1}k!} ≥ n^{k}σ^{2} imply that the probability at the right-hand side of (6.12) can be bounded by 2^{k+1}e^{−A^{1/k}nσ^{2}}, and the estimate (6.10) holds in the case |e(G)| = k. Relation (6.13) can be proved similarly to formula (6.3) in the proof of Proposition 4. It is not difficult to check that 0 ≤ ∫ h_{f}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2}, sup |h_{f}(x_{1}, …, x_{k})| ≤ 2^{−2(k+1)}, and the class of functions H = {2^{k}h_{f}, f ∈ F} is an L_{2}-dense class with exponent L and parameter D. This means that by applying the (Hoeffding type) decomposition of the functions h_{f}, f ∈ F, similarly to formula (6.4) we get such sets of functions (h_{f})_{V}, f ∈ F for all V ⊂ {1, …, k} which satisfy the conditions of Proposition 4. Hence a natural adaptation of the estimate given for the expression at the right-hand side of (6.6) yields the proof of formula (6.13). Let us observe that by our inductive hypothesis the result of Proposition 4 holds also for k, and this allows us to carry out the estimates we need also for the class of functions (h_{f})_{V}, f ∈ F, with V = {1, …, k} if A ≥ A_{0}.

In the case e(G) < k formula (6.10) will be proved with the help of Lemma 2. To carry out this proof first an appropriate expression will be introduced and bounded for all sets V_{1}, V_{2} ⊂ {1, …, k} and diagrams G ∈ G such that |e(G)| < k. To define the expression we shall bound first some notations will be introduced.

Let us consider the set J_{0}(G) = J_{0}(G, k, n),

J_{0}(G) = {(j_{1}, …, j_{k}, j′_{1}, …, j′_{k}): 1 ≤ j_{s}, j′_{s} ≤ n, 1 ≤ s ≤ k, j_{s} ≠ j_{s′} if s ≠ s′,
j′_{s} ≠ j′_{s′} if s ≠ s′, j_{s} = j′_{s′} if (s, s′) ∈ G, j_{s} ≠ j′_{s′} if (s, s′) ∉ G},

the set of those sequences (j_{1}, …, j_{k}, j′_{1}, …, j′_{k}) which appear as indices in the summation in formula (5.7). I introduce a partition of J_{0}(G) appropriate for our purposes.

To do this first I define the sets M_{1} = M_{1}(G) = {s(1), …, s(k − |e(G)|)} = {1, …, k} \ v_{1}(G), s(1) < ⋯ < s(k − |e(G)|), and M_{2} = M_{2}(G) = {s̄(1), …, s̄(k − |e(G|)} = {1, …, k} \ v_{2}(G), s̄(1) < ⋯ < s̄(k − |e(G|), the sets of those vertices of the first and second row of the diagram G in increasing order from which no edges start. Let us also introduce the set V (G) = V (G, n, k),

V (G) = {(j_{s(1)}, …, j_{s(k−|e(G)|)}, j′_{s̄(1)}, …, j′_{s̄(k−|e(G)|)}): 1 ≤ j_{s(p)}, j′_{s̄(p)} ≤ n,

1 ≤ p ≤ k − |e(G)|, j_{s(p)} ≠ j_{s(p′)}, j′_{s̄(p)} ≠ j′_{s̄(p′)} if p ≠ p′, 1 ≤ p, p′ ≤ k − |e(G)|

j_{s(p)} ≠ j′_{s̄(p′)}, 1 ≤ p, p′ ≤ k − |e(G)|},

which is the set consisting from the restriction of the coordinates of the vectors

(j_{1}, …, , j_{k}, j′_{1}, …, j′_{k}) ∈ J_{0}(G)

to M_{1} ∪ M_{2}. Given a vector v ∈ V (G) let v(r), 1 ≤ r ≤ k − |e(G)|, and v̄(r), 1 ≤ r ≤ k −|e(G)|, denote its coordinates corresponding to the set M_{1} and M_{2} respectively. Put

E_{G}(v) = {(j_{1}, …, j_{k}, j′_{1}, …, j′_{k}): 1 ≤ j_{s} ≤ n, 1 ≤ j′_{s′} ≤ n, 1 ≤ s, s′ ≤ k,

j_{s} ≠ j_{s′} if s ≠ s′, j′ ; s̄ ≠ j′_{s̄′} if s̄ ≠ s̄′,

j_{s} = j′_{s′} if (s, s′) ∈ e(G) and j_{s} ≠ j′_{s′} if (s, s′) ∉ e(G)

j_{s(r)} = v(r), j′_{s̄(r)} = v̄(r), 1 ≤ r ≤ k − |e(G)|}, v ∈ V (G),

where {s(1), …, s(k − |e(G)|)} = M_{1}, {s̄(1), …, s̄(k − |e(G)|)} = M_{2} in the last line of this definition. The set E_{G}(v) contains those vectors in J_{0}(G) whose coordinates in M_{1} ∪ M_{2} are prescribed by the vector v ∈ V (G), the remaining coordinates can be put into pairs (s, s′) such that (s, s′) ∈ e(G), and the values j_{s} = j′_{s′}, (s, s′) ∈ e(G), must be different for different pairs, otherwise they can be chosen freely from the set {1, …, n} \ {v(1), …, v(k − |e(G)|), v̄(1), …, v̄(k − |e(G)|)}.

Now we define the partition

J_{0}(G) = ⋃_{v∈V (G)} E_{G}(v)

of the set J_{0}(G).

The inequality

P (S(F|G, V_{1}, V_{2})) > A^{8/3}n^{2k}σ^{4}) ≤ 2^{k+1}e^{−A^{2/3k}nσ^{2}} if A ≥ A_{0} and e(G) < k (6.14)

will be proved for the random variable

S(F|G, V_{1}, V_{2}) = sup_{f∈F} ∑_{v∈V (G)}( ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈E_{G}(v)} ∫ f(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)

f(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y)ρ( dy))^{2},

where δ_{s} = 1 if s ∈ V_{1}, δ_{s} = −1 if s ∉ V_{1}, and δ̄_{s} = 1 if s ∈ V_{2}, δ̄_{s} = −1 if s ∉ V_{2}.

To prove formula (6.14) let us first fix some v ∈ V (G) and apply the Schwarz inequality. It yields that

(  ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈E_{G}(v)} ∫ f(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)f(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y)ρ( dy))^{2}

≤ ( ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈E_{G}(v)} ∫ f^{2}(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)ρ( dy))

( ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈E_{G}(v)} ∫ f^{2}(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y)ρ( dy)) .

for all v ∈ V (G). Summing up these inequalities for all v ∈ V (G) we get that

S(F|G, V_{1}, V_{2}) ≤ sup_{f∈F} ∑_{v∈V (G)} (  ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈E_{G}(v)} ∫ f^{2}(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)ρ( dy))

( ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈E_{G}(v)} ∫ f^{2}(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y)ρ( dy))

≤ sup_{f∈F} ( ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈J_{0}(G)} ∫ f^{2}(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)ρ( dy))

sup_{f∈F} (  ∑_{(j_{1},...,j_{k},j′_{1},...,j′_{k})∈J_{0}(G)} ∫ f^{2}(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y)ρ( dy))

(6.15)

To check formula (6.15) we have to observe that by multiplying the inner sum at the lefthand side of this inequality each term f^{2}(ξ_{j_{1},1}^{(δ_{1})}, …, ξ_{j_{k},k}^{(δ_{k})}, y)f^{2}(ξ_{j′_{1},1}^{(δ̄_{1})}, …, ξ_{j′_{k},k}^{(δ̄_{k})}, y) appears only once. (In particular, it is determined which index v ∈ V (G) has to be taken in the outer sum to get this term. The coordinates of this vector v agree with the coordinates of the vector j = (j_{1}, …, j_{k}, j′_{1}, …, j′_{k}) in M_{1} ∪ M_{2}, with the coordinates of the vector j which correspond to those vertices from which no edges of the diagram G start.) Beside this, all these products appear if the multiplications at the right-hand side expression are carried out.

Relation (6.15) implies that

P (S(F|G, V_{1}, V_{2}) > A^{8/3}n^{2k}σ^{4}) ≤ 2P (sup_{f∈F} Ī_{n,k}(h_{f}) > A^{4/3}n^{k}σ^{2})

with h_{f}(x_{1}, …, x_{k}) = ∫ f^{2}(x_{1}, …, x_{k}, y)ρ( dy). (Here we exploited that in the last formula S(F|G, V_{1}, V_{2}) is bounded by the product of two random variables whose distributions do not depend on the sets V_{1} and V_{2}.) Thus to prove inequality (6.14) it is enough to show that

2P (sup_{f∈F} Ī_{n,k}(h_{f}) > A^{4/3}n^{k}σ^{2}) ≤ 2^{k+1}e^{−A^{2/3k}} if A ≥ A_{0}.  (6.16)

Actually formula (6.16) has been already proved, only formula (6.13) has to be applied, and the parameter A has to be replaced by A^{4/3} in it.

The proof of Proposition 5 can be completed similarly to Proposition 4. It follows from Lemma 2 that

P (|H_{n,k}(f|G, V_{1}, V_{2})| > \frac{A^{2}}{2^{4k+2}k!}n^{2k}σ^{2(k+1)}| ξ_{j,s}^{±1}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) (ω)

≤ Ce^{−B2^{−(4+2/k)}(k!)^{−1/k}A^{2/3k}nσ^{2}} if S(F|G, V_{1}, V_{2})(ω) ≤ A^{8/3}n^{2k}σ^{4}

for all f ∈ F, G ∈ G, |e(G)| < k, and V_{1}, V_{2} ∈ {1, …, k} if A ≥ A_{0}.

(6.17)

Indeed, in this case the conditional probability considered in (6.17) can be bounded by

C exp \{−B (\frac{A^{4}n^{4k}σ^{4(k+1)}}{2^{8k+4}(k!)^{2}S(F|G,V_{1},V_{2})})^{1/2j}\} ≤ C exp \{−B (\frac{A^{4/3}n^{2k}σ^{4k}}{2^{8k+4}(k!)^{2}} )^{1/2j}\}, where 2j =

2k − 2|e(G)|, the number of vertices of the diagram G from which no edges start. Since j ≤ k, nσ^{2} ≥ 1, and also \frac{A^{4/3}}{2^{8k+4}(k!)^{2}} ≥ 1 if A_{0} is chosen sufficiently large the above calculation implies relation (6.17).

Let us show that also the inequality

P ( sup_{f∈F} |H_{n,k}(f|G, V_{1}, V_{2})| > \frac{A^{2}}{2^{4k+1}k!}n^{2k}σ^{2(k+1)}| ξ_{j,s}^{±1}, 1 ≤ j ≤ n, 1 ≤ s ≤ k) (ω)

≤ Cn^{(3k+1)L/2+β}e^{−BA^{2/3k}nσ^{2}/2^{(4+2/k)}(k!)^{1/k}} if S(F|G, V_{1}, V_{2}))(ω) ≤ A^{8/3}n^{2k}σ^{4}

for all G ∈ G, |e(G)| < 1, and V_{1}, V_{2} ∈ {1, …, k} if A ≥ A_{0}

(6.18)

holds.

To prove formula (6.18) let us fix an elementary event ω ∈ Ω which satisfies the relation S(F|G, V_{1}, V_{2}))(ω) ≤ A^{8/3}n^{2k}σ^{4}, two sets V_{1}, V_{2} ⊂ {1, …, k}, a diagram G, consider the points x_{j,s}^{(±1)} = x_{j,s}^{(±1)}(ω) = ξ_{j,s}^{(±1)}(ω), 1 ≤ j ≤ n, 1 ≤ s ≤ k, and introduce with their help the following probability measures: For all 1 ≤ s ≤ k define the probability measures ν_{s}^{(1)} which are uniformly distributed on the points x_{j,s}^{(δ_{s})}, 1 ≤ j ≤ n, and ν_{s}^{(2)}

which are uniformly distributed on the points x_{j,s}^{(δ̄_{s})}, 1 ≤ j ≤ n, where δ_{s} = 1 if s ∈ V_{1}, δ_{s} = −1 if s ∉ V_{1}, and similarly δ̄_{s} = 1 if s ∈ V_{2} and δ̄_{s} = −1 if s ∉ V_{2}. Let us consider the product measures α_{1} = ν_{1}^{(1)} × ⋯ × ν_{k}^{(1)} × ρ, α_{2} = ν_{1}^{(2)} × ⋯ × ν_{k}^{(2)} × ρ on the product space (X^{k} × Y, X^{k} × Y), where ρ is that probability measure on (Y, Y) which appears in Proposition 5, together with the measure α = \frac{α_{1}+α_{2}}{2} . Given two functions f ∈ F and g ∈ F we give an upper bound for |H_{n,k}(f|G, V_{1}, V_{2})(ω) − H_{n,k}(g|G, V_{1}, V_{2})(ω)| if ∫ (f − g)^{2} dα ≤ δ with some δ > 0. (This bound does not depend on the ‘randomizing terms’ ε_{j}(ω) in the definition of the random variable H_{n,k}(·|G, V_{1}, V_{2}).)

In this case ∫ (f − g)^{2} dα_{j} ≤ 2δ^{2}, and

∫ |f(x_{1,j_{1}}^{(δ_{1})}, …, x_{k,j_{k}}^{(δ_{k})}, y) − g(x_{1,j_{1}}^{(δ_{1})}, …, x_{k,j_{k}}^{(δ_{k})}, y)|^{2} ρ( dy) ≤ 2δ^{2}n^{k},
∫ |f(x_{1,j_{1}}^{(δ_{1})}, …, x_{k,j_{k}}^{(δ_{k})}, y) − g(x_{1,j_{1}}^{(δ_{1})}, …, x_{k,j_{k}}^{(δ_{k})}, y)| ρ( dy) ≤ \sqrt{2}δn^{k/2}

for all 1 ≤ s ≤ k, and 1 ≤ j_{s} ≤ n, and the same result holds if all δ_{s} is replaced by δ̄_{s}, 1 ≤ s ≤ k. Since |f| ≤ 1 for f ∈ F, the condition ∫ (f − g)^{2} dα ≤ δ^{2} implies that

∫ |f(ξ_{j_{1},1}^{(δ_{1})}(ω), …, ξ_{j_{k},k}^{(δ_{k})}(ω), y)f(ξ_{j′_{1},1}^{(δ̄_{1})}(ω), …, ξ_{j′_{k},k}^{(δ̄_{k})}(ω), y))

− g(ξ_{j_{1},1}^{(δ_{1})}(ω), …, ξ_{j_{k},k}^{(δ_{k})}(ω), y)g(ξ_{j′_{1},1}^{(δ̄_{1})}(ω), …, ξ_{j′_{k},k}^{(δ̄_{k})}(ω), y)|ρ( dy) ≤ 2\sqrt{2}δn^{k/2}

for all vectors (j_{1}, …, j_{k}, j′_{1}, …, j′_{k}) which appear as an index in the summation in (5.7), and

|H_{n,k}(f|G, V_{1}, V_{2})(ω) − H_{n,k}(g|G, V_{1}, V_{2})(ω)| ≤ 2\sqrt{2}δn^{5k/2}

if the originally fixed ω ∈ Ω is considered.

Put δ̄ = \frac{A^{2}n^{−k/2}σ^{2(k+1)}}{2^{(4k+7/2)}k!} , and δ = n^{−(3k+1)/2} ≤ δ̄ (since σ ≥ \frac{1}{\sqrt{n}} and we may assume that A ≥ A_{0} is sufficiently large), choose a δ-dense subset {f_{1}, …, f_{m}} in the L_{2}(X^{k} × Y, X^{k} × Y, α) space with m ≤ Dδ^{−L} ≤ n^{(3k+1)L/2+β} elements. Relation (6.17) for these functions together with the above estimates yield formula (6.18).

It follows from relations (6.14) and (6.18) that

P (sup_{f∈F} |H_{n,k}(f|G, V_{1}, V_{2})| > \frac{A^{2}}{2^{4k+1}k!}n^{2k}σ^{2(k+1)}) ≤ 2^{k+1}e^{−A^{2/3k}nσ^{2}}

+ Cn^{(3k+1)L/2+β}e^{−BA^{2/3k}nσ^{2}/2^{(4+2/k)}(k!)^{1/k}} if A ≥ A_{0}

for all V_{1}, V_{2} ⊂ {1, …, k} also in the case |e(G)| ≤ k − 1. This means that relation (6.10) holds also in this case if the constants A_{0} and K are chosen sufficiently large in Proposition 5. Proposition 5 is proved.

Appendix. The proof of Proposition 3

I shall explain the proof of Proposition 3 in a concise form. A more detailed explanation can be found in [8].

The proof of Proposition 3. Let us first introduce the (random) probability measures δ_{ξ_{j}}, 1 ≤ j ≤ n, concentrated in the sample points ξ_{j}. We can write μ_{n} − μ =

\frac{1}{n} ( ∑_{j=1}^{n} (δ_{ξ_{j}} − μ)), and formula (1.2) can be rewritten as

\begin{aligned}J_{n,k}(f) = \frac{1}{n^{k/2}k!} & ∑_{\begin{matrix}(j_{1},...,j_{k}) \\ 1≤j_{s}≤n for all 1≤s≤k \end{matrix}} ∫ ′ f(x_{1}, …, x_{k}) \\ & (δ_{ξ_{j_{1}}} ( dx_{1}) − μ( dx_{1})) … (δ_{ξ_{j_{k}}} ( dx_{k}) − μ( dx_{k})) . \end{aligned}  (A1)

To rearrange the above sum in a way more appropriate for us let us introduce the following notations: Let P = P_{k} denote the set of all partitions of the set {1, 2, …, k}, and given a sequence (j_{1}, …, j_{k}), 1 ≤ j_{s} ≤ n, 1 ≤ s ≤ k, of length k let H(j_{1}, …, j_{k}) denote that partition of P_{k} in which two points s and t, 1 ≤ s, t ≤ k, belong the same element of the partition if and only if j_{s} = j_{t}. Given a set A, let |A| denote its cardinality.

Let us rewrite the expression (A1) for J_{n,k}(f) in the form

J_{n,k}(f) = \frac{1}{n^{k/2}k!} ∑_{P ∈P} ∑_{\begin{matrix}(j_{1},...,j_{k}), \\ 1≤j_{s}≤n, 1≤s≤k \\ H(j_{1},...,j_{k})=P \end{matrix}} ∫ ′ f(x_{1}, …, x_{k})  (A2)

(δ_{ξ_{j_{1}}} ( dx_{1}) − μ( dx_{1})) … (δ_{ξ_{j_{k}}} ( dx_{k}) − μ( dx_{k})) .

Let us remember that the diagonals x_{s} = x_{t}, s ≠ t, were omitted from the domain of integration in the formula defining J_{n,k}(f). This implies that in the case j_{s} = j_{t} the measure δ_{ξ_{js}} ( dx_{s})δ_{ξ_{j_{t}}} ( dx_{t}) has zero measure in the domain of integration. We have to understand the cancellation effects caused by this relation. I want to show that because of these cancellations the expression in formula (A2) can be rewritten as a linear combination of the degenerate U-statistics I_{n,|V |}(f_{V}) defined in (2.11) with not too large coefficients. This seems to be a natural approach, but the detailed proof demands some rather unpleasant calculations.

Let us fix some P ∈ P and investigate the inner sum at the right-hand side of (A2) corresponding to this partition P. For the sake of simplicity let us first consider such an inner sum that corresponds to a partition P ∈ P which contains a set of the form {1, …, s} with some s ≥ 2. The products of measures corresponding to the terms in the sum determined by such a partition contain a part of length s which has the form (δ_{ξ_{j}}(dx_{1}) − μ(dx_{1})) … (δ_{ξ_{j}}(dx_{s}) − μ(dx_{s})) with some 1 ≤ j ≤ n. This part of the product can be rewritten in the domain of integration as

∑_{l=1}^{s}(−1)^{s−1}μ( dx_{1}) … μ( dx_{l−1})(δ_{ξ_{j}}( dx_{l}) − μ( dx_{l}))μ( dx_{l+1}) … μ( dx_{s})
+ (−1)^{s−1}(s − 1)μ(dx_{1}) … μ(dx_{s}).

Here we have exploited that all other terms of this product disappear in the domain of integration. Let us also observe that the term (−1)^{s−1}(s − 1)μ( dx_{1}) … μ( dx_{l}) appears n-times as we sum up for 1 ≤ j ≤ n. Similar calculation can be made for all partitions P ∈ P and all sets contained in the partitions, only the notation of the indices will be more complicated.

Let us fix a general partition P = {R_{1}, …, R_{u}} ∈ P, and let us rewrite the inner sum in formula (A2) in a more appropriate form. We can get the proof of Proposition 3 by means of summing up the identities we get in such a way for all P ∈ P. To get the desired formula fix some vector (j_{1}, …, j_{k}) such that H(j_{1}, …, j_{k}) = P, and let us rewrite the multiple integral in the inner sum of (A2) corresponding to this index.

We can get by working out the above mentioned calculation in the general case that for a vector (j_{1}, …, j_{k}) such that H(j_{1}, …, j_{k}) = P the relation

\begin{matrix}∫ ′ f(x_{1}, …, x_{k}) (δ_{ξ_{j_{1}}} ( dx_{1}) − μ( dx_{1})) … (δ_{ξ_{j_{k}}} ( dx_{k}) − μ( dx_{k})) \\ = ∑_{V ∈T (P)} α(V, P) ∫ f(x_{1}, …, x_{k}) ∏_{s∈V} (δ_{ξ_{js}} ( dx_{s}) − μ( dx_{s})) ∏_{s′∈\{1,...,k\}\V} μ( dx_{s′}) \end{matrix}

(A3)

holds with some appropriate constants α(V, P), where the class T (P) which consists of subsets of {1, …, k} and depends on the partition P = {R_{1}, …, R_{u}} is defined in the following way. For all elements R_{t}, 1 ≤ t ≤ u, of the partition P a set V ∈ T (P) contains zero or 1 elements of the set R_{t}. If R_{t} = {b_{t}} consists of one elements, then the set V contains this point b_{t}. T (P) consists of all subsets of {1, …, k} which satisfy the two above properties.

The coefficients α(V, P) at the right-hand side of (A3) could be calculated explicitly, but we do not have to do this. It is enough to know that it depends only on the partition P and the set V ∈ T (P). Let us also observe that at the right-hand side of (A3) the prime is missing in the integral, i.e. here integration is taken on the whole space X^{k}, the diagonals are not taken out from the domain of integration. Indeed, it can be seen that because of the non-atomic property of the measure μ we do not change the value of the integrals at the right-hand side of (A3) by inserting the diagonals to the domain of integration.

Formula (A3) can be rewritten in the following way.

∫ ′ f(x_{1}, …, x_{k}) (δ_{ξ_{j_{1}}} ( dx_{1}) − μ( dx_{1})) … (δ_{ξ_{j_{k}}} ( dx_{k}) − μ( dx_{k}))

= ∑_{V ∈T (P)} α(V, P) (( ∏_{s′∈{1,...,k}\V} P_{μ,s′} ∏_{s∈V} Q_{μ,s})) f(ξ_{j_{s}}, s ∈ V). (A4)

Here Q_{μ,s} = I − P_{μ,s} is the operator Q_{μ} defined in (2.8) if Y_{1} is the product of the first s−1 components of the product space X^{k}, Z is its s-th component and Y_{2} is the product of the last k −s components. The operator P_{μ,s′} is the operator P_{μ} defined in (2.7) with the choice of Y_{1} as the first s′ − 1 components, Z as the s′-th component and Y_{2} as the product of the last k − s′ components of the space X^{k}. To see why formula (A4) holds we have to understand that integration with respect to (δ_{ξ_{js}} ( dx_{s}) − μ( dx_{s})) means the application of the operator Q_{μ,s} and then putting the value ξ_{j_{s}} in the argument x_{s}, while integration with respect to μ( dx_{s′}) means the application of the operator P_{μ,s′}. Beside this, the operators Q_{μ,s} and P_{μ,s′} are exchangeable.

By fixing some V ∈ T (P) and summing up the term corresponding to it at the right-hand side of formula (A4) for all (j_{1}, …, j_{k}) such that H(j_{1}, …, j_{k}) = P we get that

α(V, P) ∑_{\begin{matrix}(j_{1},...,j_{k}) \\ 1≤j_{s}≤n, 1≤s≤k \\ H(j_{1},...,j_{k})=P \end{matrix}} ( ∏_{s′∈\{1,...,k\}\V}P_{μ,s′} ∏_{s∈V} Q_{μ,s}) f(ξ_{j_{s}}, s ∈ V) = ᾱ(V, P, k, n)I_{n,|V |}(f_{V})

(A5)

where I_{n,|V |}(f_{V}) is the U-statistic of order |V | with the kernel function

f_{V} (x_{s}, s ∈ V) = ( ∏_{s′∈{1,...,k}\V} P_{μ,s′} ∏_{s∈V} Q_{μ,s}) f(x_{1}, …, x_{k}),  (A6)

and the coefficients ᾱ(V, P, k, n) at the right-hand side of (A5) are appropriate coefficients which could be calculated explicitly. But we do not need such a formula. It can be shown with some work that they satisfy the inequality |ᾱ(V, P, k, n)| ≤ D(k)n^{β(P,V)}, where β(P, V) = u − |V | is the number of those components R_{s}, 1 ≤ s ≤ u, of the partition P for which R_{s} ∩ V = ∅, and the constant D(k) < ∞ depends only on the multiplicity k of the integral J_{n,k}(f). Such an estimate is sufficient for us.

We get from relations (A2), (A4) and (A5) by summing up identity (A5) for all P ∈ P and V ∈ T (P) that

J_{n,k}(f) = ∑_{V ⊂{1,2,...,k}} C(n, k, V)n^{−|V |/2}I_{n,|V |}(f_{V})  (A7)

with some coefficients C(n, k, V). Moreover, a careful analysis shows that the above coefficients satisfy the inequality |C(n, k, V)| ≤ G(k) with some constant G(k) > 0. The explicit expression for the coefficients C(n, k, V) has a rather complicated form, but the above estimate about their magnitude is sufficient for our purposes. This estimate for C(k, n, V) is sharp, because for a fixed set V those partitions P ∈ P which contain the |V | one-point subsets of V and (k −|V |)/2 subsets of cardinality 2 of {1, …, k}\V yield a contribution of order n^{−k/2}n^{k/2−|V |/2} to the coefficient C(n, k, V)n^{−|V |/2}. A more careful analysis also shows that for a fixed set V ⊂ {1, …, k} the sequence C(n, k, V) has a finite limit as n → ∞. It is not difficult to see that C(n, k, {1, …, k}) = 1 for V = {1, …, k}.

The definition of the function f_{V} in formula (A6) agrees with the definition of f_{V} in formula (2.11). Hence formulas (A6), (A7) and the estimates on the coefficients C(n, k, V) in formula (A7) imply Proposition 3.

References:

1.) Alexander, K. (1987) The central limit theorem for empirical processes over Vapnik–

Červonenkis classes. Ann. Probab. 15, 178–203 2.) Arcones, M. A. and Giné, E. (1993) Limit theorems for U-processes. Ann. Probab.

21, 1494–1542 3.) Arcones, M. A. and Giné, E. (1994) U-processes indexed by Vapnik–Červonenkis

classes of functions with application to asymptotics and bootstrap of U-statistics with estimated parameters. Stoch. Proc. Appl. 52, 17–38

4.) Beckner, W. (1975) Inequalities in Fourier Analysis. Ann. Math. 102, 159–182 5.) de la Peña, V. H. and Giné, E. (1999) Decoupling From dependence to indepen-

dence. Springer series in statistics. Probability and its application. Springer Verlag, New York, Berlin, Heidelberg

6.) de la Peña, V. H. and Montgomery–Smith, S. (1995) Decoupling inequalities for

the tail-probabilities of multivariate U-statistics. Ann. Probab., 25, 806–816 7.) Giné, E. and Zinn, J. (1984) Some limit theorems for empirical processes. Ann.

Probab., 12, 929–989 8.) Major, P. (2004) On the tail behaviour of multiple random integrals and degenerate

U-statistics. (manuscript for a future Lecture Note) 9.) Major, P. (2005) A multivariate generalization of Hoeffding’s inequality. Submitted

to Ann. Probab. 10.) Major, P. and Rejtő, L. (1988) Strong embedding of the distribution function under

random censorship. Annals of Statistics, 16, 1113–1132 11.) Major, P. and Rejtő, L. (1998) A note on nonparametric estimations. In the con-

ference volume to the 65. birthday of Miklós Csörgő. 759–774 12.) Pollard, D. (1984) Convergence of Stochastic Processes. Springer–Verlag, New York

Supported by the OTKA foundation Nr. 037886