ON THE TAIL BEHAVIOUR OF MULTIPLE RANDOM INTEGRALS AND U-STATISTICS,

ON THE SUPREMUM OF CLASSES OF SUCH QUANTITIES,

AND SOME RELATED QUESTIONS. Péter Major

Alfréd Rényi Mathematical Institute of the Hungarian Academy of Sciences

Summary: This paper contains sharp estimates about the distribution of multiple random integrals of functions of several variables with respect to a normalized empirical measure, about the distribution of U-statistics and multiple Wiener–Itô integrals with respect to a white noise. It also contains good estimates about the supremum of appropriate classes of such integrals or Ustatistics. The proof of most results is omitted, I have concentrated on explaining their content together with the picture behind them. I also tried to explain the reason for the investigation of such questions. My goal was to present such an explanation which also a non-expert can understand, and not only on a formal level.

1. Formulation of the main problems discussed in this paper

To formulate the main problems discussed in this paper first I introduce some notations. Let us have a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} on a measurable space (X, X) with distribution μ, and introduce their empirical distribution

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

Given a measurable function f(x_{1}, …, x_{k}) on the product space (X^{k}, X^{k}) let us consider the integral of this function with respect to the k-fold direct product of the normalized version \sqrt{n}(μ_{n} − μ) of the empirical measure μ_{n}, i.e. take the integral

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 am interested in the following two problems:

Problem a). Let us give a good estimate on the probabilities P (J_{n,k}(f) > u) under some appropriate not too restrictive conditions on the function f.

It seems to be natural to omit the diagonals x_{j} = x_{l}, j ≠ l, from the domain of integration in the definition of the random integrals J_{n,k}(f) given in (1.2). In the applications I met the estimation of such a version of the integrals was needed.

I shall also discuss the following more general problem.

Problem b). Let us have a nice class of functions f ∈ F on the space (X^{k}, X^{k}). Let

us give a good estimate on the probabilities P (sup_{f∈F} J_{n,k}(f) > u), where J_{n,k}(f)

denotes again the random integral of a function f defined in (1.2).

I met the problems formulated above when I tried to adapt the method of investigation about the limit behaviour of maximum likelihood estimates to more difficult problems, to so-called non-parametric maximum likelihood estimates. An important step in the investigation of maximum likelihood estimates consists of a good approximation of the maximum-likelihood function whose root we are looking for. We get such an approximation by means of a Taylor expansion of this function if we drop the higher order terms in this expansion. In an adaptation of this method to more complicated situations the solution of the above mentioned problems a) and b) appear in a natural way. They play a role similar to the estimation of the coefficients of the Taylor expansion in the study of maximum likelihood estimates. Here I do not discuss the details of this approach to non-parametric maximum-likelihood problems. The interested reader may find some further information about it in papers [15] and [16], where such a question is investigated in detail in a special case.

In the above mentioned papers the so-called Kaplan–Meyer method is investigated for the estimation of a distribution function by means of censored data. The solution of problem a) is needed to bound the error of the Kaplan–Meyer estimate for a single argument of the distribution function, and the solution of problem b) helps to bound the difference of this estimate and the real distribution function in the supremum norm. Let me remark that the approach in papers [15] and [16] seems to be applicable under much more general circumstances, but this requires the solution of some hard problems.

I do not know of other authors who dealt directly with the study of random integrals similar to that defined in (1.2). On the other hand, several authors investigated the behaviour of U-statistics, and discussed the next two problems. I shall describe them under the name problem a′) and problem b′). They are natural counterparts of problems a) and b).

To formulate them first I recall the notion of U-statistics.

If a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} is given on a measurable space (X, X) together with a function f(x_{1}, …, x_{k}) on the space (X^{k}, X^{k}), n ≥ k, then we call the expression

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.3)

a U-statistic of order k with kernel function f. Now I formulate the following two problems.

Problem a′). Let us give a good estimate on the probabilities P (n^{−k/2}I_{n,k}(f) > u) under some appropriate not too restrictive conditions on the function f.

Problem b′). Let us have a nice class of functions f ∈ F on the space (X^{k}, X^{k}).

Let us give a good estimate on the probabilities P (sup_{f∈F} n^{−k/2}I_{n,k}(f) > u), where

I_{n,k}(f) denotes again the U-statistic with kernel function f defined in (1.3).

Problems a) and b) are closely related to problems a′) and b′), but the detailed description of their relation demands some hard work. The main difference between these two pairs of problems is that integration with respect to a power of the measure μ_{n} − μ in formula (1.2) means some kind of normalization, while the definition of the U-statistics in (1.3) contains no normalization. Moreover, there is no simple way to introduce some good normalization in U-statistics. This has the consequence that in problems a) and b) we can get a good estimate for a much larger class of functions than in problems a′) and b′). Hence the original pair of problems seems to be more useful in several possible applications.

Both the integrals J_{n,k}(f) defined in (1.2) and the U-statistics I_{n,k}(f) defined in (1.3) are non-linear functionals of independent random variables. The main difficulty arises in the study of the above problems, because there is no general method for the study of such non-linear functionals. On the other hand, the normalized empirical measure \sqrt{n}(μ_{n} − μ) is close to a Gaussian field for a large sample size n. Moreover, as we shall see, U-statistics with a large sample size behave similarly to multiple Gaussian integrals. This suggests that the study of multiple Gaussian integrals may help a lot in the solution of our problems. To investigate them first I recall the definition of white noise that we shall need later.

Definition of a white noise with some reference measure. Let us have a σ-finite measure μ on a measurable space (X, X). We call a Gaussian field μ_{W}, i.e. a set of jointly Gaussian random variables μ_{W} (A) defined for all A ∈ X such that μ(A) < ∞ a white noise with reference measure μ if Eμ_{W} (A) = 0 for all A ∈ X such that μ(A) < ∞, and Eμ_{W} (A)μ_{W} (B) = μ(A ∩ B) for all A, B ∈ X such that μ(A) < ∞ and μ(B) < ∞.

Remark: In the definition of a white noise one also mentions the property μ_{W} (A ∪ B) = μ_{W} (A) + μ_{W} (B) with probability 1 if A ∩ B = ∅, and μ(A) < ∞, μ(B) < ∞. I omitted this property in the definition of the white noise, because it follows from its remaining properties. Indeed, simple calculation shows that E(μ_{W} (A∪B)−μ_{W} (A)−μ_{W} (B))^{2} = 0 if A ∩ B = ∅, hence μ_{W} (A ∪ B) − μ_{W} (A) − μ_{W} (B) = 0 with probability 1 in this case. We also can observe that if some sets A_{1}, …, A_{k} ∈ X, μ(A_{j}) < ∞, 1 ≤ j ≤ k, are disjoint, then the random variables μ_{W} (A_{j}), 1 ≤ j ≤ k, are independent because of the uncorrelatedness of these jointly Gaussian random variables.

It is not difficult to see that for an arbitrary reference measure μ on a space (X, X) a white noise μ_{W} with this reference measure really exists. This follows simply from Kolmogorov’s fundamental theorem, by which if we describe the finite dimensional distributions of a random field in a consistent way, then there exists a random field with these finite dimensional distributions.

Given a white noise μ_{W} with a σ-finite reference measure μ on some measurable space (X, X) together with a function f(x_{1}, …, x_{k}) on (X^{k}, X^{k}) such that

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

the multiple Wiener–Itô integral of the function f with respect to a white noise μ_{W} with reference measure μ can be defined, (see e.g. [7] or [9]). We shall denote it by

Z_{μ,k}(f) = ∫ f(x_{1}, …, x_{k})μ_{W} ( dx_{1}) … μ_{W} ( dx_{k}).  (1.5)

Here we shall not need a detailed discussion of Wiener–Itô integrals, it will be enough to recall the idea of their definition.

Let us have a measurable space (X, X) together with a non-atomic σ-finite measure μ on it. (We shall define Wiener–Itô integrals only with respect to a white noise μ_{W} with a non-atomic reference measure μ.) We call a function f on (X^{k}, X^{k}) elementary if there exists a finite partition A_{1}, …, A_{M}, 1 ≤ M < ∞, of the set X (i.e. A_{j} ∩ A_{j′} = ∅

if j ≠ j′ and ⋃_{j=1}^{M} A_{j} = X) such that μ(A_{j}) < ∞ for all 1 ≤ j ≤ M (with the possible

exception of the set A_{M}, but we demand in the next formula (1.6) that c(j_{1}, …, j_{k}) = 0 if one of the arguments j_{s}, 1 ≤ s ≤ k equals M, and μ(A_{M}) = ∞), and the function f satisfies the properties

f(x_{1}, …, x_{k}) = c(j_{1}, …, j_{k}) if x_{1} ∈ A_{j_{1}}, …, x_{k} ∈ A_{j_{k}}, 1 ≤ j_{s} ≤ M, 1 ≤ s ≤ k

and c(j_{1}, …, j_{k}) = 0 if j_{s} = j_{s′} for some 1 ≤ s < s′ ≤ k  (1.6)

with some real numbers c(j_{1}, …, j_{k}), 1 ≤ j_{s} ≤ M, 1 ≤ s ≤ k, i.e. the function f is constant on all k-dimensional rectangles A_{j_{1}} × ⋯ × A_{j_{k}}, and it equals zero on those rectangles which have two sides which agree.

We define the Wiener-Itô integral of the elementary function f(x_{1}, …, x_{k}) defined in formula (1.6) with respect to a white noise μ_{W} with the (non-atomic) reference measure μ by the formula

\begin{aligned}Z_{μ,k}(f) & = ∫ f(x_{1}, …, x_{k})μ_{W} ( dx_{1}) … μ_{W} ( dx_{k}) \\ & = ∑_{1≤j_{s}≤M, 1≤s≤k} c(j_{1}, …, j_{k})μ_{W} (A_{j_{1}}) ⋯ μ_{W} (A_{j_{k}}). \end{aligned}  (1.7)

Then the definition of Wiener–Itô integral can be extended to a general function satisfying relation (1.4) by means of an L_{2}-isomorphism. The details of this extension will be not discussed here.

Let me remark that the condition c(j_{1}, …, j_{k}) = 0 if j_{s} = j_{s′} for some 1 ≤ s < s′ ≤ k in the definition of an elementary functions can be interpreted so that, similarly to the definition of the random integral J_{n,k}(f) in (1.2), the diagonals are omitted from the domain of integration of a Wiener–Itô integral Z_{μ}(f).

The investigation of Wiener–Itô integrals is simpler than that of random integrals J_{n,k}(f) defined in (1.2) or of U-statistics introduced in (1.3) because of the Gaussian property of the underlying white noise. Beside this, the study of Wiener–Itô integrals may help us to understand what kind of estimates we can expect in the solution of problems a) and b) or a′) and b′), and this study also can help to find the proof of these estimates. Hence it is useful to consider the following two problems.

Problem a′′). Let us give a good estimate on the probabilities P (Z_{μ,k}(f) > u) under some appropriate not too restrictive conditions on the function f and measure μ.

Problem b′′). Let us have a nice class of functions f ∈ F on the space (X^{k}, X^{k}). Let

us give a good estimate on the probabilities P (sup_{f∈F} Z_{μ,k}(f) > u), where Z_{μ,k}(f)

denotes again a Wiener–Itô integral with function f and white noise with reference measure μ.

In this paper the above problems will be discussed. Such estimates will be presented for them which depend on some basic characteristics of the random expressions J_{n,k}(f), I_{n,k}(f) or Z_{μ,k}(f). They will depend mainly on the L_{2} and L_{∞}-norm of the function f taking part in the definition of the above quantities. (The L_{2}-norm of the function f is closely related to the variance of the random variables we consider.) The proof of the estimates we get is related to some other problems interesting in themselves. My main goal was to explain the results and ideas behind them. I put emphasis on the explanation of the picture that can help understanding them, and the details of almost all proofs are omitted. A detailed explanation together with the proofs can be found in my Lecture Note [14].

This paper consists of 9 sections. The first four sections contain the results about problems a), a′) and a′′) together with some other statements which may explain better their background. Section 5 contains the main ideas of their proof. In Section 6 problems b), b′) and b′′) are discussed together with some related questions. The main ideas of the proofs of the results in Section 6 which contain many unpleasant technical details are discussed in Sections 7 and 8. In Section 9 Talagrand’s theory about concentration inequalities is considered together with its relation to the problems investigated in this paper and some open questions.

2. The discussion of some large deviation results

Let us first restrict our attention to problems a), a′) and a′′), i.e. to the case when we estimate the distribution of the random integral or U-statistic of one function. These problems are much simpler in the special case k = 1. But they are not trivial even in this case. A discussion of some large deviation results may help us to understand them better. In this section I recall some large deviation results useful for us. I shall not try to formulate them in the most general form. First I recall a large deviation theorem about the sum of independent, identically distributed random variables. Actually we shall not need this result later, it is interesting for us for the sake of some orientation.

Theorem 2.1. Large deviation theorem about partial sums of independent and identically distributed random variables. Let ξ_{1}, ξ_{2}, …, be a sequence of independent and identically distributed random variables such that Eξ_{1} = 0, Ee^{tξ_{1}} < ∞

with some t > 0. Let us define the partial sums S_{n} = ∑_{j=1}^{n} ξ_{j}, n = 1, 2, . . .. Then the

relation

lim_{n→∞} \frac{1}{n} log P (S_{n} ≥ nu) = −ρ(u)  for all u > 0  (2.1)

holds with the function ρ(u) defined by the formula ρ(u) = sup_{t} (tu − log Ee^{tξ_{1}}). The

function ρ(·) in formula (2.1) has the following properties: ρ(u) > 0 for all u > 0, and it is a monotone increasing function, there is some number 0 < A ≤ ∞ with a number A depending on the distribution of the function ξ_{1} such that ρ(u) < ∞ for 0 ≤ u ≤ A, and the asymptotic relation ρ(u) = \frac{σ^{2}u^{2}}{2} + O(u^{3}) holds for small u > 0, where σ^{2} = Eξ_{1}^{2} is the variance of ξ_{1}.

The above theorem states that for all ε > 0 the inequality P (S_{n} > nu) ≤ e^{−n(ρ(u)−ε)} holds if n ≥ n(u, ε), and this estimate is essentially sharp. Actually, in nice cases, when the equation ρ(u) = sup_{t} (tu − log Ee^{tξ_{1}}) has a solution in t, the above inequality also

holds with ε = 0 for all n ≥ 1. The function ρ(u) in the exponent of the above large deviation estimate strongly depends on the distribution of ξ_{1}. It is the so-called Legendre transform of log Ee^{tξ_{1}}, of the logarithm of the moment generating function of ξ_{1}, and its values in an arbitrary interval determine the distribution of ξ_{1} completely. On the other hand, the estimate (2.1) for small u > 0 shows some resemblance to the bound suggested by the central limit theorem. Indeed, for small u > 0 it yields the upper bound e^{−nσ^{2}u^{2}/2+nO(u^{3})}, while the central limit theorem would suggest the estimate e^{−nσ^{2}u^{2}/2}. (Let us recall that the standard normal distribution function Φ(u) satisfies

the inequality (\frac{1}{u} − \frac{1}{u^{3}} ) \frac{e^{−u^{2}/2}}{\sqrt{2π}} < 1 − Φ(u) < \frac{1}{u} \frac{e^{−u^{2}/2}}{\sqrt{2π}} for all u > 0, hence for large u it

is natural to bound it by e^{−u^{2}/2}.)

The next result I mention, Bernstein’s inequality, (see e.g. [4], 1.3.2 Bernstein’s inequality) has a closer relation to the problems I am discussing in this paper. It gives a good upper bound on the distribution of sums of independent, bounded random variables with expectation zero. It is important that this estimate is universal, the constants it contains do not depend on the properties of the random variables we consider.

Theorem 2.2 (Bernstein’s inequality). Let X_{1}, …, X_{n} be independent random variables, P (|X_{j}| ≤ 1) = 1, EX_{j} = 0, 1 ≤ j ≤ n. Put σ_{j}^{2} = EX_{j}^{2}, 1 ≤ j ≤ n,

S_{n} = ∑_{j=1}^{n} X_{j} and V_{n}^{2} = Var S_{n} = ∑_{j=1}^{n} σ_{j}^{2}. Then

P (S_{n} > u) ≤ exp \{−\frac{u^{2}}{2V_{n}^{2} (1 + \frac{u}{3V_{n}^{2}} )}\} for all u > 0.  (2.2)

Let us take a closer look on the content of Theorem 2.2. Estimate (2.2) yields a bound of different form if the first term is dominating in the sum 1 + \frac{u}{3V_{n}^{2}} in the denominator of the fraction in this expression and if the second term is dominating in it. If we fix some constant C > 0, then formula (2.2) yields that P (S_{n} > u) ≤ e^{−Bu^{2}/2V_{n}^{2}} with some constant B = B(C) for 0 ≤ u ≤ CV_{n}^{2}. If, moreover 0 ≤ u ≤ εV_{n}^{2} with some small ε > 0, then the estimate P (S_{n} > u) ≤ e^{−(1−Kε)u^{2}/2V_{n}^{2}} holds with a universal constant K > 0. This means that in the case 0 < u ≤ CV_{n}^{2} the tail behaviour of the distribution of F (u) = P (S_{n} > u) can be bounded by the distribution G(u) = P (const. V_{n}η > u) where η is a standard normal random variable, and V_{n}^{2} is the variance of the partial sum S_{n}. If 0 ≤ u ≤ εV_{n}^{2} with a small ε > 0, then it also can be bounded by P ((1 − Kε))V_{n}η > u) with some universal constant K > 0.

In the case u ≫ V_{n}^{2} formula (2.2) yields a different type of estimate. In this case we get that P (S_{n} > u) < e^{−(3−ε)u/2} with a small ε > 0, and this seems to be a rather weak estimate. In particular, it does not depend on the variance V_{n}^{2} of S_{n}. In the degenerate case V_{n} = 0 when P (S_{n} > u) = 0, estimate (2.2) yields a strictly positive upper bound for P (S_{n} > u). One would like to get such an improvement of Bernstein’s inequality which gives a better bound in the case u ≫ V_{n}^{2}. Bennett’s inequality (see e.g. [18], Appendix B, 4 Bennett’s inequality) satisfies this requirement.

Theorem 2.3 (Bennett’s inequality). Let X_{1}, …, X_{n} be independent random vari-

ables, P (|X_{j}| ≤ 1) = 1, EX_{j} = 0, 1 ≤ j ≤ n. Put σ_{j}^{2} = EX_{j}^{2}, 1 ≤ j ≤ n, S_{n} = ∑_{j=1}^{n} X_{j}

and V_{n}^{2} = Var S_{n} = ∑_{j=1}^{n} σ_{j}^{2}. Then

P (S_{n} > u) ≤ exp \{−V_{n}^{2} [(1 + \frac{u}{V_{n}^{2}} ) log (1 + \frac{u}{V_{n}^{2}} ) − \frac{u}{V_{n}^{2}} ]\} for all u > 0. (2.3)

As a consequence, for all ε > 0 there exists some B = B(ε) > 0 such that

P (S_{n} > u) ≤ exp \{−(1 − ε)u log \frac{u}{V_{n}^{2}} \} if u > BV_{n}^{2},  (2.4)

and there exists some positive constant K > 0 such that

P (S_{n} > u) ≤ exp \{−Ku log \frac{u}{V_{n}^{2}} \} if u > 2V_{n}^{2}.  (2.5)

Estimates (2.4) or (2.5) yield a slight improvement of Bernstein’s inequality in the case u ≥ KV_{n}^{2} with a sufficiently large K > 0. On the other hand, even this estimate is much weaker than the estimate suggested by a formal application of the central limit theorem. The question arises whether these estimates are sharp, or they can be improved. The next example shows that inequalities (2.4) or (2.5) in Bennett’s inequality are essentially sharp. If we do not impose some additional restrictions, then at most the universal constants can be improved in them. We show that even a sum of independent, bounded and identically distributed random variables can be constructed which satisfies a lower bound similar to the upper bounds in formulas (2.4) and (2.5), only with possibly different constants.

Example 2.4. Let us fix some positive integer n, real numbers u and σ^{2} such that 0 < σ^{2} ≤ \frac{1}{8}, n > 3u ≥ 6 and u > 4nσ^{2}. Put V_{n}^{2} = nσ^{2} and take a sequence of independent, identically distributed random variables X_{1}, …, X_{n} such that P (X_{j} = 1) =

P (X_{j} = −1) = \frac{σ^{2}}{2} , and P (X_{j} = 0) = 1 − σ^{2}. Put S_{n} = ∑_{j=1}^{n} X_{j}. Then ES_{n} = 0,

Var S_{n} = V_{n}^{2}, and

P (S_{n} ≥ u) > exp \{−Bu log \frac{u}{V_{n}^{2}} \}

with some appropriate (universal) constant B > 0.

Remark: Here I formulate a statement which we shall not need later. But it can help to understand better the content of Bennett’s inequality and Example 2.4. The estimate of Example 2.4 or of relations (2.4) and (2.5) is well comparable with the tail distribution of a Poisson distributed random variable with parameter λ = const. nσ^{2} ≥ 1 at level u ≥ 2λ. Some calculation shows that a Poisson distributed random variable ζ_{λ} with parameter λ > 1 satisfies the inequality e^{−C_{1}u log(u/λ)} ≤ P (ζ_{λ}−Eζ_{λ} > u) ≤ P (ζ_{λ} > u) ≤ P (ζ_{λ} − Eζ_{λ} > \frac{u}{2}) ≤ e^{−C_{2}u log(u/λ)} with some appropriate constants 0 < C_{1} < C_{2} < ∞ for all u > 2λ, and Eζ_{λ} = Var ζ_{λ} = λ. This estimate is similar to the above mentioned relations.

I have proved the statement of Example 2.4 in Example 3.2 of my Lecture Note [14] by applying some (simple) ideas in the large deviation theory. Here I briefly explain another proof (with another universal constants) which may explain better the picture behind this example.

Proof of the statement of Example 2.4. Let us fix an integer u such that n > 3u and u > 4nσ^{2}. Let B = B(u) denote the event that among the random variables X_{j}, 1 ≤ j ≤ n, there are exactly 3u terms with values +1 or −1, and all other random variables X_{j} equal zero. Let us also define the event A = A(u) ⊂ B(u) which holds if 2u random variables X_{j} are equal to 1, u random variables X_{j} are equal to −1, and all remaining random variables X_{j}, 1 ≤ j ≤ n, are equal to zero. Clearly, P (S_{n} ≥ u) ≥ P (A) = P (B)P (A|B). On the other hand, P (B) = \binom{n}{3u} (σ^{2})^{3u} (1 − σ^{2})^{n−3u} ≥ (\frac{n}{3u})^{3u} (σ^{2})^{3u} e^{−4nσ^{2}} = e^{−3u log(3u/nσ^{2})−4nσ^{2}}. Here we exploited that because of the condition σ^{2} ≤ \frac{1}{8} we have 1 − σ^{2} ≥ e^{−4σ^{2}}. Beside this, u ≥ 4nσ^{2}, and P (B) ≥ e^{−3u log(3u/nσ^{2})−u} ≥ e^{−B_{1}u log(u/nσ^{2})} with some appropriate B_{1} > 0 under our assumptions.

Let us consider a set of 3u elements, and choose a random subset of it by taking all elements of this set with probability 1/2 to this random subset independently of each other. I claim that the conditional probability P (A|B) equals the probability that this random subset has 2u elements. Indeed, even the conditional probability of the event A under the condition that for a prescribed set of indices J ⊂ {1, …, n} with exactly 3u elements we have X_{j} = ±1 if j ∈ J and X_{j} = 0 if j ∉ J equals the probability of the event that the above defined random subset has 2u elements. This is so, because under this condition the random variables X_{j} take the value +1 with probability 1/2 for all j ∈ J independently of each other. Hence P (A|B) = \binom{3u}{2u}2^{−3u} ≥ e^{−Cu} ≥ e^{−B_{2}u log(u/nσ^{2})} with some appropriate constants C > 0 and B_{2} > 0 under our conditions, since \frac{u}{nσ^{2}} ≥ 4 in this case. The estimates given for P (B) and P (A|B) imply the statement of Example 2.4.

Bernstein’s inequality provides a solution of problems a) and a′) in the case k = 1 under some conditions. Because of the normalization (multiplication by n^{−1/2} in these problems) we get our estimates with the choice ū = \sqrt{n}u in Bernstein’s inequality.

Observe that J_{n,1}(f) = \frac{1}{\sqrt{n}} ∑_{j=1}^{n}(f(ξ_{j}) − Ef(ξ_{j})) for k = 1 in the definition (1.2). In

problem a) Bernstein’s inequality gives a good bound on P (J_{n,1}(f) > u) for a function f such that |f(x)| ≤ \frac{1}{2} for all x ∈ X with the choice X_{j} = f(ξ_{j}) − Ef(ξ_{j}), 1 ≤ j ≤ n, and ū = \sqrt{n}u. In problem a′) it gives a good bound on P (n^{−1/2}I_{n,1}(f) > u) under the condition |f(x)| ≤ 1 for all x ∈ X, and Ef(ξ_{1}) = 0 with the choice X_{j} = f(ξ_{j}), 1 ≤ j ≤ n, and ū = \sqrt{n}u. We get that in the case 0 ≤ u ≤ C\sqrt{n}σ^{2} the bounds P (J_{n,1}(f) > u) ≤ e^{−Ku^{2}/2σ^{2}} and P (n^{−1/2}I_{n,1}(f) > u) ≤ e^{−Ku^{2}/2σ^{2}} hold with σ^{2} = Var f(ξ_{1}) and some constant K = K(C) depending on the number C if the above conditions hold in the case of problem a) or a′). If 0 ≤ u ≤ ε\sqrt{n}σ^{2} with some small ε > 0, then the above constant K can be chosen very close to the number 1.

The above results can be interpreted so that in the case 0 ≤ u ≤ const. \sqrt{n}σ^{2} and a bounded function f we can get an estimate suggested by the central limit theorem for problem a), only an additional constant multiplier may appear in the exponent. A similar statement holds in the case of problem a′), only here the additional condition Ef(ξ_{j}) = 0 has to be imposed. On the other hand, the situation is quite different if u ≫ \sqrt{n}σ^{2}. In this case Bernstein’s inequality yields only a very weak estimate. Bennett’s inequality gives a slight improvement. It yields the inequality P (J_{n,1}(f) > u) ≤ e^{−Bu\sqrt{n} log(u/\sqrt{n}σ^{2})} with an appropriate constant B > 0 if |f(x)| ≤ \frac{1}{2} for all x ∈ X, u ≥ 2\sqrt{n}σ^{2}, and σ^{2} = Var f(ξ_{1}). We have the estimate P (n^{−1/2}I_{n,1}(f) > u) ≤ e^{−Bu\sqrt{n} log(u/\sqrt{n}σ^{2})} with an appropriate B > 0 if |f(x)| ≤ 1 for all x ∈ X, Ef(ξ_{1}) = 0, Var f(ξ_{1}) = σ^{2}, and u ≥ 2\sqrt{n}σ^{2}. The above estimates are much weaker than the bound suggested by a formal application of the central limit theorem. On the other hand, Example 2.4 shows that we cannot expect a better estimate in this case. Moreover, its proof gives some insight why we get a different type of estimate in the cases u ≤ \sqrt{n}σ^{2} and u ≫ \sqrt{n}σ^{2} for problems a) and a′).

In the proof of Example 2.4 we have defined a ‘bad’ irregular event A such that if it holds, then the sum of the random variables we consider is sufficiently large. Generally, the probability of such an event is very small, but if the variance of the random variables is very small, (in problems a) and a′) this is the case if σ^{2} ≪ un^{−1/2}) then we can define such a ‘bad’ irregular event whose probability is not negligible.

We shall consider problems a) and a′) also for k ≥ 2, and this will be called the multivariate case. The results we get for the solution of problems a) and a′) in the multivariate case is very similar to the results described above. To understand them first we have to discuss some problems. In particular, the answer for the following two questions has to be understood:

Question a). In the solution of problem a′) in the case k = 1 we have imposed the condition Ef(ξ_{1}) = 0, which means some sort of normalization. What kind of condition corresponds to it in the multivariate case? This question leads to the definition of degenerate U-statistics and to the so-called Hoeffding’s decomposition of U-statistics to a sum of degenerate U-statistics.

Question b). In the discussion of problems a) and a′) we have referred to the central limit theorem. What kind of limit theorems can take its place in the multivariate case? What kind of limit theorems do we have for U-statistics I_{n,k}(f) or multiple random integrals J_{n,k}(f) defined in (1.2)? The limit we get in these problems can be expressed by means of multiple Wiener–Itô integrals in a natural way.

In the next section the two above questions will be discussed.

3. On some problems about U-statistics and random integrals

A. The normalization of U-statistics.

In the case k = 1 problem a′) meant the estimation of sums of independent and identically distributed random variables. We got good estimates under the condition Ef(ξ_{1}) = 0.

In the multivariate case k ≥ 2 we need a stronger normalization property to get good estimates about the distribution of U-statistics. In this case we have to assume that the conditional expectations of the terms f(ξ_{j_{1}}, …, ξ_{j_{k}}) of the U-statistic under the condition that the value of all but one arguments takes a prescribed value equals zero. This property is formulated in a more explicit way in the following definition of degenerate U-statistics.

Definition of degenerate U-statistics. Let us consider the U-statistic I_{n,k}(f) of order k defined in formula (1.3) with kernel function f(x_{1}, …, x_{k}) and a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n}. It is a degenerate U-statistic if its kernel function satisfies the relation

Ef(ξ_{1}, …, ξ_{k}|ξ_{1} = x_{1}, …, ξ_{j−1} = x_{j−1}, ξ_{j+1} = x_{j+1}, …, ξ_{k} = x_{k}) = 0

for all 1 ≤ j ≤ k and x_{s} ∈ X, s ∈ {1, …, k} \ {j}. (3.1)

The definition of degenerate U-statistics is closely related to the notion of canonical functions described below.

Definition of canonical functions. A function f(x_{1}, …, x_{k}) taking values on the k-fold product (X^{k}, X^{k}) of a measurable space (X, X) is called canonical with respect to a probability measure μ on (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 ∈ {1, …, k} \ {j}.

(3.2)

It is clear that a U-statistic I_{n,k}(f) is degenerate if and only if its kernel function f is canonical with respect to the distribution μ of the random variables ξ_{1}, …, ξ_{n} appearing in the definition of the U-statistic.

Given a function f and a probability measure μ, this function can be written as a sum of canonical functions (with different sets of arguments) with respect to the measure μ, and this enables us to decompose a U-statistic as a linear combination of degenerate U-statistics. This is the content of Hoeffding’s decomposition of U-statistics described below. To formulate it first I introduce some notations.

Let us consider the k-fold product (X^{k}, X^{k}, μ^{k}) of a measure space (X, X , μ) with some probability measure μ, and define for all integrable functions f(x_{1}, …, x_{k}) and indices 1 ≤ j ≤ k the projection P_{j}f of the function f to its j-th coordinate as

P_{j}f(x_{1}, …, x_{j−1}, x_{j+1}, …, x_{k}) = ∫ f(x_{1}, …, x_{k})μ( dx_{j}), 1 ≤ j ≤ k.  (3.3)

Let us also define the operators Q_{j} = I − P_{j} as Q_{j}f = f − P_{j}f on the space of integrable functions on (X^{k}, X^{k}, μ^{k}), 1 ≤ j ≤ k. In the definition (3.3) P_{j}f is a function not depending on the coordinate x_{j}, but in the definition of Q_{j} we introduce the fictive coordinate x_{j} to make the expression Q_{j}f = f − P_{j}f meaningful. Now we can formulate the following result.

Theorem 3.1 (Hoeffding’s decomposition of U-statistics). Let f(x_{1}, …, x_{k}) be an integrable function on the k-fold product space (X^{k}, X^{k}, μ^{k}) of a space (X, X , μ) with a probability measure μ. It has the decomposition

f = ∑_{V ⊂{1,...,k}} f_{V} , with f_{V} (x_{j}, j ∈ V) = ( ∏_{j∈{1,...,k}\V} P_{j} ∏_{j∈V} Q_{j}) f(x_{1}, …, x_{k})

(3.4)

such that all functions f_{V}, V ⊂ {1, …, k}, in (3.4) are canonical with respect to the probability measure μ, and they depend on the |V | arguments x_{j}, j ∈ V.

Let ξ_{1}, …, ξ_{n} be a sequence of independent, μ distributed random variables, and consider the U-statistics I_{n,k}(f) and I_{n,|V |}(f_{V}) corresponding to the kernel functions f, f_{V} defined in (3.4) and random variables ξ_{1}, …, ξ_{n}. Then

I_{n,k}(f) = ∑_{V ⊂\{1,...,k\}}(n − |V |)(n − |V | − 1) ⋯ (n − k + 1)\frac{|V |!}{k!}I_{n,|V |}(f_{V})  (3.5)

is a representation of I_{n,k}(f) as a sum of degenerate U-statistics, where |V | denotes the cardinality of the set V. (The product (n−|V |)(n−|V |−1) ⋯ (n−k+1) is defined as 1 if V = {1, …, k}, i.e. |V | = k.) This representation is called the Hoeffding decomposition of I_{n,k}(f).

Remark: Hoeffding’s decomposition of U-statistics for sums of degenerate U-statistics can be slightly simplified by exploiting that I_{n,|V |}(f_{V}) = I_{n,|V |}(Sym f_{V}), and

I_{n,|V |}(f_{V} (x_{j_{1}}, …, x_{j_{|V |}})) = I_{n,|V |}(f_{V} (x_{1}, …, x_{|V |}),

i.e. the arguments x_{j_{1}}, …, x_{j_{|V |}} of the function f_{V} (if V = {j_{1}, …, j_{|V |}}) can be replaced by x_{1}, …, x_{|V |} in the U-statistic I_{n,|V |}(f_{V}). In such a way the contribution of all terms I_{n,|V |}(f_{V}) with |V | = l, with some 0 ≤ l ≤ k, can be unified into one degenerate Ustatistic of order l with a symmetric kernel function. Generally this simplified version is called the Hoeffding’s decomposition in the literature. Nevertheless, some arguments can be better carried out by means of the formula presented in Theorem 3.1.

I omit the proof of Theorem 3.1, although it is fairly simple. (See e.g. the Appendix of [5].) I only try to briefly explain that the construction of Hoeffding’s decomposition is natural. Let us recall that if we want to decompose a random variable as a sum of a random variable with expectation zero plus a constant, then we get the random variable with expectation zero in this decomposition by taking out from the original random variable its expectation. If we want to introduce such a transformation which turns to zero not only the expectation of the transformed random variable, but also its conditional expectation with respect to some condition, then it is natural to take out from the original random variable its conditional expectation. Since the operators P_{j} defined in (3.3) are closely related to the conditional expectations appearing in the definition of degenerate U-statistics, the above consideration makes natural to write the

identity f = ∏_{j=1}^{k}(P_{j} + Q_{j})f = ∑_{V ⊂{1,...,k}} f_{V} with the functions defined in (3.4). (In the

justification of the last formula we have to exploit some properties of the operators P_{j} and Q_{j}.)

It is clear that EI_{n,k}(f) = 0 for a degenerate U-statistic. Also the inequality

E (I_{n,k}(f))^{2} ≤ \frac{n^{k}}{k!} σ^{2} with σ^{2} = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k})  (3.6)

holds if I_{n,k}(f) is a degenerate U-statistic. The measure μ appearing in (3.6) is the distribution of the random variables ξ_{j} taking part in the definition of the U-statistic. Moreover, lim_{n→∞} n^{−k}E (I_{n,k}(f))^{2} = \frac{σ^{2}}{k!} if the kernel function f is a symmetric function of its arguments, i.e. f(x_{1}, …, x_{k}) = f(x_{π(1)}, …, x_{π(k)}) for all permutations π = (π(1), …, π(k)) of the set {1, …, k}.

Relation (3.6) can be proved by means of the observation that

Ef(ξ_{j_{1}}, …, ξ_{j_{k}})f(ξ_{j′_{1}}, …, ξ_{j′_{k}}) = 0

if {j_{1}, …, j_{k}} ≠ {j′_{1}, …, j′_{k}}, and f is a canonical function with respect to the distribution μ of the random variables ξ_{j}. On the other hand,

|Ef(ξ_{j_{1}}, …, ξ_{j_{k}})f(ξ_{j′_{1}}, …, ξ_{j′_{k}})| ≤ ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k})

by the Schwarz inequality if {j_{1}, …, j_{k}} = {j′_{1}, …, j′_{k}}, i.e. if the sequence of indices j′_{1} …, j′_{k} is a permutation of the sequence of indices j_{1}, …, j_{k}, and there is an identity in this relation if the function f is symmetric. The last formula enables us to check the asymptotic relation given for E (I_{n,k}(f))^{2} after relation (3.6).

Relation (3.6) suggests to restrict our attention in the investigation of problem a′) to the case of degenerate U-statistics, and it explains why we chose the normalization n^{−k/2} in it. In this case we can expect an upper bound not depending on the sample size n. The estimation of the distribution of a general U-statistic can be reduced to the degenerate case by means of Hoeffding’s decomposition (Theorem 3.1).

The random integrals J_{n,k}(f) are defined in (1.2) by means of integration with respect to the signed measure μ_{n} − μ, and this means some sort of normalization. As a consequence, we can expect a good estimate on their distribution for a rather general kernel function f. Beside this, a random integral J_{n,k}(f) can be written as a sum of U-statistics for which the Hoeffding decomposition can be applied. Hence it can be rewritten as a linear combination of degenerate U-statistics. In the next result I present the representation of the random integral J_{n,k}(f) we get in such a way. It shows that the implicit normalization caused by integration with respect to μ_{n} − μ has a serious cancellation effect. This enables us to get a good solution for problem a) or b) if we have a good solution for problem a′) or b′). Unfortunately, the proof of this result demands rather unpleasant calculations. Hence here I omit this proof. It can be found in [11] or in Theorem 9.4 of [14].

Theorem 3.2. 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}),  (3.7)

holds with the canonical (with respect to the measure μ) functions f_{V} (x_{j}, j ∈ V) defined in (3.4) 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.3). The constants C(n, k, V) in (3.7) 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}.

Let us also remark that the functions f_{V} defined in (3.4) satisfy the inequalities

∫ f_{V}^{2} (x_{j}, j ∈ V) ∏_{j∈V} μ( dx_{j}) ≤ ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k})  (3.8)

and

sup_{x_{j}, j∈V} |f_{V} (x_{j}, j ∈ V)| ≤ 2^{|V |} sup_{x_{j}, 1≤j≤k} |f(x_{1}, …, x_{k})|  (3.9)

for all V ⊂ {1, …, k}.

The decomposition of the random integral J_{n,k}(f) in formula (3.7) is similar to the Hoeffding decomposition of general U-statistics presented in Theorem 3.1. The main difference between these two formulas is that the coefficients of the normalized degenerate U-statistics n^{−|V |/2}I_{n,|V |}(f_{V}) at the right-hand side of formula (3.7) can be bounded by a universal constant depending neither on the sample size n, nor on the kernel function f of the random integral. This fact has important consequences.

Theorem 3.2 enables us to get good estimates for problem a) if we have such estimates for problem a′). In particular, formulas (3.6), (3.7) and (3.8) enable us to give good bounds on the expectation and variance of the random integral J_{n,k}(f). We have

E (J_{n,k}(f))^{2} ≤ Cσ^{2} and |EJ_{n,k}(f)| ≤ Cσ,

where σ^{2} = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) (3.10)

with some universal constant C > 0 depending only on the order of the random integral J_{n,k}(f).

Relation (3.10) yields such an estimate for the second moment of J_{n,k}(f) as we expect. On the other hand, although it gives a sufficiently good bound on its first moment, it does not state that the expectation of J_{n,k}(f) equals zero. Indeed, formula (3.7) only gives that |EJ_{n,k}(f)| = |C(n, k, ∅)f_{∅}| ≤ C|f_{∅}| = C |∫ f(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k})| ≤ Cσ with some appropriate constant C > 0. The following example shows that EJ_{n,k}(f) need not be always zero. (To understand better why such a situation may appear observe that the random measures (μ_{n} − μ)(B_{1}) and (μ_{n} − μ)(B_{2}) are not independent for disjoint sets B_{1} and B_{2}.)

We consider a random integral J_{n,2}(f) of order 2 with an appropriate kernel function f. We choose a sequence of independent random variables ξ_{1}, …, ξ_{n} with uniform distribution on the unit interval [0, 1] and denote its empirical distribution by μ_{n}. The function f = f(x, y) we shall choose is the indicator function of the unit square, i.e. f(x, y) = 1 if 0 ≤ x, y ≤ 1, and f(x, y) = 0 otherwise. We consider the random integral J_{n,2}(f) = n ∫_{x≠y} f(x, y)(μ_{n}( dx) − dx)(μ_{n}( dy) − dy) and calculate its expected value EJ_{n,2}(f). By adjusting the diagonal x = y to the domain of integration and taking out the contribution obtained in this way we get that EJ_{n,2}(f) = nE(∫_{0}^{1} (μ_{n}( dx) − μ( dx))^{2} − n^{2} · \frac{1}{n^{2}} = −1, i.e. the expected value of the above random integral is not equal to zero. (The last term is the integral of the function f(x, y) on the diagonal x = y with respect to the product measure μ_{n} ×μ_{n} which equals (μ_{n} − μ) × (μ_{n} − μ) on the diagonal.)

Now we return to the second problem discussed in this section.

B. Limit theorems for U-statistics and random integrals.

The following limit theorem about normalized degenerate U-statistics will be interesting for us.

Theorem 3.3. Limit theorem about normalized degenerate U-statistics. Let us consider a sequence of degenerate U-statistics I_{n,k}(f) of order k, n = k, k+1, …, defined in (1.3) with the help of a kernel function f(x_{1}, …, x_{k}) on the k-fold product (X^{k}, X^{k}) of a measurable space (X, X), canonical with respect to some non-atomic probability measure μ on (X, X) and such that ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ(dx_{k}) < ∞ together with a sequence of independent and identically distributed random variables ξ_{1}, ξ_{2}, … with distribution μ on (X, X). The sequence of normalized U-statistics n^{−k/2}I_{n,k}(f) converges in distribution, as n → ∞, to the k-fold Wiener–Itô integral

\frac{1}{k!}Z_{μ,k}(f) = \frac{1}{k!} ∫ f(x_{1}, …, x_{k})μ_{W} (dx_{1}) … μ_{W} (dx_{k})

with kernel function f(x_{1}, …, x_{k}) and a white noise μ_{W} with reference measure μ.

The proof of Theorem 3.3 can be found for instance in [5]. Here I present a heuristic explanation of this result.

To understand Theorem 3.3 it is useful to rewrite the normalized degenerate Ustatistics we consider in the form of multiple random integrals with respect to a normalized empirical measure. We can write

\begin{aligned}n^{−k/2}I_{n,k}(f) & = n^{k/2} ∫ ′ f(x_{1}, …, x_{k})μ_{n}( dx_{1}) … μ_{n}( dx_{k}) \\ & = n^{k/2} ∫ ′ f(x_{1}, …, x_{k})(μ_{n}( dx_{1}) − μ( dx_{1})) … (μ_{n}( dx_{k}) − μ( dx_{1})), \end{aligned}

(3.11)

where μ_{n} is the empirical distribution function of the sequence ξ_{1}, …, ξ_{n} defined in (1.1), and the prime in ∫′ denotes that the diagonals, i.e. the points x = (x_{1}, …, x_{k}) such that x_{j} = x_{j′} for some pairs of indices 1 ≤ j, j′ ≤ k, j ≠ j′ are omitted from the domain of integration. The last identity of formula (3.11) holds, because in the case of a function f(x_{1}, …, x_{k}) canonical with respect to a non-atomic measure μ we get the same result by integrating with respect to μ_{n}( dx_{j}) and with respect to μ_{n}( dx_{j}) − μ( dx_{j}). (The non-atomic property of the measure μ is needed to guarantee that the integrals we consider with respect to the measure μ remain zero if the diagonals are omitted from the domain of integration.)

Formula (3.11) may help to understand Theorem (3.3), because the random fields n^{1/2}(μ_{n}(A) − μ(A)), A ∈ X, converge to a Gaussian field ν(A), A ∈ X, as n → ∞, and this suggests a limit similar to the result of Theorem (3.3). But it is not so simple to carry out a limiting procedure leading to the proof of Theorem 3.3 with the help of formula (3.11). Some problems arise, because the fields n^{1/2}(μ_{n} − μ) converge to a not white noise type Gaussian field. The limit we get is similar to a Wiener bridge on the real line. Hence a relation between Wiener processes and Wiener bridges suggests to write the following version of formula (3.11). Let η be a standard Gaussian random variable, independent of the random sequence ξ_{1}, ξ_{2}, . . .. We can write, by exploiting again the canonical property of the function f, the identity

\begin{aligned}n^{−k/2}I_{n,k}(f) = n^{k/2} ∫ ′ & f(x_{1}, …, x_{k})(μ_{n}( dx_{1}) − μ( dx_{1}) + ημ( dx_{1})) \\ & … (μ_{n}( dx_{k}) − μ( dx_{k}) + ημ( dx_{k})). \end{aligned}  (3.12)

The random measures n^{1/2}(μ_{n} − μ + ημ) converge to a white noise with reference measure μ, hence a limiting procedure in formula (3.12) yields Theorem 3.3. Moreover, in the case of elementary functions f the central limit theorem and formula (3.12) imply the statement of Theorem 3.3 directly. (Elementary functions are defined in formula (1.6).) After this, Theorem 3.3 can be proved in the general case with the help of the investigation of the L_{2}-contraction property of some operators. I omit the details.

A similar limit theorem holds for random integrals J_{n,k}(f). It can be proved by means of Theorem 3.2 and an adaptation of the above sketched argument for the proof of Theorem 3.3. It states the following result.

Theorem 3.4. Limit theorem about multiple random integrals J_{n,k}(f). Let us have a sequence of independent and identically distributed random variables ξ_{1}, ξ_{2}, … with some non-atomic distribution μ on a measurable space (X, X) and a function f(x_{1}, …, x_{k}) on the k-fold product (X^{k}, X^{k}) of the space (X, X) such that

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

Let us consider for all n = 1, 2, … the random integrals J_{n,k}(f) of order k defined in formulas (1.1) and (1.2) with the help of the empirical distribution μ_{n} of the sequence ξ_{1}, …, ξ_{n} and the function f. The random integrals J_{n,k}(f) converge in distribution, as n → ∞, to the following sum U(f) of multiple Wiener–Itô integrals:

U(f) = ∑_{V ⊂\{1,...,k\}}\frac{C(k, V)}{V!}Z_{μ,|V |}(f_{V}) = ∑_{V ⊂\{1,...,k\}}\frac{C(k, V)}{V!} ∫ f_{V} (x_{j}, j ∈ V) ∏_{j∈V} μ_{W} (dx_{j}),

where the functions f_{V} (x_{j} j ∈ V), V ⊂ {1, …, k}, are those functions defined in formula (3.4) which appear in the Hoeffding decomposition of the function f(x_{1}, …, x_{k}), the constants C(k, V) are the limits appearing in the limit relation lim_{n→∞} C(n, k, V) = C(k, V) satisfied by the quantities C(n, k, V) in formula (3.7), and μ_{W} is a white noise with reference measure μ.

The results of this section suggest that to understand what kind of results we can expect for the solution of problems a) and a′) it is useful to study first their simpler counterpart, problem a′′) about the behaviour of multiple Wiener–Itô integrals. They also show that problem a′) is interesting in the case when the distribution of degenerate U-statistics is investigated. The next section contains some results about these problems.

4. Estimates on the distribution of random integrals and U-statistics

First I formulate the results about the solution of problem a′′), about the tail-behaviour of multiple Wiener–Itô integrals.

Theorem 4.1. Let us consider a σ-finite measure μ on a measurable space (X, X) together with a white noise μ_{W} with reference measure μ. Let us have a real-valued function f(x_{1}, …, x_{k}) on the space (X^{k}, X^{k}) which satisfies relation (1.4) with some σ^{2} < ∞. Take the random integral Z_{μ,k}(f) introduced in formula (1.5). It satisfies the inequality

P (|Z_{μ,k}(f)| > u) ≤ C exp \{−\frac{1}{2} (\frac{u}{σ} )^{2/k}\} for all u > 0  (4.1)

with an appropriate constant C = C(k) > 0 depending only on the multiplicity k of the integral.

The next example shows that the estimate of Theorem 4.1 is sharp.

Example 4.2. Let us have a σ-finite measure μ on some measurable space (X, X) together with a white noise μ_{W} on (X, X) with reference measure μ. Let f_{0}(x) be a real valued function on (X, X) such that ∫ f_{0}(x)^{2}μ( dx) = 1, and take the function f(x_{1}, …, x_{k}) = σf_{0}(x_{1}) ⋯ f_{0}(x_{k}) with some number σ > 0 and the Wiener–Itô integral Z_{μ,k}(f) introduced in formula (1.5). Then the relation

∫ f(x_{1}, …, x_{k})^{2} μ( dx_{1}) … μ( dx_{k}) = σ^{2}

holds, and the Wiener–Itô integral Z_{μ,k}(f) satisfies the inequality

P (|Z_{μ,k}(f)| > u) ≥ \frac{C̄}{(\frac{u}{σ})^{1/k} + 1} exp \{−\frac{1}{2} (\frac{u}{σ} )^{2/k}\} for all u > 0  (4.2)

with some constant C̄ > 0.

Let us also remark that a Wiener–Itô integral Z_{μ,k}(f) defined in (1.5) with a kernel function f satisfying relation (1.4) also satisfies the relations EZ_{μ,k}(f) = 0 and EZ_{μ,k}(f)^{2} ≤ k!σ^{2} with the number σ^{2} appearing in (1.4). We can write identity in the last inequality if the function f is symmetric, i.e. if f(x_{1}, …, x_{k}) = f(x_{π(1)}, …, x_{π(k)}) for all permutations π of the set {1, …, k}. Hence we can interpret Theorem 4.1 in the following way. The random integral Z_{μ,k}(f) has expectation zero, its variance is less than or equal to k!σ^{2}, there is identity in this relation if f is a symmetric function, and the tail-behaviour of the distribution of this random integral satisfies an estimate similar to that of ση^{k}, where η is a standard normal random variable. We cannot state that the estimate (4.1) in Theorem 4.1 is always sharp, but Example 4.2 shows that there are cases when the exponent in estimate (4.1) cannot be improved.

Let me also remark that the above statement can be formulated in a slightly nicer form if we compare the distribution of Z_{μ,k}(f) not with that of ση^{k}, but with that of σH_{k}(η), where H_{k}(x) is the k-th Hermite polynomial with leading coefficient 1. The identities EH_{k}(η) = 0, EH_{k}(η)^{2} = k! hold. Thus we can say not only that the tail distributions of Z_{μ,k}(f) and σH_{k}(η) are similar, but in the case of a symmetric function f also their first two moments agree.

In problems a) and a′) we can expect an estimate slightly weaker but similar to that of Theorem 4.1. In the case of problem a′) the following result holds (see [12]).

Theorem 4.3. Let ξ_{1}, …, ξ_{n} be a sequence of independent and identically distributed random variables on a space (X, X) with some distribution μ. Let us consider a function f(x_{1}, …, x_{k}) on the space (X^{k}, X^{k}), canonical with respect to the measure μ which satisfies the conditions

∥f∥_{∞} = sup_{x_{j}∈X, 1≤j≤k} |f(x_{1}, …, x_{k})| ≤ 1,  (4.3)
∥f∥_{2}^{2} = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2},  (4.4)

with some 0 < σ^{2} ≤ 1 together with the degenerate U-statistic I_{n,k}(f) defined in formula (1.3) with this kernel function f. There exist some constants A = A(k) > 0 and B = B(k) > 0 depending only on the order k of the U-statistic I_{n,k}(f) such that

P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ A exp \{−\frac{u^{2/k}}{2σ^{2/k} (1 + B (un^{−k/2}σ^{−(k+1)})^{1/k})}\} (4.5)

for all 0 ≤ u ≤ n^{k/2}σ^{k+1}.

Remark: Actually, the universal constant B > 0 can be chosen independently of the order k of the degenerate U-statistic I_{n,k}(f) in inequality (4.5).

Theorem 4.3 can be considered as a generalization of Bernstein’s inequality (Theorem 2.2) to the multivariate case in a slightly weaker form when only the sum of independent and identically distributed random variables is considered. Its statement, inequality (4.5) does not contain an explicit value for the constants A and B, which are equal to A = 2 and B = \frac{1}{3} in the case of Bernstein’s inequality. (The constant A = 2 appears, because we wrote absolute value in the probability at left-hand side of (4.5).) There is a formal difference between formula (2.2) and the statement of formula (4.5) in the case k = 1, because in formula (4.5) the U-statistic I_{n,k}(f) of order k is multiplied by n^{−k/2}. Another difference is between them that inequality (4.5) in Theorem 4.3 is stated under the condition 0 ≤ u ≤ n^{k/2}σ^{k+1}, and this restriction has no counterpart in Bernstein’s inequality. But, as I shall show, Theorem 4.3 also contains an estimate for u ≥ n^{k/2}σ^{k+1} in an implicit way, and it can be considered as the multivariate version of Bernstein’s inequality.

Beside this, Bernstein’s inequality gives a good estimate only if 0 ≤ u ≤ const. \sqrt{n}σ^{2}

(with the normalization of Theorem 4.3, i.e. if the probability P (n^{−1/2} ∑_{k=1}^{n} X_{k} > u)

is considered). As we shall see, in the multivariate case a similar picture appears. We get a good estimate for problem a′) suggested by Theorem 4.1 only under the condition 0 ≤ u ≤ const. n^{k/2}σ^{k+1}. Let us also observe that if 0 < u ≤ εn^{k/2}σ^{k+1} with a sufficiently small ε > 0, then Theorem 4.3 implies the inequality P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ A exp \{−\frac{1−Cε^{1/k}}{2} (\frac{u}{σ})^{2/k}\} with some universal constants A > 0 and C > 0 depending only on the order k of the U-statistic I_{n,k}(f). This means that in this case Theorem 4.3 yields an almost as good estimate as Theorem 4.1 about the distribution of multiple Wiener–Itô integrals. We have seen that Bernstein’s inequality has a similar property if we compare the estimate (2.2) in the case 0 < u ≤ εV_{n}^{2} with a small ε > 0 to the central limit theorem.

To see what kind of estimate Theorem 4.3 yields in the case u ≥ n^{k/2}σ^{k+1} let us observe that in condition (4.4) we have an inequality and not an identity. Hence in the case n^{k/2} ≥ u > n^{k/2}σ^{k+1} relation (4.5) holds with σ̄ = (un^{−k/2})^{1/(k+1)}, and we have

P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ A exp \{−\frac{1}{2(1+B)^{1/k}} (\frac{u}{σ̄})^{2/k}\} = Ae^{−(u^{2}n)^{1/(k+1)}/2(1+B)^{1/k}}.

(The inequality n^{k/2} ≥ u was imposed to satisfy the condition 0 ≤ σ̄^{2} ≤ 1.) If u > n^{k/2}, then the probability at the left-hand side of (4.5) equals zero because of condition (4.3). It is not difficult to see by means of the above calculation that Theorem 4.3 implies the inequality

P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ c_{1} exp \{−\frac{c_{2}u^{2/k}}{σ^{2/k} (1 + c_{3} (un^{−k/2}σ^{−(k+1)})^{2/k(k+1)})}\}
for all u > 0

(4.6)

with some universal constants c_{1}, c_{2} and c_{3} depending only on the order k of the Ustatistic I_{n,k}(f), if the conditions of Theorem 4.3 hold. Inequality (4.6) holds for all u ≥ 0. Arcones and Giné formulated and proved this estimate in a slightly different but equivalent form in paper [2] under the name generalized Bernstein’s inequality. This result is weaker than Theorem 4.3, since it does not give a good value for the constant c_{2}. The method of paper [2] is based on a symmetrization argument. Symmetrization arguments can be very useful in the study of problems b) and b′) formulated in the Introduction, but they cannot supply a proof of Theorem 4.3 with good constants because of some principal reasons.

The following result which can be considered as a solution of problem a) is a fairly simple consequence of Theorem 4.1, Theorem 3.2 and formulas (3.8) and (3.9).

Theorem 4.4. Let us take a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} on a measurable space (X, X) with a non-atomic distribution μ on it together with a measurable function f(x_{1}, …, x_{k}) on the k-fold product (X^{k}, X^{k}) of the space (X, X) with some k ≥ 1 which satisfies conditions (4.3) and (4.4) with some constant 0 < σ ≤ 1. Then there exist some constants C = C_{k} > 0 and α = α_{k} > 0 such that the random integral J_{n,k}(f) defined by formulas (1.1) and (1.2) with this sequence of random variables ξ_{1}, …, ξ_{n} and function f satisfies the inequality

P (|J_{n,k}(f)| > u) ≤ C exp \{−α (\frac{u}{σ} )^{2/k}\} for all 0 < u ≤ n^{k/2}σ^{k+1}.  (4.7)

Theorem 4.4 provides a slightly weaker estimate on the probability considered in Problem a) than Theorem 4.3 about its counterpart in Problem a′). It does not give an almost optimal constant α in the inequality (4.7) for 0 ≤ u ≤ εn^{k/2}σ^{k+1} with a small ε > 0. On the other hand, this estimate is sharp in that sense that disregarding the value of the universal constant in them we cannot present a better estimate. It seems to be appropriate in the solution of the problems about non-parametric maximum likelihood estimates mentioned in the Introduction.

Formula (4.7) can be rewritten as an estimate on the probability P (|J_{n,k}(f)| > u) in a form similar to relation (4.6), which holds for all u > 0. On the other hand, both Theorem 4.3 and Theorem 4.4 yield a very weak estimate if u ≫ n^{k/2}σ^{k+1}. We met a similar situation in Section 3 when these problems were investigated in the case k = 1. It is natural to expect that a generalization of Bennett’s inequality holds in the multivariate case k ≥ 2, and it gives an improvement of estimates (4.5) and (4.7) in the case u ≫ n^{k/2}σ^{k+1} for all k ≥ 1. I can prove only partial results in this direction which are not sharp in the general case. On the other hand, there is a possibility to give such a generalization of Example 2.4 which shows that the inequalities implied by Theorem 4.3 or 4.4 in the case u ≥ n^{k/2}σ^{k+1}, k ≥ 2 have only a slight improvement.

The results of Theorems 4.3 and 4.4 imply that in the case u ≤ n^{k/2}σ^{k+1} under the condition of these results the probabilities P (n^{k/2}|I_{n,k}(f)| > u) and P (|J_{n,k}(f)| > u) can be bounded by P (Cσ|η|^{k} > u) with an appropriate universal constant C = C(k) > 0 depending only on the order k of the degenerate U-statistic I_{n,k}(f) or of the multiple random integral J_{n,k}(f), where the random variable η has standard normal distribution, and σ^{2} = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}). A generalization of Example 2.4 can be given which shows for all k ≥ 1 that in the case u ≫ n^{k/2}σ^{k+1} we can have only a much weaker estimate. I shall present such an example only for k = 2, but it can be generalized for all k ≥ 1. This example is taken from my Lecture Note [14] (Example 8.6). Here I present it without a detailed proof. The proof which exploits the properties of Example 2.4 is not long. But I found more instructive to explain the idea behind this example.

Example 4.5. Let ξ_{1}, …, ξ_{n} be a sequence of independent, identically distributed valued random variables taking values on the plane, i.e. on X = R^{2}, such that ξ_{j} = (η_{j,1}, η_{j,2}), η_{j,1} and η_{j,2} are independent, P (η_{j,1} = 1) = P (η_{j,1} = −1) = \frac{σ^{2}}{8} , P (η_{j,1} = 0) = 1 − \frac{σ^{2}}{4} , P (η_{j,2} = 1) = P (η_{j,2} = −1) = \frac{1}{2} for all 1 ≤ j ≤ n. Let us introduce the function f(x, y) = f((x_{1}, x_{2}), (y_{1}, y_{2})) = x_{1}y_{2} + x_{2}y_{1}, x = (x_{1}, x_{2}) ∈ R^{2}, y = (y_{1}, y_{2}) ∈ R^{2} on X^{2}, and define the U-statistic

I_{n,2}(f) = ∑_{1≤j,k≤n, j≠k}(η_{j,1}η_{k,2} + η_{k,1}η_{j,2})  (4.8)

of order 2 with the above kernel function f and the sequence of independent random variables ξ_{1}, …, ξ_{n}. Then I_{n,2}(f) is a degenerate U-statistic. If u ≥ B_{1}nσ^{3} with some appropriate constant B_{1} > 0, B_{2}^{−1}n ≥ u ≥ B_{2}n^{−2} with a sufficiently large fixed number B_{2} > 0, and 1 ≥ σ ≥ \frac{1}{n}, then the estimate

P (n^{−1}I_{n,2}(f) > u) ≥ exp \{−Bn^{1/3}u^{2/3} log (\frac{u}{nσ^{3}} )\}  (4.9)

holds with some constant B > 0 depending neither on n nor on σ.

It is not difficult to see that the U-statistic I_{n,2}(f) introduced in Example 4.5 is a degenerate U-statistic of order two with a kernel function f such that sup |f(x, y)| ≤ 1 and σ^{2} = ∫ f^{2}(x, y)μ( dx)μ( dy) = E(2η_{j,1}η_{j,2})^{2} = σ^{2}. Example 4.5 means that in the case u ≫ nσ^{3}, (i.e. if u ≫ n^{k/2}σ^{k+1} with k = 2) we have a much weaker estimate than in the case u ≤ nσ^{3}. Let us fix the numbers u and n, and consider the dependence of our estimate on σ. We have P (n^{−1}|I_{n,2}(f)| > u) ≤ e^{−Ku/σ} = e^{−Ku^{2/3}n^{1/3}} if σ = u^{1/3}n^{−1/3}, and Example 4.5 shows that a rather weak improvement can be made if σ ≪ u^{1/3}n^{−1/3}.

To understand why the statement of Example 4.5 holds observe that we commit a small error if the condition j ≠ k is omitted from the summation in formula (4.8),

and this suggests that the approximation \frac{1}{n}I_{n,2}(f) ∼ \frac{2}{n} ( ∑_{j=1}^{n} η_{j,1}) ( ∑_{j=1}^{n} η_{j,2}) causes

a negligible error. This fact together with the independence of the sequences η_{j,1}, 1 ≤ j ≤ n, and η_{j,2}, 1 ≤ j ≤ n, imply that

\begin{aligned}P (n^{−1}I_{n,2}(f) > u) & ∼ P ((∑_{j=1}^{n} η_{j,1}) (∑_{j=1}^{n} η_{j,2}) > \frac{nu}{2}) \\ & ≥ P (∑_{j=1}^{n} η_{j,1} > v_{1}) P (∑_{j=1}^{n} η_{j,2} > v_{2}) \end{aligned}  (4.10)

with such a choice of numbers v_{1} and v_{2} for which v_{1}v_{2} = \frac{nu}{2}.

The first probability at the right-hand side of (4.10) can be bounded because of

the result of Example 2.4 as P ( ∑_{j=1}^{n} η_{j,1} > v_{1}) ≥ e^{−Bv_{1} log(4v_{1}/nσ^{2})} if v_{1} ≥ 4nσ^{2}, and

the second probability as P ( ∑_{j=1}^{n} η_{j,2} > v_{2}) ≥ Ce^{−Kv_{2}^{2}/n} with some appropriate C > 0 and K > 0 if 0 ≤ v_{2} ≤ n. We can get the proof of the statement of Example 4.5 by an appropriate choice of the numbers v_{1} and v_{2}.

In Theorem 4.1 the distribution of a k-fold Wiener–Itô integral Z_{μ,k}(f) was bounded by the distribution of ση^{k} with a standard normal random variable η and an appropriate constant σ. By Theorems 4.3 and 4.4 a similar, but weaker estimate holds for the distribution of a degenerate U-statistic I_{n,k}(f) or random integral J_{n,k}(f). In the next section I briefly explain why such results hold.

There is a method to get a good estimate on the moments of the random variables considered in the above theorems, and they enable us to get a good estimate also on the distribution of the random integrals and U-statistics appearing in these theorems. The moments of a k-fold Wiener–Itô integral can be bounded by the moments of ση^{k} with an appropriate σ > 0, and this estimate implies Theorem 4.1. Theorems 4.2 and 4.4 can be proved in a similar way. But we can give a good estimate only on not too high moments of the random variables I_{n,k}(f) and J_{n,k}(f), and this is the reason why we get only a weaker result for their distribution.

5. On the proof of the results in the previous section

Theorem 4.1 can be proved by means of the following

Proposition 5.1. Let the conditions of Theorem 4.1 be satisfied for a multiple Wiener– Itô integral Z_{μ,k}(f) of order k. Then, with the notations of Theorem 4.1, the inequality

E (|Z_{μ,k}(f)|)^{2M} ≤ 1 · 3 · 5 ⋯ (2kM − 1)σ^{2M}  (5.1)

holds for all M = 1, 2, . . ..

By the Stirling formula Proposition 5.1 implies that

E(|Z_{μ,k}(f)|)^{2M} ≤ \frac{(2kM)!}{2^{kM}(kM)!}σ^{2M} ≤ A (\frac{2}{e})^{kM} (kM)^{kM}σ^{2M}  (5.2)

for any A > \sqrt{2} if M ≥ M_{0} = M_{0}(A), and this estimate is sharp. The following Proposition 5.2 which can be applied in the proof of Theorem 4.3 states a similar, but weaker inequality for the moments of normalized degenerate U-statistics.

Proposition 5.2. Let us consider a degenerate U-statistic I_{n,k}(f) of order k with sample size n and with a kernel function f satisfying relations (4.3) and (4.4) with some 0 < σ^{2} ≤ 1. Fix a positive number η > 0. There exist some universal constants A = A(k) > \sqrt{2}, C = C(k) > 0 and M_{0} = M_{0}(k) ≥ 1 depending only on the order of the U-statistic I_{n,k}(f) such that

E (n^{−k/2}k!I_{n,k}(f))^{2M} ≤ A (1 + C\sqrt{α})^{2kM} (\frac{2}{e})^{kM} (kM)^{kM} σ^{2M}
for all integers M such that kM_{0} ≤ kM ≤ αnσ^{2}.

(5.3)

The constant C = C(k) in formula (5.3) can be chosen e.g. as C = 2\sqrt{2} which does not depend on the order k of the U-statistic I_{n,k}(f).

Formula (5.1) can be reformulated as E(|Z_{μ,k}(f)|)^{2M} ≤ E(ση^{k})^{2M}, where η is a standard normal random variable. Theorem 4.1 states that the tail distribution of k!|Z_{μ,k}(f)| satisfies an estimate similar to that of σ|η|^{k}. This can be deduced relatively simply from Proposition 5.1 and the Markov inequality P (|Z_{μ,k}(f)| > u) ≤ \frac{E(k!|Z_{μ,k}(f)|)^{2M}}{u^{2M}} with an appropriate choice of the parameter M.

Proposition 5.2 gives a bound on the moments of k!n^{−k/2}I_{n,k}(f) similar to the estimate (5.2) on the moments of Z_{μ,k}(f). The difference between them is that estimate (5.3) in Proposition 5.2 contains a factor (1 + C\sqrt{α})^{2kM} at its right-hand side, and it holds only for such moments E (k!n^{−k/2}I_{n,k}(f))^{2M} for which kM_{0} ≤ kM ≤ αnσ^{2} with some constant M_{0}. The parameter α > 0 in relation (5.2) can be chosen in an arbitrary way, but it yields a really useful estimate only for not too large values. Theorem 4.3 can be proved by means of the estimate in Proposition 5.2 and the Markov inequality. But because of the relatively weak estimate of Proposition 5.2 we can get only the estimate of Theorem 4.3 for degenerate U-statistics. The main step both in the proof of Theorem 4.1 and 4.3 is to get the moment estimates of Propositions 5.1 and 5.2.

Proposition 5.1 can be proved by means of an important result about Wiener–Itô integrals, the so-called diagram formula. This result can be found e.g. in [9]. It enables us to rewrite the product of Wiener–Itô integrals as a sum of Wiener–Itô integrals of different order. It got the name ‘diagram formula’, because the kernel functions of the Wiener–Itô integrals appearing in the sum representation of the product of Wiener– Itô integrals are defined with the help of certain diagrams. As the expectation of a Wiener–Itô integral of order k equals zero for all k ≥ 1, the expectation of the product equals the sum of the constant terms (i.e. of the integrals of order zero) in the diagram formula. The sum of the constant terms in the diagram formula can be bounded, and such a calculation leads to the proof of Proposition 5.1.

A version of the diagram formula can be proved both for the product of multiple random integrals J_{n,k}(f) defined in formula (1.2) (see [10]) or for degenerate U-statistics (see [12]) which expresses the product of multiple random integrals or degenerate Ustatistics as a sum of multiple random integrals or degenerate U-statistics of different order. The main difference between these new and the original diagram formula about Wiener–Itô integrals is that in the case of random (non-Gaussian) integrals or degenerate U-statistics some new diagrams appear, and they give an additional contribution in the sum representation of the product of random integrals J_{n,k}(f) or of degenerate U-statistics I_{n,k}(f).

Proposition 5.2 can be proved by means of the diagram formula for the product of degenerate U-statistics and a good bound on the contribution of all integrals corresponding to the diagrams. Theorem 4.4 can be proved similarly by means of the diagram formula for the product of multiple random integrals J_{n,k}(f) (see [10]). The main difficulty of such an approach arises, because the expected value of a k-fold random integral J_{n,k}(f) (unlike that of a Wiener–Itô integral or degenerate U-statistic) may be non-zero also in the case k ≥ 1. The expectation of all these integrals is small, but since the diagram formula contains a large number of such terms, it cannot supply such a sharp estimate for the moments random integrals J_{n,k}(f) as we have for degenerate U-statistics I_{n,k}(f). On the other hand, Theorem 4.4 can be deduced from Theorems 4.3, 3.2, and formulas (3.8) and (3.9).

The statement of Example 4.2 follows relatively simply from another important result about multiple Wiener–Itô integrals, from the so-called Itô formula (see e.g. [7] or [9]) which enables us to express the random integrals considered in Example 4.2 as the Hermite polynomial of an appropriately defined standard normal random variable.

Here I did not formulate the diagram formula, hence I cannot explain the details of the proof of Propositions 5.1 and 5.2. Instead of it I discuss briefly an analogous, but simpler problem which may help in getting some feeling why such results hold.

Let us consider a sequence of independent and identically distributed random vari-

ables ξ_{1}, …, ξ_{n} with expectation zero, take their sum S_{n} = ∑_{j=1}^{n} ξ_{j}, and let us try to

give a good estimate on the moments ES_{n}^{2M} for all M = 1, 2, . . .. Because of the independence of the random variables ξ_{j} and the condition Eξ_{j} = 0 we can write

ES_{n}^{2M} = ∑_{(j_{1},...,j_{s},l_{1},...,l_{s}) j_{1}+···+j_{s}=2M, j_{u}≥2, for all 1≤u≤s l_{u}≠l_{u′} if u≠u′} Eξ_{l_{1}}^{j_{1}} ⋯ Eξ_{l_{s}}^{j_{s}}.  (5.4)

Simple combinatorial considerations show that a dominating number of terms at the right-hand side of (5.4) are indexed by a vector (j_{1}, …, j_{M}, l_{1}, …, l_{M}) such that j_{u} = 2 for all 1 ≤ u ≤ M, and the number of such vectors is equal to \binom{n}{M} \frac{(2M)!}{2^{M}} ∼ n^{M} \frac{(2M)!}{2^{M} M!}. The last asymptotic relation holds if the number n of terms in the random sum S_{n} is sufficiently large. The above considerations suggest that under not too restrictive conditions ES_{n}^{2M} ∼ (nσ^{2})^{M} \frac{(2M)!}{2^{M} M!} = Eη_{nσ^{2}}^{2M}, where σ^{2} = Eξ^{2} is the variance of the terms in the sum S_{n}, and η_{u} is a random variable with normal distribution with expectation zero and variance u. The question arises when the above heuristic argument gives a right estimate.

For the sake of simplicity let us restrict our attention to the case when the absolute value of the random variables ξ_{j} is bounded by 1. Let us observe that even in this case we have to impose a condition that the variance σ^{2} of the random variables ξ_{j} is not too small. Indeed, let us consider such random variables ξ_{j}, for which P (ξ_{j} = 1) = P (ξ_{j} = −1) = \frac{σ^{2}}{2} , P (ξ_{j} = 0) = 1 − σ^{2}. Then these random variables ξ_{j} have variance σ^{2}, and the contribution of the terms Eξ_{j}^{2M}, 1 ≤ j ≤ n, to the sum in (5.4) equals nσ^{2}. If σ^{2} is

very small, then it may occur that nσ^{2} ≫ (nσ^{2})^{M} \frac{(2M)!}{2^{M} M!}, and the approximation given for ES_{n}^{2M} in the previous paragraph does not hold any longer. Let us observe that for larger moments ES_{n}^{2M} the choice of a smaller variance σ^{2} is sufficient to violate the asymptotic relation obtained by this approximation.

A similar picture arises in Proposition 5.2. If the variance of the random variable I_{n,k}(f) is not too small, then those terms give the essential contribution to the moments of I_{n,k}(f) which correspond to such diagrams which appear also in the diagram formula for Wiener–Itô integrals. The higher moment we estimate the stronger condition we have to impose on the variance of I_{n,k}(f) to preserve this property and to get a good bound on the moment we consider.

In the next Section problems b), b′) and b′′) will be discussed, where the distribution of the supremum of an appropriate class of multiple random integrals J_{n,k}(f), degenerate U-statistics I_{n,k}(f) and multiple Wiener–Itô integrals Z_{μ,k}(f) will be estimated for an appropriate class of functions f ∈ F. Under some appropriate conditions for the class of functions F a similar estimate can be proved in these problems as in their natural counterpart when only one function is taken. The only difference is that we may have worse universal constants in the new estimates. The conditions we had to impose in the results about problems a) and a′) appear in their counterparts problems b) and b′) in a natural way. But these conditions also have some hidden, more surprising consequences in the study of the new problems.

6. On the supremum of random integrals and U-statistics

To formulate the results of this section first I introduce some notions which appear in their formulation. Such properties will be introduced which say about a class of functions that it has relatively small and in some sense dense finite subsets.

First I introduce the following definition.

Definition of L_{p}-dense classes of functions with respect to some measure. Let us have a measurable space (Y, Y), together with a σ-finite measure ν and a set G of Y measurable real valued functions on this space. We call G an L_{p}-dense class of functions, 1 ≤ p < ∞, with respect to this measure ν with parameter D and exponent L if for all numbers 1 ≥ ε > 0 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 exists a set G_{ε} ⊂ G with m ≤ Dε^{−L} elements such that inf_{g_{j}∈G_{ε}} ∫ |g − g_{j}|^{p} dν < ε^{p} for all functions g ∈ G.

We shall also need the following notion.

Definition of L_{p}-dense classes of functions. Let us have a measurable space (Y, Y) and a set G of Y measurable real valued functions on this space. We call G an L_{p}-dense class of functions, 1 ≤ p < ∞, with parameter D and exponent L if it is L_{p}-dense with parameter D and exponent L with respect to all probability measures ν on (Y, Y).

The above introduced properties can be considered as a possible version of the socalled ε-entropy frequently applied in the literature. Nevertheless, there seems to exist no unanimously accepted version of this notion. Generally we shall apply the above introduced definitions with the choice p = 2, but because of some arguments in this paper it was more natural to introduce them in a more general form. The first result I present can be considered as a solution of problem b′′).

Theorem 6.1 Let us consider a measurable space (X, X) together with a σ-finite nonatomic measure μ on it, and let μ_{W} be a white noise with reference measure μ on (X, X).

Let F be a countable and L_{2}-dense class of functions f(x_{1}, …, x_{k}) on (X^{k}, X^{k}) with some parameter D and exponent L with respect to the product measure μ^{k} such that

∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2} with some 0 < σ ≤ 1 for all f ∈ F.

Let us consider the multiple Wiener integrals Z_{μ,k}(f) introduced in formula (1.5) for all f ∈ F. The inequality

P (sup_{f∈F} |Z_{μ,k}(f)| > u) ≤ C(D +1) exp \{−α (\frac{u}{σ} )^{2/k}\} if (\frac{u}{σ} )^{2/k} ≥ ML log \frac{2}{σ} (6.1)

holds with some universal constants C = C(k) > 0, M = M(k) > 0 and α = α(k) > 0.

The next two results can be considered as a solution of problems b) and b′).

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

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

and

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

(6.3)

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)| ≥ u) ≤ CD exp \{−α (\frac{u}{σ} )^{2/k}\}

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

(6.4)

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

Theorem 6.3. Let us have a probability measure μ on a measurable space (X, X) together with a countable and L_{2}-dense class F of functions f = f(x_{1}, …, x_{k}) of k variables with some parameter D and exponent L, L ≥ 1, on the product space (X^{k}, X^{k}) which satisfies conditions (6.2) and (6.3) with some constant 0 < σ ≤ 1. Beside these conditions let us also assume that the U-statistics I_{n,k}(f) defined with the help of a sequence of independent μ distributed random variables ξ_{1}, …, ξ_{n} are degenerate for all f ∈ F, or in an equivalent form, all functions f ∈ F are canonical with respect to the measure μ. 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 inequality

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

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

(6.5)

holds, where β = max (\frac{log D}{log n} , 0) and the number D and L agree with the parameter and exponent of the L_{2}-dense class F.

The above theorems say that under some conditions on the class of functions F we can give an almost as good estimate for problems b), b′) and b′′) as for the analogous problems a), a′) and a′′), where similar problems were investigated, but only one function f was considered. An essential restriction in the results of Theorems 6.1, 6.2 and 6.3 is that the condition (\frac{u}{σ})^{2/k} ≥ M(L, D) log \frac{2}{σ} is imposed in them with some constant M(L, D, k) depending on the exponent L and parameter D of the L_{2}-dense class F. In Theorem 6.1 we have chosen M(L, D, k) = ML, in Theorems 6.2 and 6.3 M(L, D, k) = M(L + β)^{3/2} with an appropriate universal constant M = M(k) and β = max (0, \frac{log D}{log n} ). We are interested not so much in a good choice of the quantity M(L, D, k) in these results. Actually, they could have been chosen in a better way. We would like to understand why our results hold only under such a condition.

I shall also discuss some other questions related to the above theorems. Beside the role of the lower bound on (\frac{u}{σ})^{2/k} one would also like to understand why we have imposed the condition of L_{2}-dense property for the class of functions F in Theorems 6.2 and 6.3. This is a stronger restriction than the condition about the L_{2}-dense property of the class F with respect to the measure μ^{k} imposed in Theorem 6.1. It may be a little bit mysterious why we need in Theorems 6.2 and 6.3 the condition that this class of functions must be L_{2}(ν)-dense with respect to such probability measures ν which seem to have no relation to our problems. I can give only a partial answer to this question. In the next section I present a very brief sketch of the proofs, and it shows that in the proof of Theorems 6.2 and 6.3 we apply the L_{2}-dense property of the class of functions F in the form as we have imposed it. I shall discuss another question which also naturally arises in this context. One would like to know some results which enable us to check the L_{2}-dense property and which show that it holds in many interesting cases.

I shall discuss still another problem related to the above results. One would like to weaken the condition by which the classes of functions F must be countable. Let me recall that in the Introduction I mentioned that our results can be applied in the study of some non-parametric maximum likelihood problems. In these applications such cases may occur where we have to work with the supremum of non-countably infinite random integrals. I shall discuss this question separately at the end of this section.

I show an example which shows that the condition (\frac{u}{σ})^{2/k} ≥ M(L, D, k) log \frac{2}{σ} with some appropriate constant M(L, D, k) > 0 cannot be omitted from Theorem 6.1. In this example we shall take ([0, 1], B), i.e. the interval [0, 1] together with the Borel σ-algebra as the measurable space (X, X), and introduce the Lebesgue measure λ on [0, 1] together with the usual white noise λ_{W} with the Lebesgue measure as the reference measure. We define the class of functions of k variables F = F_{σ} on ([0, 1]^{k}, B^{k}) consisting of

the indicator functions of the k-dimensional rectangles ∏_{j=1}^{k}[a_{j}, b_{j}] ⊂ [0, 1]^{k} such that all

numbers a_{j} and b_{j}, 1 ≤ j ≤ k, are rational, and the volume of these rectangles satisfy

the condition ∏_{j=1}^{k}(b_{j} − a_{j}) ≤ σ^{2} with some fixed number σ. It can be seen that this

countable class of functions F is L_{2}-dense with respect to the measure λ, (moreover it is L_{2}-dense in the general sense), hence Theorem 6.1 can be applied for the supremum of the Wiener–Itô integrals Z_{λ,k}(f) with the above class of functions f ∈ F.

Let us choose some small number σ > 0 such that σ^{2/k} is a rational number, and let us define the functions f_{j} as the indicator functions of the k-dimensional cube with edges [a_{l}, a_{l+1}] = [(j−1)σ^{2/k}, jσ^{2/k}], 1 ≤ l ≤ for all 1 ≤ j ≤ N, with N = [σ^{−2/k}], where [x] denotes the integer part of the number x. Then all these functions f_{j} are elements of the above defined class of functions F = F_{σ}. The integrals Z_{λ,k}(f_{j}), 1 ≤ j ≤ N, are independent random variables. Hence

P (sup_{f∈F} |Z_{λ,k}(f)| > u) ≥ P ( sup_{1≤j≤N} |Z_{λ,k}(f_{j})| > u) = 1 − P (|Z_{λ,k}(f_{1})| ≤ u)^{N} (6.6)

for all numbers u > 0. I will show with the help of relation (6.6) that for a small σ > 0 and such a number u for which (\frac{u}{σ})^{2/k} = a log \frac{2}{σ} with some a < \frac{4}{k} the probability

P (sup_{f∈F} |Z_{λ,k}(f)| > u) is very close to 1.

Indeed, it can be seen with the help of the Itô formula that for all 0 < γ < 1 there exists some σ_{0} = σ_{0}(γ) such that P (|Z_{λ,k}(f_{1})| ≤ u) ≤ 1 − e^{−γ(u/σ)^{2/k}/2} = 1 − (\frac{σ}{2} )^{γa/2} if 0 < σ < σ_{0}. (Actually a similar calculation is applied also in the proof of the statement of Example 5.2.) Hence relation (6.6) and the inequality N ≥ σ^{−2/k} − 1 imply that

P (sup_{f∈F} |Z_{λ,k}(f)| > u) ≥ 1 − (1 − (\frac{σ}{2} )^{γa/2})^{σ^{−2/k}−1}. By choosing γ sufficiently close

to 1 it can be shown with the help of the above relation that with a sufficiently small

σ > 0 and the above choice of the number u the probability P (sup_{f∈F} |Z_{λ,k}(f)| > u) is

almost 1.

The above calculation shows that a condition of the type (\frac{u}{σ})^{2/k} ≥ M(L, D, k) log \frac{2}{σ} cannot be dropped in Theorem 6.1. With some extra work a similar example can be made in the case of Theorem 6.2. In this example we can choose the same space (X, X), the same class of functions F = F_{σ}, only the white noise has to be replaced for instance by a sequence of independent random variables ξ_{1}, …, ξ_{n} with uniform distribution on the unit interval and with a sufficiently large sample size n. (The lower bound on the sample size should depend also on σ.) Also in the case of Theorem 6.3 a similar example can be constructed. I omit the details.

The theory of Vapnik–Červonenkis classes is a fairly popular and important subject in probability theory. I shall show that this theory is also useful in the study of our problems. It provides a useful sufficient condition for the L_{2}-dense property of a class of functions, a property which played an important role in Theorems 6.2 and 6.3. To formulate the result interesting for us first I recall the notion of Vapnik–Červonenkis classes.

Definition of Vapnik-Červonenkis classes of sets and functions. Let a set S be given, and let us select a class D consisting of certain subsets of this set S. We call D a Vapnik–Červonenkis class if there exist two real numbers B and K such that for all positive integers n and subsets S_{0}(n) = {x_{1}, …, x_{n}} ⊂ S of cardinality n of the set S the collection of sets of the form S_{0}(n)∩D, D ∈ D, contains no more than Bn^{K} subsets of S_{0}(n). We shall call B the parameter and K the exponent of this Vapnik–Červonenkis class.

A class of real valued functions F on a space (Y, Y) is called a Vapnik–Červonenkis class if the collection of 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 subsets of the product space S = Y × R^{1}.

The theory about Vapnik–Červonenkis classes has a big literature. There are results which give a good possibility to show that certain classes of sets or functions are Vapnik– Červonenkis classes. Here I do not discuss them. I only present an important result of Richard Dudley, which states that a Vapnik–Červonenkis class of functions bounded by 1 is an L_{1}-dense class of functions.

Theorem 6.4. Let f(y), f ∈ F, be a Vapnik–Červonenkis class of real valued functions on some measurable space (Y, Y) such that sup_{y∈Y} |f(y)| ≤ 1 for all f ∈ F. Then F is an

L_{1}-dense class of functions on (Y, Y). More explicitly, if F is a Vapnik–Červonenkis class with parameter B ≥ 1 and exponent K > 0, then it is an L_{1}-dense class with exponent L = 2K and parameter D = CB^{2}(4K)^{2K} with some universal constant C > 0.

The proof of this result can be found in [18] (25 Approximation Lemma) or in my Lecture Note [14]. Formally, Theorem 6.4 gives a sufficient condition for a class of functions to be an L_{1}-dense class. But it is fairly simple to show that a class of functions satisfying the conditions of Theorem 6.4 is not only an L_{1}, but also an L_{2}-dense class. Indeed, an L_{1}-dense class of functions whose absolute values are bounded by 1 in the supremum norm is also an L_{2}-dense class, only with a possibly different exponent and parameter. I finish this section by discussing the problem how to replace the condition of countable cardinality of the class of functions in Theorems 6.2 and 6.3 by a useful weaker condition.

On the supremum of non-countable classes of random integrals and Ustatistics

First I introduce the following notion.

Definition of countably approximable classes of random variables. Let a class of random variables U(f), f ∈ F, indexed by a class of functions on a measurable space (Y, Y) be given. We say that this class of random variables U(f), f ∈ F, is countably approximable if there is a countable subset F′ ⊂ F such that for all numbers u > 0 the sets A(u) = {ω: sup_{f∈F} |U(f)(ω)| ≥ u} and B(u) = {ω: sup_{f∈F′} |U(f)(ω)| ≥ u} satisfy the

identity P (A(u) \ B(u)) = 0.

Clearly, B(u) ⊂ A(u) for the sets A(u) and B(u). In the above definition we demanded that for all u > 0 the set B(u) should be almost as large as A(u). It is fairly simple to see that in Theorems 6.1, 6.2 and 6.3 the condition about the countable cardinality of the class of functions F can be replaced by the weaker condition that the class of random variables Z_{μ,k}(f), J_{n,k}(f) or I_{n,k}(f), f ∈ F, is a countably approximable class of functions. One would like to get some results which enable us to check this property. The following simple lemma (see Lemma 4.3 in [14]) may be useful for us.

Lemma 6.5. Let a class of random variables U(f), f ∈ F, indexed by some set F of functions on a space (Y, Y) be given. If there exists a countable subset F′ ⊂ F of the set F such that the sets A(u) = {ω: sup_{f∈F} |U(f)(ω)| ≥ u} and B(u) = {ω: sup_{f∈F′} |U(f)(ω)| ≥

u} introduced for all u > 0 in the definition of countable approximability satisfy the relation A(u) ⊂ B(u − ε) for all u > ε > 0, then the class of random variables U(f), f ∈ F, is countably approximable.

The above property holds if for all f ∈ F, ε > 0 and ω ∈ Ω there exists a function f̄ = f̄(f, ε, ω) ∈ F′ such that |U(f̄)(ω)| ≥ |U(f)(ω)| − ε.

Thus to prove the countable approximability property of a class of random variables U(f), f ∈ F, it is enough to check the condition formulated in the second paragraph of Lemma 6.5. I present an example when this condition can be checked. This example is interesting in particular, because in the study of non-parametric maximum likelihood problems such examples have to be considered.

Let us fix a function f(x_{1}, …, x_{k}), sup |f(x_{1}, …, x_{k})| ≤ 1, on the space (X^{k}, X^{k}) = (R^{ks}, B^{ks}) with some s ≥ 1, where B^{t} denotes the Borel σ-algebra on the Euclidean space R^{t}, together with some probability measure μ on (R^{s}, B^{s}). For all vectors (u_{1}, …, u_{k}), (v_{1}, …, v_{k}) such that u_{j}, v_{j} ∈ R^{s} and u_{j} ≤ v_{j}, 1 ≤ j ≤ k, (i.e. all coordinates of u_{j} is smaller than or equal to the corresponding coordinate of v_{j}) let us define the function f_{u_{1},...,u_{k},v_{1},...,v_{k}} which equals the function f on the rectangle [u_{1}, v_{1}] × ⋯ [u_{k}, v_{k}], and it is zero outside of this rectangle.

Let us consider a sequence of i.i.d. random variables ξ_{1}, …, ξ_{n} taking values in the space (R^{s}, B^{s}) with some distribution μ, and define the empirical measure μ_{n} and random integrals J_{n,k}(f_{u_{1},...,u_{k},v_{1},...,v_{k}}) by formulas (1.1) and (1.2) for all vectors (u_{1}, …, u_{k}), (v_{1}, …, v_{k}), u_{j} ≤ v_{j} for all 1 ≤ j ≤ k, with the above defined functions f_{u_{1},...,u_{k},v_{1},...,v_{k}}. The following result holds (see Lemma 4.4 in [14]).

Lemma 6.6. Let us take n independent and identically distributed random variables ξ_{1}, …, ξ_{n} with values in the space (R^{s}, B^{s}). Let us define with the help of their distribution μ and the empirical distribution μ_{n} determined by them the class of random variables J_{n,k}(f_{u_{1},...,u_{k},v_{1},...,v_{k}}) introduced in formula (1.2), where the class of kernel functions F in these integrals consists of all functions f_{u_{1},...,u_{k},v_{1},...,v_{k}} ∈ (R^{sk}, B^{sk}), u_{j}, v_{j} ∈ R^{s}, u_{j} ≤ v_{j}, 1 ≤ j ≤ k, introduced in the last but one paragraph. This class of random variables J_{n,k}(f), f ∈ F, is countably approximable.

Let me also remark that the class of functions f_{u_{1},...,u_{k},v_{1},...,v_{k}} is also an L_{2}-dense class of functions, actually it is also a Vapnik–Červonenkis class of functions. As a consequence, Theorem 6.2 can be applied for this class of functions.

To understand better the picture behind the above results let us make the following remark. The class of random variables Z_{μ,k}(f), J_{n,k}(f) or I_{n,k}(f), f ∈ F, can be considered as a stochastic process indexed by the functions f ∈ F, and we estimate the supremum of this stochastic process. In the study of a stochastic process with a large parameter set one introduces some smoothness type property of the trajectories which can be satisfied. Here we followed a very similar approach. The condition formulated in the second paragraph of Lemma 6.5 can be considered as the smoothness type property needed in our problem.

In the study of a general stochastic process one has to make special efforts to find its right version with sufficiently smooth trajectories. In the case of the random processes J_{n,k}(f) or I_{n,k}(f), f ∈ F, this right version can be constructed in a natural, simple way. We have a finite sequence of random variables ξ_{1}(ω), …, ξ_{n}(ω) at the start, and we can define the random integrals J_{n,k}(f)(ω) or U-statistics I_{n,k}(f)(ω), f ∈ F, for all ω ∈ Ω on the probability field (Ω, A, P) where the random variables ξ_{1}(ω), …, ξ_{n}(ω) are living separately. It remains to check whether the ‘trajectories’ of this random process have the ‘smoothness properties’ necessary for us. The case of a class of Wiener–Itô integrals Z_{μ,k}(f), f ∈ F, is different. Wiener–Itô integrals are defined with the help of some L_{2}- limit procedure. Hence each random integral Z_{μ,k}(f) is defined only with probability 1, and in the case of a non-countable set of functions F we have to find the right version Z_{μ,k}(f), f ∈ F, of the Wiener–Itô integrals to get a countably approximable class of random variables.

R. M. Dudley (see e.g. [4]) worked out a rather deep theory to overcome the measurability difficulties appearing in the case of a non-countable set of random variables by working with analytic sets, Suslin property, outer probability. e.t.c. I must admit that I do not know the precise relation between this theory and our method. At any rate, in the problems discussed here our elementary approach seems to be satisfactory.

In the next two sections I discuss the idea of the proof of Theorems 6.1, 6.2 and 6.3. A simple and natural approach, the so-called chaining argument suffices to prove Theorem 6.1. In the case of Theorems 6.2 and 6.3 this chaining argument can only help to reduce the proof to a slightly weaker statement, and we apply an essentially different method based on some randomization arguments to complete the proof. Since in the multivariate case k ≥ 2 some essential additional difficulties appear, it seemed to be more natural to discuss it in a separate Section.

7. The method of proof of Theorems 6.1, 6.2 and 6.3

There is a simple but useful method, called the chaining argument, which helps us to prove Theorem 6.1. It suggests to take an appropriate increasing sequence F_{j}, j = 0, 1, …, of L_{2}-dense subsets of the class of functions F and to give a good estimate on the supremum of the Wiener–Itô integrals Z_{μ,k}(f), f ∈ F_{j}, for all j = 0, 1, . . ..

In the application of this method let us first define a sequence of subclasses G_{j} of F, j = 0, 1, 2, …, such that G_{j} = {g_{j,1}, …, g_{j,m_{j}}} ⊂ F is an 2^{−jk}σ-dense subset of F in the L_{2}(μ^{k})-norm, i.e. let

\begin{aligned}inf_{1≤l≤m_{j}} ρ(f, g_{j,l})^{2} & = inf_{1≤l≤m_{j}} ∫ (f(x_{1}, …, x_{k}) − g_{j,l}(x_{1}, …, x_{k}))^{2}μ( dx_{1}) … μ( dx_{k}) \\ & ≤ 2^{−2jk}σ^{2} \end{aligned}

(7.1)

for all f ∈ F, and let m_{j} ≤ D2^{jkL}σ^{−L}. Such sets G_{j} exist because of the conditions

of Theorem 6.1. Let us also define the classes of functions F_{j} = ⋃_{p=0}^{j} G_{p}, and sets B_{j} =

B_{j}(u) = {ω: sup_{f∈F_{j}} Z_{μ,k}(f)(ω) ≥ u (1 − 2^{−jk/2})}, j = 0, 1, 2, . . .. Given a function

f_{j+1,l} ∈ G_{j+1} let us choose such a function f_{j,l′} ∈ F_{j} with some l′ = l′(l) for which ρ(f_{j,l′}, f_{j+1,l}) ≤ 2^{−jk}σ with the function ρ(f, g) defined in formula (7.1). Then

P (B_{j+1}) ≤ P (B_{j}) + ∑_{l=1}^{m_{j+1}} P (|Z_{μ,k}(f_{j+1,l} − f_{j,l′})| > u2^{−k(j+1)/2}) .  (7.2)

Theorem 4.1 enables us to give a good estimate on the terms in the sum at the righthand side of (7.2). Similarly, it enables us to give a good estimate on P (B_{0}). With the help of some small modification of the construction we also can guarantee that

⋃_{j=0}^{∞} F_{j} = F. Then we can get the proof of Theorem 6.1 with the help of the estimates

in Theorem 4.1.

Theorem 6.2 can be deduced from Theorem 6.3 relatively simply with the help of Theorem 3.3, since Theorem 6.3 enables to give a good bound on all terms in the sum at the right-hand side of formula (3.7). The only non-trivial step in this argument is to show that the set of functions f_{V}, f ∈ F, appearing in formula (3.7) satisfy the estimates we need in the application of Theorem 6.3. Relations (3.8) and (3.9) are parts of the estimates we need. Beside this, we have to show that if F is an L_{2}-dense class of functions, then the same relation holds for the class of functions F_{V} = {f_{V} : f ∈ F} for all sets V ⊂ {1, …, k}. This relation can also be shown with the help of a not too difficult proof (see [11] or [14]), but this question will be not discussed here.

One may try to prove Theorem 6.3, similarly to Theorem 6.1, with the help of the chaining argument. But this method does not work well in this case. The reason for its weakness is that the tail distribution of a degenerate U-statistic with a small variance σ^{2} does not satisfy such a good estimate as the tail distribution of a multiple Wiener–Itô integral. At this point the condition u ≤ n^{k/2}σ^{k+1} in Theorem 4.2 plays an important role. Let us recall that, as Example 4.5 shows, the tail distribution of the normalized degenerated U-statistics n^{−k/2}I_{n,k}(f) satisfies only a relatively weak estimate at level u if u ≫ n^{k/2}σ^{k+1}. We may try to work with an estimate analogous to relation (7.2) in the proof of Theorem 6.3. But the probabilities appearing at the right-hand side of such an estimate cannot be well estimated for large indices j.

Thus we can start the procedure of the chaining argument, but after finitely many steps we have to stop it. In such a way we can find a relatively dense subset F_{0} ⊂ F (in L_{2}(μ) norm) such that a good estimate can be given for the distribution of the supremum sup_{f∈F_{0}} I_{n,k}(f). This result enables us to reduce Theorem 6.3 to a slightly

weaker statement formulated in Proposition 7.1 below, but it cannot yield more help. Nevertheless, such a reduction turned out to be useful.

Proposition 7.1. Let us have a probability measure μ on a measurable space (X, X) together with 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 and exponent L on the product space (X^{k}, X^{k}) such that all functions f ∈ F satisfy conditions (6.2) and (6.3) with some 0 < σ ≤ 1. Let us consider the (degenerate) U-statistics I_{n,k}(f) with the random sequence ξ_{1}, …, ξ_{n} and kernel functions f ∈ F. There exists a sufficiently large constant K = K(k) together with 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 such that if nσ^{2} > K(L + β) log n with β = max (\frac{log D}{log n} , 0), then the degenerate U-statistics I_{n,k}(f), f ∈ F, 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}.  (7.3)

The statement of Proposition 7.1 is similar to that of Theorem 6.3. The essential difference between them is that Proposition 7.1 yields an estimate only for u ≥ A_{0}n^{k/2}σ^{k+1} with a sufficiently large constant A_{0}, i.e. for relatively large numbers u. In the case u ≫ n^{k/2}σ^{k+1} it yields a weaker estimate than formula (6.5) in Theorem 6.3, but actually we need this estimate only in the case when the number A in formula (7.3) is bounded away both from zero and infinity.

The reduction of Theorem 6.3 to Proposition 7.1 is useful for us, because the proof of the latter result is based on a symmetrization argument which works only for such numbers u = An^{k/2}σ^{k+1} which satisfy the conditions of Proposition 7.1. It may seem pure luck that Proposition 7.1 covers the case needed to complete the proof of Theorem 6.3 after the application of the chaining argument. But this may have a deeper cause. The proof of Proposition 7.1, briefly explained below, is based on an inductive procedure. In each step of this procedure we diminish the number A_{0} for which we can show that inequality (7.3) holds for all numbers An^{k/2}σ^{k+1} with A ≥ A_{0}. We follow this diminishing procedure of the number A_{0} as far as we can. As the proof shows we have to stop at that point, where the probabilities we are interested have the ‘typical magnitude’ and not the appearance of some ‘irregular event’ yields the main contribution to their values. This means that we have to finish the application of the method of the chaining argument and the inductive procedure in the proof of Proposition 7.1 at the same point.

In the symmetrization argument applied in the proof of Proposition 7.1 several additional difficulties arise if the multivariate case k ≥ 2 is considered. Hence in this section I discuss only the case k = 1. A degenerate U-statistic I_{n,1}(f) of order 1 is the sum of independent, identically distributed random variables with expectation zero. In this paper the proof of Proposition 7.1 will be only briefly explained. A detailed proof can be found in [11] or [14]. Let me also remark that the method of these works was taken from Alexander’s paper [1], where all ideas appeared in a different context.

We shall bound the probability appearing at the left-hand side of (7.3) (with k = 1) from above by the probability of the event that the supremum of appropriate randomized sums is larger than some number. We apply a symmetrization method which means that we estimate an expression we want to bound by means of a randomized (symmetrized) expression. Lemma 7.2, formulated below, has such a character.

Lemma 7.2. Let us fix a countable class of functions F on a measurable space (X, X) together with a real number 0 < σ < 1. Consider a sequence of independent, identically distributed X-valued random variables ξ_{1}, …, ξ_{n} such that Ef(ξ_{1}) = 0, Ef^{2}(ξ_{1}) ≤ σ^{2} for all f ∈ F together with another sequence ε_{1}, …, ε_{n} of independent random variables with distribution P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, independent also of the random sequence ξ_{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 ≥ \frac{3\sqrt{2}}{\sqrt{n}σ} .

(7.4)

Let us first understand why Lemma 7.2 can help in the proof of Proposition 7.1. It enables us to reduce the estimate of the probability at the left-hand side of formula (7.4) to that at its right-hand side. This reduction turned out to be useful for the following reason. At the right-hand side of formula 7.4 we have the probability of such an event which depends on the random variables ξ_{1}, …, ξ_{n} and some randomizing terms ε_{1}, …, ε_{n}. Let us estimate the probability of this event by bounding first its conditional probability under the condition that the values of the random variables ξ_{1}, …, ξ_{n} are prescribed. These conditional probabilities can be well estimated by means of Hoeffding’s inequality formulated below, and the estimates we get for them also yield a good bound on the expression at the right-hand side of (7.4).

Hoeffding’s inequality states that the linear combinations of independent random variables ε_{j}, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, behave so as the central limit theorem suggests. It is formulated in a more explicit way in the following Theorem 7.3.

Theorem 7.3 (Hoeffding’s inequality). Let ε_{1}, …, ε_{n} be independent random variables, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, and let a_{1}, …, a_{n} be arbitrary real

numbers. Put V = ∑_{j=1}^{n} a_{j}ε_{j}. Then

P (V > y) ≤ exp \{−\frac{y^{2}}{2 ∑_{j=1}^{n} a_{j}^{2}} \} for all y > 0.  (7.5)

As we shall see, the application of Lemma 7.2 together with the above mentioned conditioning argument and Hoeffding’s inequality enable us to reduce the estimation of

the distribution of sup_{f∈F} ∑_{j=1}^{n} f(ξ_{j}) to that of sup_{f∈F} ∑_{j=1}^{n} f^{2}(ξ_{j}) ≤ sup_{f∈F} ∑_{j=1}^{n}[f^{2}(ξ_{j}) − Ef^{2}(ξ_{j})] +

n sup_{f∈F} Ef^{2}(ξ_{1}). At first sight it may seem so that we did not gain very much by applying

this approach. We have replaced the estimation of the supremum of a class of sums of independent and identically distributed random variables to the estimation of a similar supremum. But a closer look shows that this method can help us in finding a proof of Proposition 7.1. We have to follow at what level we wanted to bound the distribution of the supremum in the original problem, and what level we have to choose in the modified problem to get a good estimate in the problem we are interested in. It turns out that in the second problem we need a good estimate about the distribution of the supremum of a class of sums of independent and identically distributed random variables at a considerable higher level. This observation enables us to work out an inductive procedure which leads to the proof of Proposition 7.1.

Indeed, in Proposition 7.1 we have to prove estimate (7.3) for all numbers A ≥ A_{0} with some appropriate number A_{0}. Let us observe that this estimate trivially holds if A_{0} > σ^{−2}, because in this case the boundedness condition (6.2) on the functions f ∈ F implies that the probability at the left-hand side of (7.3) equals zero. The argument of the previous paragraph suggests to show that if relation (7.3) holds for some constant A_{0}, then it also holds for a smaller A_{0} and to prove Proposition 7.1 by an inductive procedure in which we diminish the number A_{0} at each step.

The actual proof consists of an elaboration of the details in the above heuristic approach. An inductive procedure is applied in which it is shown that if relation (7.3) holds with some number A_{0} for a class of functions F satisfying the conditions of Proposition 7.1, then this relation also holds for it if A_{0} is replaced by A_{0}^{3/4}, provided that A_{0} is larger than some fixed universal constant. I would like to emphasize that we prove this statement not only for the class of functions F we are interested in, but simultaneously for all classes of functions which satisfy the conditions of Proposition 7.1. As we want to prove the inductive statement for a class of functions F, then we apply our previous information not for this class of functions, but for another appropriately defined class of functions F′ = F′(F) which also satisfies the conditions of Propositions 7.1. I omit the details of the proof, I only discuss one point which deserves special attention.

Hoeffding’s inequality, applied in the justification of the inductive procedure leading to the proof of Proposition 7.1 gives an estimate for the distribution of a single sum, while we need a good estimate on the supremum of a class of sums. The question may arise whether this does not cause some problem in the proof. I try to briefly explain that the reason to introduce the condition about the L_{2}-dense property of the class F was to overcome this difficulty.

In the inductive procedure we want to prove that relation (7.3) holds for all A ≥ A_{0}^{3/4} if it holds for all A ≥ A_{0}. It can be shown by means of the inductive assumption which states that relation (7.3) holds for A ≥ A_{0} and Hoeffding’s inequality (Theorem 7.3) that there is a set D ⊂ Ω such that the conditional probabilities

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

are very small for all f ∈ F, and the probability of the set Ω \ D is negligibly small. Let me emphasize that at this step of the proof we can give a good estimate about the conditional probability in (7.6) for all functions f ∈ F if ω ∈ D, but we cannot work with their supremum which we would need to apply formula (7.4). We overcome this difficulty with the help of the following argument.

Let us introduce the (random) probability measure ν = ν(ω) uniformly distributed in the points ξ_{1}(ω), …, ξ_{n}(ω) for all ω ∈ D. Let us observe that the (random) measure ν has a support consisting of n points, and the ν-measure of all points in the support of ν equals \frac{1}{n}. This implies that we can bound a function defined on the support of the measure ν in the supremum norm by means of its L_{2}(ν)-norm. This property together with the L_{2}(ν)-dense property of the class of functions F imposed in the conditions of Proposition 7.1 imply that we can choose a finite set {f_{1}, …, f_{m}} ⊂ F with relatively few elements m in such a way that for all f ∈ F there is some function f_{l}, 1 ≤ l ≤ m, whose distance from the function f in the L_{2}(ν) norm is less than Aσ^{2}/6,

hence inf_{1≤l≤m} n^{−1/2} | ∑_{j=1}^{n} ε_{j}(f(ξ_{j}) − f_{l}(ξ_{j}))| ≤ n^{1/2} ∫ |f − f_{l}|dν ≤ \frac{An^{1/2}σ^{2}}{6} . The condition

that F is L_{2}-dense with exponent L and parameter D enables us to give a good upper bound on the number m. This is the point, where we exploited the condition that the class of functions F is L_{2}-dense in full strength. Since we can give a good bound on the conditional probability in (7.6) for all functions f = f_{l}, 1 ≤ l ≤ m, we can bound the probability at the right-hand side of (7.4). It turns out that the estimate we get in such a way is sufficiently sharp, and we can prove the inductive statement, hence also Proposition 7.1 by working out the details.

I briefly explain the proof of Lemma 7.2. The randomizing terms ε_{j}, 1 ≤ j ≤ n, in it can be introduced with the help of the following simple lemma.

Lemma 7.4. Let ξ_{1}, …, ξ_{n} and ξ̄_{1}, …, ξ̄_{n} be two sequences of independent and identically distributed random variables with the same distribution μ on some measurable space (X, X), independent of each other. Let ε_{1}, …, ε_{n} be a sequence of independent random variables P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, which is independent of the random sequences ξ_{1}, …, ξ_{n} and ξ̄_{1}, …, ξ̄_{n}. Take a countable set of functions F on the space (X, X). Then the set of random variables

\frac{1}{\sqrt{n}} ∑_{j=1}^{n} (f(ξ_{j}) − f(ξ̄_{j})) , f ∈ F,

and its randomized version

\frac{1}{\sqrt{n}} ∑_{j=1}^{n} ε_{j} (f(ξ_{j}) − f(ξ̄_{j})) , f ∈ F,

have the same joint distribution.

Lemma 7.2 can be proved by means of Lemma 7.4 and some calculations. There is one harder step in the calculations. We have to bound from above a probability of the

type P (\frac{1}{\sqrt{n}} sup_{f∈F} ∑_{j=1}^{n} f(ξ_{j}) > u) by means of a probability of the type

P (\frac{1}{\sqrt{n}} sup_{f∈F} ∑_{j=1}^{n} (f(ξ_{j}) − f(ξ̄_{j})) > u − K)

with some number K > 0. (Here we applied the notation of Lemma 7.4.) At this point the following symmetrization lemma may be useful for us.

Lemma 7.5 (Symmetrization Lemma). Let Z_{p} and Z̄_{p}, p = 1, 2, …, be two sequences of random variables independent of each other, and let the random variables Z̄_{p}, p = 1, 2, …, satisfy the inequality

P (|Z̄_{p}| ≤ α) ≥ β for all p = 1, 2, …  (7.7)

with some numbers α ≥ 0 and β ≥ 0. Then

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

The proof of Lemma 7.5 can be found for instance in [18] (8 Symmetrization Lemma) or in [14] Lemma 7.1.

Let us list the element of the countable class of functions F in Lemma 7.2 in the form F = {f_{1}, f_{2}, …, }. Then Lemma 7.2 can be proved by means of Lemma 7.4 and Lemma 7.5 with the choice of the random variables

Z_{p} = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f_{p}(ξ_{j}) and Z̄_{p} = \frac{1}{\sqrt{n}} ∑_{j=1}^{n} f_{p}(ξ̄_{j}), p = 1, 2, ….  (7.8)

I omit the details.

One may try to generalize the above rather briefly explained proof of Theorem 6.3 to the multivariate case k ≥ 2. Here the question arises how to generalize Lemma 7.2 to the multivariate case and how to prove this generalization. These are highly non-trivial problems. This will be the main subject of the next section.

8. On the proof of Theorem 6.3 in the multivariate case

Here we are mainly interested in the question how to carry out the symmetrization procedure in the proof of Proposition 7.1 to the multivariate case k ≥ 2. It turned out that it is possible to reduce this problem to the investigation of modified U-statistics, where k independent copies of the original random sequence are taken and put into the k different arguments of the kernel function of the U-statistic of order k. Such modified versions of U-statistics are called decoupled U-statistics in the literature, and they can be better studied by means of the symmetrization argument we are going to apply. To give a precise meaning of the above statements some definitions have to be introduced and some results have to be formulated. I introduce the following notions.

The definition of decoupled and randomized decoupled U-statistics. Let us have k independent copies ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, of a sequence ξ_{1}, …, ξ_{n} of independent and identically distributed random variables taking their values on a measurable space (X, X) together with a measurable function f(x_{1}, …, x_{k}) on the product space (X^{k}, X^{k}) with values in a separable Banach space. Then the decoupled U-statistic determined by the random sequences ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, and kernel function f is defined by the formula

Ī_{n,k}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤l_{j}≤n, j=1,...,k \\ l_{j}≠l_{j′} if j≠j′ \end{matrix}} f (ξ_{l_{1}}^{(1)}, …, ξ_{l_{k}}^{(k)}) .  (8.1)

Let us have beside the sequences ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, and function f(x_{1}, …, x_{k}) a sequence of independent random variables ε = (ε_{1}, …, ε_{n}), P (ε_{l} = 1) = P (ε_{l} = −1) = \frac{1}{2}, 1 ≤ l ≤ n, which is independent also of the sequences of random variables ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k. We define the randomized decoupled U-statistic determined by the random sequences ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, the kernel function f and the randomizing sequence ε_{1}, …, ε_{n} by the formula

Ī_{n,k}^{ε}(f) = \frac{1}{k!} ∑_{\begin{matrix}1≤l_{j}≤n, j=1,...,k \\ l_{j}≠l_{j′} if j≠j′ \end{matrix}} ε_{l_{1}} ⋯ ε_{l_{k}}f (ξ_{l_{1}}^{(1)}, …, ξ_{l_{k}}^{(k)}) .  (8.2)

Our first goal is to reduce the study of inequality (7.3) in Proposition 7.1 to an analogous problem about the supremum of decoupled U-statistics defined above. Then we want to show that a symmetrization argument enables us to reduce this problem to the study of randomized decoupled U-statistics introduced in formula (8.2). A result of de la Peña and Montgomery–Smith formulated below can be considered as the realization of our first goal. Let me remark that both in the definition of decoupled Ustatistics and in the result of de la Peña and Montgomery–Smith such functions f are considered which take their values in a separable Banach space, i.e. we do not restrict our attention to real-valued functions. This is not because of my inclination for results in general spaces, but because in such a general setting we can get a simpler proof of inequality (8.4) presented below. (The definition of U-statistics given in formula (1.3) is also meaningful in the case of Banach-space valued functions f.)

Theorem 8.1. (de la Peña and Montgomery–Smith) Let us consider a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} on a measurable space (X, X) together with k independent copies ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k. Let us also have a function f(x_{1}, …, x_{k}) on the k-fold product space (X^{k}, X^{k}) which takes its values on a separable Banach space B. Define the U-statistic and decoupled U-statistic I_{n,k}(f) and Ī_{n,k}(f) with the help of the above random sequences ξ_{1}, …, ξ_{n}, ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, and kernel function f. There exist some constants C̄ = C̄(k) > 0 and γ = γ(k) > 0 depending only on the order k of the U-statistic such that

P (∥I_{n,k}(f)∥ > u) ≤ C̄P (∥Ī_{n,k}(f)∥ > γu)  (8.3)

for all u > 0. Here ∥ · ∥ denotes the norm in the Banach space B where the function f takes its values.

More generally, if we have a countable sequence of functions f_{s}, s = 1, 2, …, taking their values in the same separable Banach-space, then

P ( sup_{1≤s<∞} ∥I_{n,k}(f_{s})∥ > u) ≤ C̄P ( sup_{1≤s<∞} ∥Ī_{n,k}(f_{s})∥ > γu) .  (8.4)

The proof of Theorem 8.2 can be found in [3] or in Appendix B of my Lecture Note [14]. Actually [3] contains only the proof of inequality (8.3), but (8.4) can be deduced from it simply by introducing appropriate separable Banach spaces and by exploiting that the universal constants in formula (8.3) do not depend on the Banach space where the random variables are living. Theorem 8.1 is useful for us, because it shows that Proposition 7.1 simply follows from its version presented in Proposition 8.2 below, where U-statistics are replaced by decoupled U-statistics. The distribution of a decoupled U-statistic is not changing if we replace the sequences of random variables put in some coordinates of its kernel function by an independent copy, and this is a very useful property in the application of symmetrization arguments. Beside this, the usual arguments applied in calculation with usual U-statistics can be adapted to the study of decoupled U-statistics. Now I formulate the following version of Proposition 7.1.

Proposition 8.2. Let a class of functions f ∈ F on the k-fold product (X^{k}, X^{k}) of a measurable space (X, X), a probability measure μ on (X, X) together with a sequence of independent and μ distributed random variables ξ_{1}, …, ξ_{n} satisfy the conditions of Proposition 7.1. Let us take k independent copies ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, of the random sequence ξ_{1}, …, ξ_{n}, and consider the decoupled U-statistics Ī_{n,k}(f), f ∈ F, defined with their help by formula (8.1). There exists a sufficiently large constant K = K(k) together with some number γ = γ(k) > 0 and threshold index A_{0} = A_{0}(k) > 0 depending only on the order k of the decoupled U-statistics we consider such that if nσ^{2} > K(L + β) log n with β = max (\frac{log D}{log n} , 0), then the (degenerate) decoupled U-statistics Ī_{n,k}(f), f ∈ F, satisfy the following version of inequality (7.3):

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

It is clear that Proposition 8.2 and Theorem 8.1 imply Proposition 7.1. Hence it is enough to concentrate on the proof of Proposition 8.2. It is natural to try to adapt the method applied in the proof of Proposition 7.1 in the case k = 1. I try to explain what kind of new problems appear in the multivariate case, and how to overcome them.

The proof of Proposition 7.1 was based on a symmetrization type result formulated in Lemma 7.2 and Hoeffding’s inequality (Theorem 7.3). We have to find the multivariate versions of these results. It is not difficult to find the multivariate version of Hoeffding’s inequality. Such a result can be found in [14] (Theorem 12.3), or [13] contains an improved version with optimal constant in the exponent. Here I do not formulate this result, I only explain its main content. Let us consider a homogeneous polynomial of Rademacher functions of order k. The multivariate version of Hoeffding’s inequality states that its tail distribution can be bounded by that of Kση^{k} with some constant K = K(k) depending only on the order k of the homogeneous polynomial, where η is a standard normal random variable, and σ^{2} is the variance of the random homogeneous polynomial.

The problem about the multivariate generalization of Lemma 7.2 is much harder. We want to prove the following multivariate version of this result.

Lemma 8.3. Let F be a class of functions on the space (X^{k}, X^{k}) which satisfies the conditions of Proposition 7.1 with some probability measure μ. Let us have k independent copies ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, of a sequence of independent μ distributed random variables ξ_{1}, …, ξ_{n}, and a sequence of independent random variables ε = (ε_{1}, …, ε_{n}), P (ε_{l} = 1) = P (ε_{l} = −1) = \frac{1}{2}, 1 ≤ l ≤ n, which is independent also of the random sequences ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k. Consider the decoupled U-statistics Ī_{n,k}(f) defined with the help of these random variables by formula (8.1) together with their randomized version Ī_{n,k}^{ε}(f) defined in (8.2) for all f ∈ F. There exists some constant A_{0} = A_{0}(k) > 0 such that the inequality

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})
+ Bn^{k−1}e^{−A^{1/(2k−1)}nσ^{2}/k}  (8.6)

holds for all A ≥ A_{0} with some appropriate constant B = B(k). One can choose for instance B = 2^{k} in this result.

The estimate (8.6) in Lemma 8.3 is similar to formula (7.4) in Lemma 7.2. There is a slight difference between them, because the right-hand side of (8.6) contains an additional constant term. But this term is sufficiently small, and its presence causes no problem as we try to prove Proposition 8.2 by means of Lemma 8.3. In this proof we want to estimate the distribution of the supremum of the decoupled U-statistics Ī_{n,k}(f), f ∈ F, defined in formula (8.1), and Lemma 8.3 helps us in reducing this problem to an analogous one, where these decoupled U-statistics are replaced by the randomized decoupled U-statistics Ī_{n,k}^{ε}(f), defined in formula (8.2). This reduced problem can be studied by taking the conditional probability of the event whose probability is considered at the right-hand side of (8.6) with respect to the condition that all random variables ξ_{l}^{(j)}, 1 ≤ j ≤ k, 1 ≤ l ≤ n take a prescribed value. These conditional probabilities can be estimated by means of the multivariate version of the Hoeffding inequality, and then an adaptation of the method described in the previous section supplies the proof of Proposition 8.2. The proof is harder in this new case, but no new principal difficulty arises.

Lemma 7.2 was proved by means of a simple result formulated in Lemma 7.4 which enabled us to introduce the randomizing terms ε_{j}, 1 ≤ j ≤ n. In this result we have taken beside the original sequence ξ_{1}, …, ξ_{n} an independent copy ξ̄_{1}, …, ξ̄_{n}. In the next Lemma 8.4 I formulate a multivariate version of Lemma 7.4 which may help in the proof of Lemma 8.3. In its formulation I introduce beside the k independent copies ξ_{1}^{(j)}, …, ξ_{n}^{(j)}, 1 ≤ j ≤ k, of the original sequence of independent, identically distributed random variables ξ_{1}, …, ξ_{n} appearing in the definition of a decoupled U-statistic of order k another k independent copies ξ̄_{1}^{(j)}, …, ξ̄_{n}^{(j)}, 1 ≤ j ≤ k, of this sequence. Because of notational convenience I reindex them, and I shall deal in Lemma 8.4 with 2k independent copies ξ_{1}^{(j,1)}, …, ξ_{n}^{(j,1)} and ξ_{1}^{(j,−1)}, …, ξ_{n}^{(j,−1)}, 1 ≤ j ≤ k, of the original sequence ξ_{1}, …, ξ_{n}.

Now I formulate Lemma 8.4.

Lemma 8.4. Let us have a (non-empty) class of functions F of k variables f(x_{1}, …, x_{k}) on a measurable space (X^{k}, X^{k}) together with 2k independent copies ξ_{1}^{(j,1)}, …, ξ_{n}^{(j,1)} and ξ_{1}^{(j,−1)}, …, ξ_{n}^{(j,−1)}, 1 ≤ j ≤ k, of a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} on (X, X), and another sequence of independent random variables ε_{1}, …, ε_{n}, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, independent of all previously considered random sequences. Let us denote the class of sequences of length k consisting of ±1 digits by V_{k}, and let m(v) denote the number of digits −1 in a sequence v = (v(1), …, v(k)) ∈ V_{k}. Let us introduce, with the help of the above notations, the random variables Ĩ_{n,k}(f) and Ĩ_{n,k}(f, ε) as

Ĩ_{n,k}(f) = \frac{1}{k!} ∑_{v∈V_{k}}(−1)^{m(v)} ∑_{\begin{matrix}1≤l_{r}≤n, r=1,...,k \\ l_{r}≠l_{r′} if r≠r′ \end{matrix}} f (ξ_{l_{1}}^{(1,v(1))}, …, ξ_{l_{k}}^{(k,v(k))})  (8.7)

and

Ĩ_{n,k}(f, ε) = \frac{1}{k!} ∑_{v∈V_{k}}(−1)^{m(v)} ∑_{\begin{matrix}1≤l_{r}≤n, r=1,...,k \\ l_{r}≠l_{r′} if r≠r′ \end{matrix}} ε_{l_{1}} ⋯ ε_{l_{k}}f (ξ_{l_{1}}^{(1,v(1))}, …, ξ_{l_{k}}^{(k,v(k))}) (8.8)

for all f ∈ F. The joint distributions of the set of random variables {Ĩ_{n,k}(f); f ∈ F} and {Ĩ_{n,k}(f, ε); f ∈ F} defined in formulas (8.7) and (8.8) agree.

The proof of Lemma 8.4 can be found as Lemma 11.5 in [14]. Actually, this proof is not difficult. Let us observe that the inner sum in formula (8.7) is a decoupled Ustatistic, and in formula (8.8) a randomized decoupled U-statistic. (Actually they are multiplied by k!). In formulas (8.7) and (8.8) we took such a linear combination of these expressions which is similar to the formula appearing in the definition of Stieltjes measures.

Let us list the functions in the class of functions F in Lemma 8.3 in the form {f_{1}, f_{2}, … } = F, and introduce the quantities

Z_{p} = n^{−k/2} ∑_{\begin{matrix}1≤l_{r}≤n, r=1,...,k \\ l_{r}≠l_{r′} if r≠r′ \end{matrix}} f (ξ_{l_{1}}^{(1,1))}, …, ξ_{l_{k}}^{(k,1)}) , p = 1, 2, …,  (8.9)

and

Z̄_{p} = Z_{p} − n^{−k/2}Ĩ_{n,k}(f_{p}), p = 1, 2, …,  (8.10)

with the random variables Ĩ_{n,k}(f) introduced in (8.7). We would like to prove Lemma 8.3 with the help of Lemma 8.4. This can be done with the help of some calculations, but this require to overcome some very hard problems. We should bound a probability

of the form P ( sup_{1≤p<∞} Z_{p} > u) from above with the help of a probability of the form

P ( sup_{1≤p<∞}(Z_{p} − Z̄_{p}) > \frac{u}{2}) for all sufficiently large numbers u. We should provide such

an estimate for all not too large numbers u. The question arises how to prove such an estimate. This problem is the most difficult part of the proof.

In the case k = 1 considered in the previous section the analogous problem could be simply solved by means of a Symmetrization Lemma (Lemma 7.5). This Lemma cannot be applied in the present case, because it has an important condition, by which the sequences of random variables Z_{p}, p = 1, 2, …, and Z̄_{p}, p = 1, 2, …, should be independent. In the problem of Section 7 we could work with such sequences which satisfy this condition. On the other hand, the sequences Z_{p} and Z̄_{p}, p = 1, 2, …, defined in formulas (8.9) and (8.10) we have to work with now are not independent in the case k ≥ 2. They satisfy some weak sort of independence, and the problem is how to exploit this to get the estimates we need.

Let us first formulate such a version of the Symmetrization Lemma which can be applied also in the problem investigated now. This is done in the next Lemma 8.5.

Lemma 8.5 (Generalized version of the Symmetrization Lemma.) Let Z_{p} and Z̄_{p}, p = 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 Bmeasurable set B and two numbers α > 0 and β > 0 such that the random variables Z_{p}, p = 1, 2, …, are B measurable, and the inequality

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

holds. Then

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

(8.12)

The proof of Lemma 8.5 is contained together with its proof in [14] under the name Lemma 13.1, and the proof is not hard. It consists of a natural adaptation of the proof of the original Symmetrization Lemma, presented in Lemma 7.5. The hard problem is to check condition formula (8.11) if we try to apply Lemma 8.5. In our case we would like to apply it for the random variables Z_{p} and Z̄_{p}, p = 1, 2, …, defined in formulas (8.9) and (8.10) together with the σ-algebra B = B(ξ_{1}^{(j,1)}, …, ξ_{n}^{(j,1)}, 1 ≤ j ≤ k) generated by the random variables ξ_{1}^{(j,1)}, …, ξ_{n}^{(j,1)}, 1 ≤ j ≤ k. We would like to show that relation (8.11) holds with this choice on a set B of probability almost 1. (Let me emphasize that in (8.11) a set of inequalities must hold for all p = 1, 2, … simultaneously if ω ∈ B.)

In the analogous problem considered in Section 7 we had to check condition (7.7) with some appropriate constants α > 0 and β > 0 for the random variables Z̄_{p} p = 1, 2, …, defined in formula (7.8). This could be checked fairly simply by the calculation of the variance of the random variables Z̄_{p}, p = 1, 2, . . .. A natural adaptation of this approach is to bound from above the supremum sup_{1≤p<∞} E (Z̄_{p}^{2}|B) of the conditional

second moments of the random variables Z̄_{p}, 1 ≤ p < ∞, defined in (8.10) with respect to the σ-algebra B and to show that this expression is small with large probability. I have followed this approach in [11] and [14]. One can get the desired estimates, but many unpleasant technical details have to be overcome during the proof. I do not discuss here all details, I only briefly explain what kind of problems we meet when try to apply this method in the special case k = 2 and give some indications how we can overcome them.

In the case k = 2 the definition of Z̄_{p} is very similar to that of Ĩ_{n,2}(f_{p}) defined in (8.7) with the function f = f_{p}. The only difference is that in the definition of Z_{p} we have to take the values v = (1, −1), v = (−1, 1) and v = (−1, −1) in the outer sum, i.e. the term v = (1, 1) is dropped, and we multiply by (−1)^{m(v)+1} instead of (−1)^{m(v)}. We can get the desired estimate on the conditional supremum of second moments if we can prove a good estimate on the conditional second moments of the supremum of the inner sums in Ĩ_{n,2}(f_{p}), 1 ≤ p < ∞, in the case of each index v = (1, −1), v = (−1, 1) and v = (−1, −1). If we can get a good estimate in the case v = (1, −1), then we can get it in the remaining cases, too. So we have to give a good bound on the expression

sup_{1≤p<∞} E ( \frac{1}{n} (  ∑_{1≤l_{r}≤n, r=1,2, l_{1}≠l_{2}} f_{p} (ξ_{l_{1}}^{(1,1)}, ξ_{l_{2}}^{(2,−1)}))^{2}| B) .  (8.13)

Moreover, since the sequence of random variables ξ_{l}^{(2,−1)}, 1 ≤ l ≤ n, is independent of the σ-algebra B, and the canonical property of the functions f_{p} implies some orthogonalities, the estimation of the expression in (8.13) can be simplified. A detailed calculation shows that it is enough to prove the following inequality:

Let us have a countable class F of canonical functions f(x, y) with respect to a probability measure μ on the second power (X^{2}, X^{2}) of a measurable space (X, X), which is L_{2}-dense with some exponent L and parameter D, (the probability measure μ is living in the space (X, X)) together with a sequence of independent and μ-distributed random variables ξ_{1}, …, ξ_{n}, n ≥ 2, on (X, X), and let the relation

∫ f(x, y)^{2}μ( dx)μ( dy) ≤ σ^{2}, sup |f(x, y)| ≤ 1  for all f ∈ F  (8.14)

hold with some number 0 < σ^{2} ≤ 1 which satisfies the relation nσ^{2} ≥ K(L+β) log n with β = max (\frac{log D}{log n} , 0) and a sufficiently large fixed constant K > 0. Then the inequality

P (sup_{f∈F} \frac{1}{n} ∫ (∑_{l=1}^{n} f(ξ_{l}, y))^{2} μ( dy) ≥ A^{2}nσ^{4}) ≤ exp \{−A^{1/3}nσ^{2}\}  (8.15)

holds if A ≥ A_{0} with some sufficiently large fixed constant A_{0}.

Inequality (8.15) is similar to relation (7.3) in Proposition 7.1 in the case k = 1, but it does not follow from it. (It follows from (7.3) in the special case when the function f does not depend on the argument y with respect to which we integrate.) On the other hand, inequality (8.15) can be proved by working out a similar, although somewhat more complicated symmetrization argument and induction procedure as it was done in the proof of Proposition 7.1 in the case k = 1. After this, inequality (8.15) enables us to work out the symmetrization argument we need to prove Proposition 7.1 for k = 2. This procedure can be continued for all k = 2, 3, . . .. If we have already proved Proposition 7.1 for some k, then an inequality can be formulated and proved with the help of the already known results which enable us to carry out that symmetrization procedure which is needed in the proof of Proposition 7.1 in the case k + 1. This is a rather cumbersome method with a lot of technical details, hence its detailed explanation had to be omitted from an overview paper. In the work [14] Sections 13, 14 and 15 deal only with the proof of Proposition 7.1. Section 13 contains the proof of some preparatory results and the formulation of the inductive statements we have to prove to get the result of Proposition 7.1, Section 14 contains the proof of the Symmetrization arguments we need, and finally the proof is completed with their help in Section 15.

There is an interesting theory of Talagrand about so-called concentration inequalities. This theory has some relation to the questions discussed in this paper. In the last section this relation will be discussed together with some open problems.

9. Relation with other results and some open problems

Talagrand worked out a deep theory about so-called concentration inequalities. (See his overview in paper [19] about this subject.) His results are closely related to the supremum estimates described in this paper. First I discuss this relation.

On Talagrand’s concentration inequalities.

Talagrand considered a sequence of independent random variables ξ_{1}, …, ξ_{n}, a class of

functions F, took the partial sums ∑_{j=1}^{n} f(ξ_{j}) for all functions f ∈ F, and investigated

their supremum. He proved such estimates which state that this supremum is very close to its expected value, (it is concentrated around it). The following theorem is a typical result in this direction.

Theorem 9.1. (Theorem of Talagrand.) Consider n independent and identically distributed random variables ξ_{1}, …, ξ_{n} with values in some measurable space (X, X). Let F be some countable family of real-valued measurable functions of (X, X) such that

∥f∥_{∞} ≤ b < ∞ for every f ∈ F. Let Z = sup_{f∈F} ∑_{i=1}^{n} f(ξ_{i}) and v = E(sup_{f∈F} ∑_{i=1}^{n} f^{2}(ξ_{i})).

Then for every positive number x,

P (Z ≥ EZ + x) ≤ K exp \{−\frac{1}{K′} \frac{x}{b} log (1 + \frac{xb}{v})\}  (9.1)

and

P (Z ≥ EZ + x) ≤ K exp \{−\frac{x^{2}}{2(c_{1}v + c_{2}bx)}\} ,  (9.2)

where K, K′, c_{1} and c_{2} are universal positive constants. Moreover, the same inequalities hold when replacing Z by −Z.

Inequality (9.1) can be considered as a generalization of Bennett’s inequality, inequality (9.2) as a generalization of Bernstein’s inequality. In these estimates the distribution of the supremum of possibly infinitely many partial sums of independent and identically distributed functions are considered. A remarkable feature of Theorem 9.1 is that it imposes no condition about the structure of the class of functions F. In this respect it differs from Theorems 6.2 and 6.3 in this paper, where such a class of functions F is considered which satisfies a so-called L_{2}-density property.

Talagrand’s study was also continued by other authors, who got interesting results. In particular, the works of M. Ledoux [8] and P. Massart [17] are worth mentioning. In these works the above mentioned result was improved. Such a version was proved which also holds for the supremum of appropriate classes of sums of independent but not necessarily identically distributed random variables. (On the other hand, I do not know of such a generalization in which U-statistics of higher order are considered.) Beside this,

there are such improvements of Theorem 9.1 in which the quantity v = E(sup_{f∈F} ∑_{i=1}^{n} f^{2}(ξ_{i})) is replaced by σ^{2} = sup_{f∈F} ∑_{i=1}^{n} Var (f(ξ_{i})), i.e. the supremum of the expectation of the indi-

vidual partial sums ∑_{i=1}^{n} f^{2}(ξ_{i}) is considered (the statement that σ^{2} equals the supremum

of the expected values of the partial sums ∑_{i=1}^{n} f^{2}(ξ_{i}) holds if Ef(ξ_{i}) = 0 for all random

variables ξ_{i} and functions f) instead of the second moment of the supremum of these partial sums.

On the other hand, the estimates in Theorem 9.1 contain the expected value EZ =

E (sup_{f∈F} ∑_{i=1}^{n} f(ξ_{i})), and this quantity appears in all concentration type inequalities. This

fact has deep consequences which deserve a more detailed discussion.

Let us consider Theorem 9.1 or one of its improvements and try to understand what kind of solution they provide for problem b) or b′) formulated in Section 1 in the case k = 1. They supply a good estimate on the probabilities we consider for the

numbers u ≥ n^{−1/2}EZ = n^{−1/2}E(sup_{f∈F} ∑_{i=1}^{n} f(ξ_{i})). But to apply these results we need a

good estimate on the expectation EZ of the supremum of the partial sums we consider, and the proof of such an estimate is a highly non-trivial problem.

Let us consider problem b′) (in the case k = 1) for such a class of functions F which satisfies the conditions of Theorem 6.3. The considerations taken in Section 6 show that there are such classes of functions F which satisfy the conditions of Theorem 6.3,

and for which the probability P (sup_{f∈F} n^{−1/2} ∑_{i=1}^{n} f(ξ_{i}) > ασ log \frac{2}{σ}) is almost 1 with an

appropriate small number α > 0 for all large enough sample sizes n. (Here the number σ is the same as in Theorem 6.3.) This means that En^{−1/2}Z ≥ α − ε for all ε > 0 if the sample size n of the sequence ξ_{1}, …, ξ_{n} is greater than n_{0} = n_{0}(ε, σ). Some calculation also shows that under the conditions of Theorem 6.3 En^{−1/2}Z ≤ Kσ log \frac{2}{σ} with an appropriate number K > 0. (In this calculation some difficulty may arise, because Theorem 6.3 for k = 1 does not yield a good estimate if u ≥ \sqrt{n}σ^{2}. But

we can write P (sup_{f∈F} n^{−1/2} ∑_{i=1}^{n} f(ξ_{i}) > u) ≤ e^{−α(u/σ̄)^{2}} = e^{−αu\sqrt{n}} with σ̄^{2} = un^{−1/2} if

u ≥ \sqrt{n}σ^{2}, and this estimate is sufficient for us. We get the upper bound we formulated for n^{−1/2}EZ from Theorem 6.3 only under the condition nσ^{2} ≥ const. log \frac{2}{σ} with some appropriate constant. It can be seen that this condition is really needed, it appeared not because of the weakness of our method. I omit the details of the calculation.) Then the concentration inequality Theorem 9.1, or more precisely its improvement, Theorem 3 in paper [17] which gives a similar inequality, but with the quantity σ^{2} instead of v implies Theorem 6.3 in the case k = 1. This means that Theorem 6.3 can be deduced from concentration type inequalities in the case k = 1 if we can show that under its conditions En^{−1/2}Z ≤ Kσ log \frac{2}{σ} with some appropriate K > 0 depending only on the exponent and parameter of the L_{2}-dense class F. Such a proof can be made (see [6] on the basis of paper [19]), but it requires rather long and non-trivial considerations. I prefer a direct proof of Theorem 6.3.

Finally I discuss the question about some natural generalization of the problems considered in this work.

Some natural generalizations of the problem discussed in this paper

Problems a), b) and a′), b′) in the case k ≥ 2 can be considered as a natural generalization of some questions about the behaviour of sums of independent and identically distributed random variables to the multivariate case. It seems natural to consider the sum of independent, but not necessarily identically distributed random variables, and to investigate the natural multivariate generalization of the results describing their behaviour. The first step of such a program would be the formulation of the generalization of problem a′) in this direction. I shall discuss this problem.

First we have to define the natural generalization of U-statistics, which can be considered as the multivariate version of sums of independent, but not necessarily identically distributed random variables. We also have to clarify when such generalized Ustatistics can be considered as degenerate U-statistics. The following definition seems to be natural.

Let us consider a sequence of independent, but not necessarily identically distributed random variables ξ_{1}, …, ξ_{n} and a set of functions

f = {f_{l_{1},...,l_{k}}(x_{1}, …, x_{k}), 1 ≤ l_{j} ≤ n, 1 ≤ j ≤ k, and l_{j} ≠ l_{j′} if j ≠ j′}

on the k-fold product (X^{k}, X^{k}) of a measurable space (X, X). This set of functions f will be considered as the class of kernel functions of the generalized U-statistic of order k defined as

I_{n,k}(f) = ∑_{\begin{matrix}1≤l_{j}≤n, 1≤j≤k \\ l_{j}≠l_{j′} if j≠j′ \end{matrix}} f_{l_{1},...,l_{k}}(ξ_{l_{1}}, …, ξ_{l_{k}}).  (9.3)

We call the generalized U-statistic I_{n,k}(f) of order k degenerate if for all sets of indices (l_{1}, …, l_{k}) in the sum (9.3) and for all 1 ≤ j ≤ k

E(f_{l_{1},...,l_{k}}(ξ_{l_{1}}, …, ξ_{l_{k}})|ξ_{l_{s}}, s ∈ {1 …, k} \ {j}) = 0 with probability 1.  (9.4)

With the help of the above notations the following generalized version of problem a′) can be formulated.

Generalized version of problem a′). Let us consider a generalized degenerate Ustatistic I_{n,k}(f) determined by a sequence of independent random variables ξ_{1}, …, ξ_{n} and a class of kernel functions f = {f_{l_{1},...,l_{k}}(x_{1}, …, x_{k})}. Let us give a good estimate on the probabilities

P (|I_{n,k}(f)| > u) for all u > 0.  (9.5)

One would like to get such an estimate on the probability in formula (9.5) which contains the result of Theorem 4.3 as a special case. It may be expected that the method of Theorem 4.3 can be adapted to the investigation of this more general problem.

It may be worth mentioning that the method of Hoeffding’s decomposition can be adapted to the case of generalized U-statistics, and the diagram formula about the expression of the product of degenerate U-statistics in the form of a sum of degenerate U-statistics can also be generalized to generalized U-statistics, although the result has a more complicated form in this case. This means that the basic tools of the proof of Theorem 4.3 can be applied also in the study of this problem.

Nevertheless, there remains the question how to find the right form of the estimate of the probability in formula (9.5). This seems to be a non-trivial question. It is possible that this is the hardest part of the problem. I make some comments about it.

It is natural to expect that generalized degenerate U-statistics I_{n,k}(f) of order k (without normalization) satisfy the inequality

P (|I_{n,k}(f)| > u) < A exp \{−C (\frac{u}{V_{n}} )^{2/k}\}  (9.6)

with some universal constants A = A(k) > 0 and C = C(k) > 0 in a relatively large interval for the parameter u, where V_{n}^{2} denotes the variance of I_{n,k}(f). An essential problem is to find a relatively good constant C and to determine that interval 0 < u < D_{n}, where the estimate (9.6) should hold. Theorem 4.3 states that in the case of classical degenerate U-statistics inequality (9.6) holds in the interval [0, D_{n}] with D_{n} = const. n^{k}σ^{k+1}, where σ^{2} = Ef(ξ_{1}, …, ξ_{k})^{2}. In the special case k = 1 D_{n} = const. n^{k}σ^{k+1} = const. nσ^{2} = const. V_{n}^{2}. Beside this, generalized U-statistics of order k = 1 satisfy inequality (9.6) in the interval [0, D_{n}] = [0, const. V_{n}^{2}] with appropriate constants A > 0 and C > 0 by Bernstein’s inequality (Theorem 2.2). We have to understand what is the right choice of D_{n} in the case of generalized degenerate U-statistics of order k ≥ 2. In the case of classical degenerate U-statistics it is D_{n} = const. n^{k}σ^{k+1}, but it is not clear what corresponds to this quantity in the case of generalized degenerate U-statistics. (The variance of a degenerate U-statistic of order k is of order n^{k}σ^{2}.) The clarification of this question seems to be the most important point in the solution of the generalized version of problem a′).

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.) de la Peña, V. H. and Montgomery–Smith, S. (1995) Decoupling inequalities for

the tail-probabilities of multivariate U-statistics. Ann. Probab., 23, 806–816 4.) Dudley, R. M. (1998) Uniform Central Limit Theorems. Cambridge University

Press, Cambridge U.K. 5.) Dynkin, E. B. and Mandelbaum, A. (1983) Symmetric statistics, Poisson processes

and multiple Wiener integrals. Annals of Statistics 11, 739–745 6.) Giné, E. and Guillou, A. (2001) On consistency of kernel density estimators for

randomly censored data: Rates holding uniformly over adaptive intervals. Ann. Inst. Henri Poincaré PR 37 503–522

7.) Itô K. (1951) Multiple Wiener integral. J. Math. Soc. Japan 3. 157–164 8.) Ledoux, M. (1996) Talagrand deviation inequalities for product measures. ESAIM:

Probab. Statist. 1. 63–87. Available at http://www.emath./fr/ps/. 9.) Major, P. (1981) Multiple Wiener–Itô integrals. Lecture Notes in Mathematics

849, Springer Verlag, Berlin, Heidelberg, New York, 10.) Major, P. (2005) An estimate about multiple stochastic integrals with respect to a

normalized empirical measure. Submitted to Studia Scientarum Mathematicarum Hungarica.

11.) Major, P. (2005) An estimate on the maximum of a nice class of stochastic integrals.

Submitted to Probability Theory and Related Fields, 12.) Major, P. (2005) On a multivariate version of Bernstein’s inequality submitted to

Ann. Probab. 13.) Major, P. (2005) A multivariate generalization of Hoeffding’s inequality. Submitted

to Ann. Probab. 14.) Major, P. (2005) On the tail behaviour of multiple random integrals and degenerate

U-statistics. (manuscript for a future Lecture Note) 15.) Major, P. and Rejtő, L. (1988) Strong embedding of the distribution function under

random censorship. Annals of Statistics, 16, 1113–1132 16.) 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 17.) Massart, P. (2000) About the constants in Talagrand’s concentration inequalities

for empirical processes. Ann. Probab. 28, 863–884 18.) Pollard, D. (1984) Convergence of Stochastic Processes. Springer Verlag, New York 19.) Talagrand, M. (1994) Sharper bounds for Gaussian and empirical processes. Ann.

Probab. 22, 28–76 20.) Talagrand, M. (1996) New concentration inequalities in product spaces. Invent.

Math. 126, 505–563