ESTIMATION OF MULTIPLE RANDOM INTEGRALS

AND U-STATISTICS. Péter Major Alfréd Rényi Alfréd Mathematical Institute of the Hungarian Academy of Sciences

Here I give a short survey about some problems on multiple random integrals and U-statistics together with some other questions which occur during their study in a natural way. I write down the main results, discuss their background together with some pictures and mathematical ideas which explain them better.

1. Introduction. Formulation of the problems.

To formulate the problems first I introduce some notations. Let ξ_{1}, …, ξ_{n} be a sequence of independent and identically distributed random variables with some probability distribution μ on a measurable space (X, X) and let μ_{n},

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

denote its empirical distribution. Let a measurable function f(x_{1}, …, x_{k}) of kvariables be given on the product space (X^{k}, X^{k}). Take the k-fold direct product of the normalized version \sqrt{n}(μ_{n} − μ) of this empirical measure μ_{n} and consider the integral of the function f with respect to it. More explicitly, the (random) 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.1)

will be considered.

The following two problems will be studied in this note:

Problem A). Give a good estimate on the probabilities P (J_{n,k}(f) > u) under appropriate conditions on the function f.

(The omission of the diagonals x_{j} = x_{l}, j ≠ l, from the domain of integration turned out to be natural in possible applications.) The second, more general problem is the following one.

Problem B). Let a nice class F of functions f(x_{1}, …, x_{k}) be given on the space

(X^{k}, X^{k}). Give a good estimate on the probabilities P (sup_{f∈F} J_{n,k}(f) > u),

where J_{n,k}(f) denotes the integral of the function f defined in formula (1.1).

It turned out useful to study these two problems together with their U-statistic analogues. To formulate them first I recall the definition of U-statistics.

The definition of U-statistics. Let a sequence ξ_{1}, …, ξ_{n} of independent and identically distributed random variables be given with values in some measurable space (X, X) together with a function f(x_{1}, …, x_{k}) on the k-fold product space (X^{k}, X^{k}) with some k ≤ n. 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.2)

is called a U-statistic of order k with kernel function f.

I formulated the following versions of the above two problems.

Problem A′). Give a good estimate on the probabilities P (n^{−k/2}I_{n,k}(f) > u) under appropriate conditions on the function f.

Problem B′). Let a nice class F of functions f(x_{1}, …, x_{k}) be given on a (product) space (X^{k}, X^{k}) together with a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} with values in (X, X). Give a good es-

timate on the probabilities P (sup_{f∈F} n^{−k/2}I_{n,k}(f) > u), where I_{n,k}(f) denotes

the U-statistic of order k with kernel function f defined in formula (1.2).

It may be useful to remark that a U-statistic of order k with the kernel function f can be rewritten as

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

where μ_{n} is the empirical distribution of the sequence ξ_{1}, …, ξ_{n}. This shows that the essential difference between the random integrals introduced in formula (1.1) and the U-statistics is that in the random integrals J_{n,k}(f) integration is taken with respect to the ‘normalized’ measures μ_{n} − μ, while in the integral representation of the U-statistics I_{n,k}(f) with respect to the ‘non-normalized’ measures μ_{n}.

I met the above problems when tried to adapt a simple method applied in the study of the asymptotic behaviour of maximum likelihood estimates to the investigation of harder problems. In the study of maximum likelihood estimates the root of the so-called maximum likelihood equation has to be well estimated. This can be done by means of a good approximation of the function in the maximum likelihood equation which is obtained with the help of its Taylor expansion if the high order terms of this expansion are omitted. It has to be shown that such an approximation causes only a negligibly small error. But this can be proved relatively simply.

I tried to apply a similar method in the study of some so-called non-parametric maximum likelihood estimation problems. Such a problem arises for instance if we want to estimate an unknown distribution function by means of some partial information. In the study of the error of such an estimate in a fixed point a version of the Taylor expansion can be applied together with the omission of the higher order terms. But in this case it is much harder to show that such an approximation causes only a negligibly small error. To prove this a good solution of Problem A is needed. If we want to bound the error of the estimation in all points simultaneously, then we need a good solution of Problem B.

In the investigation of general non-parametric estimation problems several additional difficulties have to be overcome, but the solution of Problems A and B is especially important. Beside this, these problems are related to a better understanding of some fundamental probabilistic phenomena. Hence I found useful a detailed study of the above questions.

2. An overview of the problems. The study of the one-variate case.

Before a detailed discussion it is worth thinking over what kind of results can be expected. Let us observe that the normalized signed measures \sqrt{n}(μ_{n} − μ) converge to a Gaussian field as n → ∞. Hence it is natural to expect that under very general conditions such results hold both in the solution of Problem A and Problem B which their Gaussian counterparts suggest. But we have to understand the answer to the following two questions.

1.) What kind of estimates do the Gaussian counterparts of these problems sug-

gest? 2.) What does the expression ‘under very general conditions’ mean?

To clarify the above questions it is useful to study first Problem A in the case k = 1 when the distribution of sums of independent random variables has to be bounded. Such a bound is given in the following classical result called Bernstein’s inequality.

Bernstein’s inequality. Let ξ_{1}, …, ξ_{n} be independent random variables which satisfy the relations P (|ξ_{j}| ≤ 1) = 1 and Eξ_{j} = 0, 1 ≤ j ≤ n. Let us introduce

the notation σ_{j}^{2} = Eξ_{j}^{2}, 1 ≤ j ≤ n, S_{n} = ∑_{j=1}^{n} ξ_{j} and V_{n}^{2} = Var S_{n} = ∑_{j=1}^{n} σ_{j}^{2}. The

inequality

P (S_{n} > u) ≤ exp \{−\frac{u^{2}}{2V_{n}^{2} (1 + \frac{u}{3V_{n}^{2}} )}\}  (2.1)

holds for all numbers u > 0.

Bernstein’s inequality yields an estimate on the distribution of sums of independent random variables suggested by the central limit theorem, although the coefficient 1 + \frac{u}{3V_{n}^{2}} in the denominator of the upper bound slightly modifies the picture. In the next remark the effect of this factor is considered in different cases.

a) If u ≤ εV_{n}^{2} with some small number ε > 0, then P (S_{n} > u) ≤ e^{−(1−ε)u^{2}/2V_{n}^{2}}. This is almost such a good estimate as the estimate obtained by a formal application of the central limit theorem.

b) If u ≤ 3V_{n}^{2}, then P (S_{n} > u) ≤ e^{−const. u^{2}/2V_{n}^{2}}. This is a bound similar to that suggested by the central limit theorem, only it has a worse constant in the exponent.

c) If u ≫ V_{n}^{2}, then

P (S_{n} > u) ≤ e^{−u}.  (2.2)

This is a very bad bound. In particular, it does not depend on the variance of the sum.

The question arises whether Bernstein’s inequality can be improved in the ‘bad case’ u ≫ V_{n}^{2}. To this question a positive answer can be given. Bennett’s inequality formulated below yields a slight improvement of Bernstein’s inequality in this case.

Bennett’s inequality. Let ξ_{1}, …, ξ_{n} be a sequence of independent random variables which satisfy the relations P (|ξ_{j}| ≤ 1) = 1 and EX_{j} = 0, 1 ≤ j ≤ n. Put

σ_{j}^{2} = Eξ_{j}^{2}, 1 ≤ j ≤ n, S_{n} = ∑_{j=1}^{n} ξ_{j} and V_{n}^{2} = Var S_{n} = ∑_{j=1}^{n} σ_{j}^{2}. Then the inequality

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}} ]\}

holds for all numbers u > 0.

Hence there exists a constant B = B(ε) > 0 for all ε > 0 such that

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

and there exists a number K > 0 such that

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

Formula (2.3) yields a slight improvement of formula (2.2), but even this bound is very far from the estimate suggested by the central limit theorem. On the other hand, as the next example shows, this estimate cannot be improved.

Lower bound for the distribution of sums of independent random variables in an appropriate example. Let us fix a positive integer n together with two positive numbers u and σ^{2} which satisfy the relations 0 < σ^{2} ≤ \frac{1}{8}, n > 3u ≥ 6 and u > 3nσ^{2}. Let us introduce the quantity V_{n}^{2} = nσ^{2}, and consider a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} such that

P (ξ_{j} = 1) = P (ξ_{j} = −1) = \frac{σ^{2}}{2} and P (ξ_{j} = 0) = 1 − σ^{2}. Put S_{n} = ∑_{j=1}^{n} ξ_{j}. In this

example ES_{n} = 0, Var S_{n} = V_{n}^{2}, and

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

with some appropriate number K > 0.

In formula (2.4) that probability is bounded from below in a special case which is bounded from above in (2.3). These two estimates are very similar. The only difference between them is that they may contain a different constant K > 0. The above results can be summarized in the following way.

For small numbers u > 0 the probability P (S_{n} > u) satisfies a good estimate suggested by the central limit theorem. Such a situation holds if u ≤ εV_{n}^{2}. This probability satisfies a slightly weaker estimate for not too large numbers u (if εV_{n}^{2} ≤ u ≤ CV_{n}^{2} with some fixed number C > 0), and it satisfies only very weak estimates for large numbers u (if u ≫ V_{n}^{2}).

3. Some results useful in the study of the general case.

In the solution of Problem A) in the general case k ≥ 1 similar results hold as in the special case k = 1 discussed before. To understand their similarity better it is useful to study first the following two questions.

Question 1. In the case k = 1 the sum of independent random variables with zero expectation was considered. What kind of normalization corresponds to this zero expectation in the case k ≥ 2?

Question 2. In the case k = 1 the central limit theorem and the behaviour of the normal distribution function were in the background of the estimates. What kind of limit theorem and estimation do take their part in the case k ≥ 2?

Discussion of the first question.

It is useful to consider first the second moment of the expressions we are investigating. In the case k = 1 independent random variables of expectation zero are summed up. In this case the identity

Var (∑_{k=1}^{n} ξ_{k}) = ∑_{k=1}^{n} Var ξ_{k},

holds because of the identity Eξ_{i}ξ_{j} = 0 for all pairs i ≠ j.

The multivariate version of this identity (in the case of U-statistics) would be the identity

I_{n,k}(f) = Var (\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}}))

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

This identity holds if

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

for all pairs of k-tuples such that {j_{1}, …, j_{k}} ≠ {j′_{1}, …, j′_{k}}. The above relation holds for the degenerate U-statistics introduced below.

Definition of degenerate U-statistics. Take a U-statistic I_{n,k}(f) determined by a sequence of independent and identically distributed random variables ξ_{1}, …, ξ_{n} with distribution μ and a kernel function f(x_{1}, …, x_{k}). This U-statistic is degenerate if

E(f(ξ_{1}, …, ξ_{k})|ξ_{1} = x_{1}, …, ξ_{j−1} = x_{j−1}, ξ_{j+1} = x_{j+1}, …, ξ_{k} = x_{k}) = 0 for all indices 1 ≤ j ≤ k and values x_{s} ∈ X, s ∈ {1, …, k} \ {j}.

A U-statistic is degenerate if its kernel function is canonical, i.e. it satisfies the following property.

Definition of canonical functions. A function f(x_{1}, …, x_{k}) defined on the k-fold direct product (X^{k}, X^{k}) is canonical with respect to a probability measure μ on the space (X, X) if

∫ f(x_{1}, …, x_{j−1}, u, x_{j+1}, …, x_{k})μ( du) = 0

for all indices 1 ≤ j ≤ k and values x_{s} ∈ X, s ∈ {1, …, k} \ {j}.

The notion of degenerate U-statistics is useful, because in some sense such U-statistics behave so as sums of independent random variables with expectation zero. Beside this, the study of general U-statistics can be reduced to the study of degenerate U-statistics by means of the following Hoeffding-decomposition.

Hoeffding decomposition of general U-statistics. All U-statistics I_{n,k}(f) of order k can be written in the form of a linear combination

I_{n,k}(f) = ∑_{j=0}^{k} n^{k−j}I_{n,j}(f_{j})  (3.1)

of degenerate U-statistics I_{n,j}(f_{j}). The (canonical) kernel functions f_{j} (of j variables) of the degenerate U-statistics I_{n,j}(f_{j}), 0 ≤ j ≤ k, can be calculated explicitly. It can be shown that they satisfy the inequality

∫ f_{j}^{2}(x_{1}, …, x_{j})μ( dx_{1}) … μ( dx_{j}) ≤ ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k})

for all indices 0 ≤ j ≤ k.

The problems about the behaviour of the multiple random integrals J_{n,k}(f) defined in formula (1.1) can also be reduced to problems about the behaviour of degenerate U-statistics by means of their appropriate decomposition. Such expressions can be written as the linear combination

J_{n,k}(f) = ∑_{j=0}^{k} c(n, j)n^{−j/2}I_{n,j}(f_{j})  (3.2)

of degenerate U-statistics with the same kernel functions f_{j} which appear in formula (3.1) and with some appropriate coefficients c(n, j) such that c(n, j) < K(j) with some universal constant K(j). This has the consequence that while in typical cases the terms with small index j (with index j = 1, if Ef(ξ_{1}, …, ξ_{k}) = 0) are the dominating terms in the Hoeffding expansion (3.1) of a U-statistic, all terms have the same order of magnitude in the expansion (3.2) of a multiple random integral J_{n,k}(f).

In the definition of the random integral J_{n,k}(f) integration is taken with respect to the signed measure μ_{n} − μ, and this ‘normalization’ diminishes the value of the integral. This diminishing effect is reflected in the relatively small value of the coefficients c(n, j)n^{−j/2} in formula (3.2).

Discussion of the second problem.

The previous results suggest that in the study of U-statistics and multiple random integrals the limit distributions of appropriately normalized degenerate U-statistics take the role of normal distributions. The limit theorems about degenerate Ustatistics are known, and they can be formulated by means of multiple Wiener-Itô integrals with respect to a white noise. To formulate them first I recall the definition of white noise.

The notion of white noise. Let a measure μ be given on some measurable space (X, X). A system of jointly Gaussian random variables indexed by the measurable sets A ⊂ X such that μ(A) < ∞ is a white noise with reference measure μ if

Eμ_{W} (A)μ_{W} (B) = μ(A ∩ B) and Eμ_{W} (A) = 0

for all measurable sets A, B ⊂ X such that μ(A) < ∞ and μ(B) < ∞.

If a white noise μ_{W} is given with some reference measure μ together with a function f(x_{1}, …, x_{k}) square integrable with respect to the k-fold product μ^{k} of the measure μ, then the k-fold Wiener–Itô integral

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

of this function f with respect to the white noise μ_{W} can be defined in a natural way. (First this integral is defined for simple so-called step functions which take a constant value on finitely many rectangles, and disappear outside them. Then the integral can be extended to general functions by means of an appropriate L_{2}-isomorphism.)

The following result holds.

Limit distribution theorem for degenerate U-statistics. Let us consider such a sequence I_{n,k}(f), n = k, k + 1, …, of degenerate U-statistics which is determined by a sequence of independent and identically distributed random variables ξ_{1}, ξ_{2}, …, on a measurable space (X, X) with distribution μ and a (canonical) function f(x_{1}, …, x_{k}) square integrable with respect to the measure μ^{k}. The normalized degenerate U-statistics n^{−k/2}I_{n,k}(f) converge in distribution to the k-fold Wiener–Itô integral

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

of the function f with respect to a white noise μ_{W} with the reference measure μ which agrees with the distribution of the random variables ξ_{j} as n → ∞.

A heuristic explanation of the previous result.

If I_{n,k}(f) is a degenerate U-statistics, then the identity

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

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

holds, where μ_{n} denotes the empirical distribution of the sequence ξ_{1}, …, ξ_{n}. Beside this, the normalized empirical distributions \sqrt{n}(μ_{n}(·) − μ(·)) have a Gaussian limit as n → ∞. This suggests a limiting procedure, and as more detailed considerations show (see e.g. [1]) the normalized empirical measures \sqrt{n}(μ_{n}(·) − μ(·)) can be replaced by the white noise μ_{W} (·) in the limit process. The proof consists of the justification of this heuristic argument.

It is natural to extend the problems formulated in the introduction with their appropriate counterpart about Wiener–Itô integrals. Their solution indicates what kind of results can be expected in the original problems.

Let us consider the Wiener–Itô integral Z_{μ,k}(f) of a function f(x_{1}, …, x_{k}) of k variables with respect to a white noise μ_{W} with reference measure μ introduced in formula (3.3) and study the following problems.

Problem A′′). Let us give a good estimate on the probability P (Z_{μ,k}(f) > u) for all numbers u > 0.

Problem B′′). Let a nice class F of functions f(x_{1}, …, x_{k}) of k variables be given. Take the Wiener–Itô integral Z_{μ,k}(f) of all functions f ∈ F with respect to a white noise μ_{W}. Give a good estimate on the distribution of the supremum of these random integrals, i.e. on the probability

P (sup_{f∈F} Z_{μ,k}(f) > u) for all numbers u > 0.

4. Results about the distribution of random integrals and U-statistics.

It is worth considering first Problem A′′) about the estimation of Wiener–Itô integrals. I present a result in this direction.

Estimation about the tail distribution of Wiener–Itô integrals. Let a white noise μ_{W} be given with reference measure μ together with a function f(x_{1}, …, x_{k}) of k variables on a measurable space (X, X) such that

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

with some number σ^{2} < ∞. The Wiener–Itô integral

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

introduced in formula (3.3) satisfies the inequality

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

for all numbers u > 0 with some constant C = C(k) > 0 depending only on the multiplicity k of the integral.

The next example shows that the above estimate is sharp.

Lower bound on the tail distribution of a special Wiener–Itô integral. Let a σ-finite measure μ be given on a measurable space (X, X) together with a white noise μ_{W} on (X, X) with this reference measure μ. Let f_{0}(x) be a real valued function on the space (X, X) such that ∫ f_{0}(x)^{2}μ( dx) = 1. Let us introduce the function f(x_{1}, …, x_{k}) = σf_{0}(x_{1}) ⋯ f_{0}(x_{k}) with some number σ > 0, and consider the Wiener–Itô integral Z_{μ,k}(f) introduced in formula (3.3). Then the identity

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

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

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

for all numbers u > 0 with some appropriate constant C̄ > 0.

The integral σ^{2} = ∫ f(x_{1}, …, x_{k})^{2} μ( dx_{1}) … μ( dx_{k}) in the above results agrees with the variance of the random integral (k!)^{−1/2}Z_{μ,k}(f). Hence these results can be interpreted so that

P (Z_{k,μ}(f) > u) ≤ const. P (ση^{k} > u)

for all numbers u > 0, where η is a standard normal random variable, and σ^{2} = (k!)^{−1/2}EZ_{μ,k}(f)^{2}. Furthermore, this estimate is sharp. This sharpness means that if we have no more information about the kernel function f than its L_{2} norm, i.e. the variance of the Wiener–Itô integral determined by it, then we cannot get a better estimate, than the above formulated inequality. On the other hand, in some special cases a considerably better estimate can be proved under some appropriate additional information about the behaviour of the kernel function f. But this question, which does not appear in the statistical problems which gave the motivation for the study of the problems considered in this note will be not discussed here.

Similar, but slightly weaker estimates hold for degenerate U-statistics and multiple random integrals with respect to normalized empirical distributions.

Estimate on the tail distribution of degenerate U-statistics. Let ξ_{1}, …, ξ_{n} be a sequence of independent and identically distributed random variables on a measurable space (X, X) with distribution μ. Take 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.1)
∥f∥_{2}^{2} = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) ≤ σ^{2}  (4.2)

with some number 0 < σ^{2} ≤ 1, and consider the (degenerate) U-statistic defined in formula (1.2) with the help of these quantities. Then there exist some constants A = A(k) > 0 and B = B(k) > 0 depending only on the order k of the U-statistic such that the inequality

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

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

The above estimate can be considered as a multivariate generalization of Bernstein’s inequality. For multiple integrals with respect to normalized empirical distributions the following similar estimate holds.

Estimate about the tail distribution of random integrals with respect to normalized empirical distributions. Let a sequence ξ_{1}, …, ξ_{n} of independent and identically distributed random variables be given with distribution μ which take their values in a measurable space (X, X) together with a function f(x_{1}, …, x_{k}) on the k-fold product space (X^{k}, X^{k}) which satisfy relations (4.1) and (4.2) with some constant 0 < σ ≤ 1. Then there exist some constants C = C_{k} > 0 and α = α_{k} > 0 depending only on the multiplicity k of the integral J_{n,k}(f) defined in formula (1.1) such that the inequality

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

holds.

In the case k = 1 we have seen that the tail distribution P (n^{−1/2}S_{n} > u) of the normalized sum n^{−1/2}S_{n} of n independent, identically distributed, bounded random variables with expectation zero satisfies only a very weak estimate if u ≫ n^{1/2}σ^{2}, an estimate which is very far from the bound suggested by the central limit theorem.

Similarly, in the case k ≥ 2 the tail distribution P (k!n^{−k/2}I_{n,k}(f) > u) of degenerate U-statistics satisfies a much weaker estimate than the bound suggested by the behaviour of Wiener–Itô integrals if u ≫ n^{k/2}σ^{k+1}. This means that the previous estimates about the tail distribution of degenerate U-statistics and integrals with respect to normalized empirical distributions are sharp also in that sense that they give the domain where the sharp estimate suggested by the behaviour of Wiener–Itô integrals holds.

For the sake of completeness I present such a degenerate U-statistic in the case k = 2 whose tail-distribution satisfies only a much weaker estimate than formula (4.3) if u ≫ nσ^{3}.

Lower bound for the tail distribution of a special degenerate U-statistic in the case k = 2. Let ξ_{1}, …, ξ_{n} be a sequence of independent, identically distributed random variables with values on the two-dimensional Euclidean space. Let ξ_{j} = (η_{j,1}, η_{j,2}), 1 ≤ j ≤ n, where η_{j,1} and η_{j,2} are independent random variables, P (η_{j,1} = 1) = P (η_{j,1} = −1) = \frac{σ^{2}}{8} , and P (η_{j,1} = 0) = 1 − \frac{σ^{2}}{4} , P (η_{j,2} = 1) = P (η_{j,2} = −1) = \frac{1}{2} for all indices 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}, and define the U-statistic of order 2

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

with this kernel function f and the independent random variables ξ_{1}, …, ξ_{n}. The expression I_{n,2}(f) is a degenerate U-statistic. Furthermore, if u ≥ B_{1}nσ^{3} with some appropriate constant B_{1} > 0, B_{2}^{−1}n ≥ u ≥ B_{2}n^{−2} with some sufficiently large number B_{2} > 0, and \frac{1}{n} ≤ σ ≤ 1, then the inequality

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

= exp \{−B \frac{u}{σ} (\frac{nσ^{3}}{u} )^{1/3} log (\frac{u}{nσ^{3}} )\}

holds with some constant B > 0, which depends neither on the number n nor on the parameter σ.

5. A brief explanation of the results.

It is worth showing that the high even order moments EI_{n,k}(f)^{2M} of a degenerate U-statistic I_{n,k}(f) of order k satisfy such estimates as the moments Eη^{2kM} of a Gaussian random variable η with expectation zero and appropriate variance. Such estimates (together with the Markov inequality) imply the inequalities we want prove, and beside this there is a method which enables us to bound such moments.

Such moments can be estimated by means of the so-called diagram formula about random integrals. This formula makes possible to express the moments we are interested in as the sum of certain integrals defined with the help of some diagrams. To give a good estimate on the moments we want to bound it has to be shown that the “diagrams corresponding to the Gaussian effect” yield the main contribution to them. In such a way we can get an explanation why the tail distribution of degenerate U-statistics and random integrals satisfy such an estimate which the behaviour of Wiener–Itô integrals (i.e. the Gaussian case) suggests.

The explanation of the details in the estimation of multiple random integrals or degenerate U-statistics of order k ≥ 2 demands the application of rather complicated notations. This requires much work which cannot be done in a short summary paper. Hence I omit its discussion. On the other hand, I consider a special case of this problem, the estimation of the moments of sums of independent random variables. This may explain very much also about the general case.

Let ξ_{1}, …, ξ_{n} be a sequence of independent and identically distributed random variables such that Eξ_{1} = 0, Var ξ_{1} = σ^{2}, and let us estimate the even moments

of the sum S_{n} = ∑_{j=1}^{n} ξ_{j}. The identity

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

holds.

Simple combinatorial considerations show that in the sum at the right-hand side of the identity (5.1) most terms are indexed with such a vector

(j_{1}, …, j_{M}, l_{1}, …, l_{M})

for which j_{u} = 2 for all numbers 1 ≤ u ≤ M. The number of such terms equals \binom{n}{M} \frac{(2M)!}{2^{M}} ∼ n^{M} \frac{(2M)!}{2^{M} M!}. Hence it is natural to expect that in typical cases ES_{n}^{2M} ∼ (nσ^{2})^{M} \frac{(2M)!}{2^{M} M!}. This consideration suggests the estimate

∑_{1≤l_{1}<l_{2}<···<l_{M} ≤n} Eξ_{l_{1}}^{2} ⋯ Eξ_{l_{M}}^{2} = \binom{n}{M}\frac{(2M)!}{2^{M}}σ^{2M} ∼ \frac{(2M)!}{2^{M}M!}(nσ^{2})^{M} = Eη^{2M}

for the quantity ES_{n}^{2M}, where η is a Gaussian random variable with expectation zero and variance Var S_{n}.

The above heuristic argument shows why we can expect such estimates for the moments of sums of independent random variables as in the Gaussian case. In nice cases this argument yields the right estimate.

But at working out the details some finer considerations have to be applied. It is not enough to give a good estimate on the number of the terms of different type, their magnitude has also to be taken into consideration. It is possible that relatively few summands with relatively large values yield the main contribution in the sum at the right-hand side of formula (5.1).

Let us consider for instance the following example. Let the terms of the sum be of the following form: P (ξ_{1} = 1) = P (ξ_{1} = −1) = \frac{σ^{2}}{2} , P (ξ_{1} = 0) = 1 − σ^{2}. If σ^{2} is very small and the number M is large, then

∑_{j=1}^{n} Eξ_{j}^{2M} = nσ^{2} ≫ ∑_{1≤l_{1}<l_{2}<···<l_{M} ≤n} Eξ_{l_{1}}^{2} ⋯ Eξ_{l_{M}}^{2} ∼ \frac{(2M)!}{2^{M}M!}n^{M}σ^{2M}.

It can be seen by working out the details of the above example in the general case that we can get a good estimate for high moments of sums of independent random variables only if the variance of the summands is not too small, and not too high moments are bounded. Similar considerations may also explain why we can get good ‘Gaussian type’ estimates on the high moments of degenerate Ustatistics and random integrals only under the condition that their variance is not too small.

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

Let us consider the random integrals of a class of functions with respect to a normalized empirical distribution or a system of degenerate U-statistics defined with the help of a class of kernel functions and a sequence of independent and identically distributed random variables. We want to give a good estimate on the supremum of such integrals or U-statistics. It can be expected that in nice cases almost such a good estimate holds for this supremum as in the case when all but one random integrals or U-statistics are omitted from this class, and only the ‘worst’ integral or U-statistic is preserved, that one for which the weakest estimate holds. In the subsequent discussion such results will be given. To get them first the definition of good classes of functions has to be found for which good and substantial results hold.

It is useful to look for such classes of functions from which such a subclass with relatively few functions can be selected which is dense in the original class in an appropriate sense. The introduction of the following two notions proved to be useful.

Definition of L_{2}-dense classes of functions with respect to some measure. Let a measurable space be (Y, Y) be given together with a σ-finite measure ν and a class G of Y-measurable, real valued functions on this space. This class of functions G is called an L_{2}-dense class with respect to ν with parameter D and exponent L if for all numbers 1 ≥ ε > 0 there exists a subclass G_{ε} = {g_{1}, …, g_{m}} ⊂ G in the space L_{2}(Y, Y, ν) consisting of m ≤ Dε^{−L} elements such that inf_{g_{j}∈G_{ε}} ∫ |g − g_{j}|^{2} dν < ε^{2}

for all functions g ∈ G.

The other useful notion is the following one.

Definition of L_{2}-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_{2}-dense class of functions with parameter D and exponent L if it is L_{2}-dense with parameter D and exponent L with respect to all probability measures ν on (Y, Y).

It is useful to consider first Problem B′′) about the supremum of Wiener–Itô integrals, then to describe the results on Problems B) and B′) about the supremum of random integrals with respect to normalized empirical distribution and degenerate U-statistics and to compare these results.

Estimate about the tail distribution of the supremum of Wiener–Itô integrals. Let us consider a measurable space (X, X) together with a σ-finite non-atomic 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 (3.3) for all f ∈ F. The inequality

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

holds with some universal constants C = C(k) > 0 and α = α(k) > 0 if

(\frac{u}{σ} )^{2/k} ≥ ML log \frac{2}{σ}  (6.1)

with some appropriate constant M = M(k) > 0.

In the above result — disregarding the value of the universal constants appearing in it — the same estimate is obtained about the tail distribution of Wiener–Itô integrals (under appropriate conditions) as in the estimate about the tail distribution of a single Wiener–Itô integral. The only essential difference between these two results is that in the present case an additional condition formulated in formula (6.1) had to be imposed. It is not difficult to present such an example which shows that such a condition is really needed. But here I omit its description.

The next result is an estimate on the tail-distribution of the supremum of random integrals J_{n,k}(f) defined in formula (1.1).

Estimate on the tail distribution of the supremum of multiple integrals with respect to a normalized empirical distribution. 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}) such that

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

and

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

for all functions f ∈ F 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.1) satisfies the inequality

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

provided that

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

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.

A similar estimate holds for the supremum of degenerate U-statistics I_{n,k}(f), f ∈ F. The only difference in comparison with the above result that in the case of the supremum of U-statistics the additional condition has to be imposed that the U-statistics I_{n,k}(f) must be degenerate.

An essential difference between the results about the estimation of the supremum of Wiener–Itô integrals Z_{μ,k}(f) and integrals with respect to normalized empirical distribution J_{n,k}(f) is that in the first case the class of functions F had to be L_{2}-dense with respect to the product measure μ^{k}, while in the second case a more restrictive condition was imposed. In the case of supremum of integrals with respect to a normalized empirical distribution the class of functions F had to satisfy the L_{2}-property, i.e. it had to be L_{2}-dense with respect to all probability measures. The question arises what the cause of this difference is.

The supremum of Wiener–Itô integrals can be bounded by means of a simple and natural method, the so-called ‘chaining argument’. In the case of the random integrals J_{n,k}(f) this method is not strong enough to solve the problem, it only yields some partial results. To get a complete solution some additional methods have to be applied, and their application demands some additional restrictions.

The elaboration of the details would demand much work and the application of methods essentially different from previous ones. Hence I shall present only a brief sketch of the main ideas. The main emphasize will be put on the explanation of the main problems and methods. First I briefly explain the ‘chaining argument’.

The ‘chaining argument’, and the boundary of this method.

Let us apply the notation worked out in the formulation of the results about the supremum of Wiener–Itô integrals. Let us take for all indices N = 1, 2, … such a system of increasing subsets F_{1} ⊂ F_{2} ⊂ ⋯ ⊂ F_{N} ⊂ ⋯ ⊂ F of the class of functions F with relatively small cardinalities which satisfy the relation

inf_{g∈F_{N}} ∫ (f(x_{1}, …, x_{k}) − g(x_{1}, …, x_{k}))^{2} μ( dx_{1}) … μ( dx_{k}) ≤ 2^{−2N}σ^{2}.

for all functions f ∈ F.

The probabilities

P ( sup_{g∈F_{N}} Z_{μ,k}(g) > u (1 − 2^{−N}))

can be well estimated by means of a recursion for N = 1, 2, …, since for all functions g ∈ F_{N+1} there exists a function g′ ∈ F_{N} (close to it) for which

∫ (g(x_{1}, …, x_{k}) − g′(x_{1}, …, x_{k}))^{2} μ( dx_{1}) … μ( dx_{k}) ≤ 2^{−2N}σ^{2}.

Hence the probability

P (|Z_{μ,k}(g) − Z_{μ,k}(g′)| > 2^{−N}u) = P (|Z_{μ,k}(g − g′)| > 2^{−N}u)

can be well estimated by means of the previous results about the tail distribution Wiener–Itô integrals. By working out the details the result about the tail distribution of the supremum of Wiener–Itô integrals can be relatively simply proved.

The above considered ‘chaining argument’ is not strong enough to estimate the supremum of integrals with normalized empirical distribution or of degenerate U-statistics. It only makes possible to reduce the problem to the case when the expressions σ^{2}(f) = ∫ f^{2}(x_{1}, …, x_{k})μ( dx_{1}) … μ( dx_{k}) are small for all functions f ∈ F.

The ‘chaining argument’ is a weak method in the study of this problem for the following reason.

There are only very weak estimates on probabilities of the form

P (I_{n,k}(f) > u) or P (J_{μ,k}(f) > u)

if σ^{2}(f) is very small, and the number u is relatively large. This is the consequence of the previously discussed fact that there cannot be given such a good estimate for the tail distribution of degenerate U-statistics or random integrals with respect to a normalized empirical distribution function with small variance as the Gaussian comparison would suggest.

This difficulty can be overcome by means of a different method, by means of a symmetrization argument. This method consists of reducing the estimation of a probability of the type

P (\frac{1}{k!} sup_{f∈F} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} f(ξ_{j_{1}}, …, ξ_{j_{k}}) > u)

to a probability of the type

P (\frac{1}{k!} sup_{f∈F} ∑_{\begin{matrix}1≤j_{s}≤n, s=1,...,k, \\ j_{s}≠j_{s′} if s≠s′ \end{matrix}} ε_{j_{1}} … ε_{j_{k}}f(ξ_{j_{1}}, …, ξ_{j_{k}}) > u) ,  (6.2)

where ε_{1}, …, ε_{n} are independent random variables with distribution P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2} for all indices 1 ≤ j ≤ n. Beside this, they are also independent of the random variables ξ_{1}, …, ξ_{n}.

The probabilities in formula (6.2) can be well estimated by means of a ‘conditioning argument’. In the application of this method the conditional probability of the investigated event has to be bounded under the condition ξ_{1} = x_{1}, …, ξ_{n} = x_{n} for all possible values x_{1}, …, x_{n}. There are good methods to estimate such type of conditional probabilities, but they are not discussed here. On the other hand, these methods work only if the class of functions F is L_{2}-dense. This is the reason why this property appears in this problem.

There is a point which should be emphasized even in this sketchy discussion of the problems. In the study of the supremum of random integrals with respect to a normalized empirical distribution or of degenerate U-statistics a different method was applied in the estimation of random variables with relatively large and small variance. In the case of relatively large variance the ‘chaining argument’ works, while in the case of small variance an appropriate symmetrization argument was applied. Behind the different approaches in these two cases there is a deeper reason.

The ‘chaining argument’ works well only in the study of the supremum of degenerate U-statistics or random integrals with respect to a normalized empirical measures with not too small variance; in the case when the U-statistics and random integrals satisfy such estimates which their ‘Gaussian type limits’ suggest. There can be defined some ‘irregular events’ whose appearance implies that the U-statistics or random integrals take extremely large values. But in the case of random variables with not too small variances the probability of such irregular events is very small, and their effect can be disregarded. The case of U-statistics or random integrals with a small variance is different. In this case the probability of these irregularities (compared to the events of regular events) is relatively large, and in the estimation of the probabilities we are interested in their effect is dominant.

In the estimation of the tail distribution of the supremum of multiple integrals a simultaneous application of the two above mentioned arguments is needed. The ‘chaining argument’ helps to reduce the problem to such a case when the supremum of random variables with very small variance have to be bounded. In this situation the effect of the irregularities is non-negligible, and we can estimate this supremum ‘with non-Gaussian behaviour’ with the help of some symmetrization type arguments.

In this work I tried to describe briefly the result of an important subject together with the heuristic picture behind the results. A more detailed discussion of this subject can be found in my work [1]. This work also contains a fairly detailed list of references.

References

1.) Péter Major: Tail behaviour of multiple random integrals and U-statistics. Probability Reviews. 448–505, (2005)