ON A MULTIVARIATE VERSION OF BERNSTEIN’S INEQUALITY

Péter Major Alfréd Rényi Mathematical Institute of the Hungarian Academy of Sciences Budapest, P.O.B. 127 H–1364, Hungary, e-mail: major@renyi.hu

Summary: We prove such a multivariate version of Bernstein’s inequality about the tail distribution of degenerate U-statistics which is an improvement of some former results. This estimate will be compared with an analogous bound about the tail distribution of multiple Wiener-Itô integrals. Their comparison shows that our estimate is sharp. The proof is based on good estimates about high moments of degenerate U-statistics. They are obtained by means of a diagram formula which enables us to express the product of degenerate U-statistics as the sum of such expressions.

1. Introduction.

Let us consider a sequence of iid. random variables ξ_{1}, ξ_{2}, …, on a measurable space (X, X) with some distribution μ together with a real valued function f = f(x_{1}, …, x_{k}) of k variables defined on the k-th power (X^{k}, X^{k}) of the space (X, X) and define with their help the U-statistics I_{n,k}(f), n = k, k + 1, …,

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

We want to get good estimates on the probabilities P (n^{−k/2}k!|I_{n,k}(f)| > u) for u > 0 under appropriate conditions.

Let me first recall a result of Arcones and Giné [2] in this direction. They have proved 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

(1.2)

with some universal constants c_{1}, c_{2} and c_{3} depending only on the order k of the Ustatistic I_{n,k}(f) defined in (1.1) if the function f satisfies the conditions

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

and it is canonical with respect to the probability measure μ, i.e.

∫ 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}.

A U-statistic defined in (1.1) with the help of a canonical function f is called degenerate in the literature. Degenerate U-statistics are the natural multivariate versions of sums of iid. random variables with expectation zero.

Actually Arcones and Giné formulated their result in a slightly different but equivalent form. They called their estimate (1.2) a new Bernstein-type inequality. The reason for such a name is that the original Bernstein inequality (see e.g. [3], 1.3.2 Bernstein inequality) states relation (1.2) in the special case k = 1 with constants c_{1} = 2, c_{2} = \frac{1}{2} and c_{3} = \frac{1}{3} if the function f(x) satisfies the conditions sup |f(x)| ≤ 1, ∫ f(x)μ( dx) = 0 and ∫ f^{2}(x)μ( dx) ≤ σ^{2}. (Bernstein’s inequality states a slightly stronger estimate in the case k = 1. It states this inequality with constants c_{1} = 1, c_{2} = \frac{1}{2} and c_{3} = \frac{1}{3} if there is no absolute value inside the probability at the left-hand side of (1.2).)

Our goal is to prove such an improvement of this result which gives the right value of the parameter c_{2} in formula (1.2), and we also want to explain the probabilistic content of such an improvement. For this goal let us first make a more detailed comparison between Bernstein’s inequality and estimate (1.2).

Let us consider the sum S_{n} = ∑_{j=1}^{n} ξ_{j} of iid. random variables ξ_{1}, …, ξ_{n} such that

Eξ_{1} = 0, P (|ξ_{1}| ≤ 1) = 1, and consider the probability p_{n}(u) = P (\frac{1}{\sqrt{n}}S_{n} > u) for all

u > 0. Put σ^{2} = Eξ_{1}^{2}. Bernstein’s inequality implies that

p_{n}(u) ≤ exp \{− (1 − \frac{Ku}{\sqrt{n}σ^{2}} ) \frac{u^{2}}{2σ^{2}} \} for all 0 ≤ u ≤ \sqrt{n}σ^{2}

with some number K < 1. A similar estimate holds for 0 ≤ u ≤ C\sqrt{n}σ^{2} for any number C > 0, but in the case u ≫ \sqrt{n}σ^{2} only a much weaker inequality holds. (See Example 2.4 in [10] for an example where only a very weak estimate holds if u ≫ \sqrt{n}σ^{2}.) This means that Bernstein’s inequality has the following perturbation type character. For small numbers u (if 0 < u < ε\sqrt{n}σ^{2} with some small ε > 0) the expression in the exponent of the upper bound given for p_{n}(u) is a small perturbation of −\frac{u^{2}}{2σ^{2}} , of the expression suggested by the central limit theorem. For u ≤ const. \sqrt{n}σ^{2} a similar bound holds, only with a worse constant in the exponent. If u ≫ \sqrt{n}σ^{2}, then no good Gaussian type estimate holds for the probability p_{n}(u).

Next I formulate the main result of this paper, Theorem 1, which is an estimate similar to that of [2]. But, as I will show, it is sharper, and it has a perturbation type character, similar to Bernstein’s inequality.

Theorem 1. Let ξ_{1}, …, ξ_{n} be a sequence of iid. random variables on a space (X, X) with some distribution μ. Let us consider a function f(x_{1}, …, x_{k}), canonical with respect to the measure μ on the space (X^{k}, X^{k}) which satisfies conditions (1.3) and (1.4) with some 0σ^{2} ≤ 1 together with the degenerate U-statistic I_{n,k}(f) 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})}\} (1.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 (1.5).

To understand the content of Theorem 1 better let us recall the following limit distribution result about degenerate U-statistics, (see e.g. [4]). If the canonical function f of k variables satisfies condition (1.4), then the degenerate U-statistics n^{−k/2}I_{n,k}(f) converge in distribution to the k-fold Wiener–Itô integral J_{μ,k}(f),

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

of the function f with respect to a white noise μ_{W} with reference measure μ. Here μ is the distribution of the random variables ξ_{j}, j = 1, 2, … appearing in the U-statistics I_{n,k}(f). Let me recall that a white noise μ_{W} with reference measure μ on (X, X) is a set of jointly Gaussian random variables μ_{W} (A), A ∈ X, μ(A) < ∞, such that Eμ_{W} (A) = 0, Eμ_{W} (A)μ_{W} (B) = μ(A ∩ B) for all A ∈ X and B ∈ X. The definition of Wiener–Itô integrals can be found for instance in [6] or [8].

The above result suggests to describe the tail-distribution of the Wiener–Itô integral J_{μ,k}(f) and to show that Theorem 1 gives such an estimate which the above mentioned limit theorem and the tail distribution of J_{μ,k}(f) suggests. At this moment there appears an essential difference between the problem discussed in Bernstein’s inequality and its multivariate version.

We want to estimate both the U-statistic I_{n,k}(f) and the Wiener–Itô integral J_{μ,k}(f) by means of their variance. (Let me remark that the integral in formula (1.4) equals the variance of (k!)^{1/2}J_{μ,k}(f), and it is asymptotically equal to the variance of (k!)^{1/2}n^{−k/2}I_{n,k}(f) for large n. At least, this is the case if f is a symmetric function of its variables. But, since I_{n,k}(f) = I_{n,k}(Sym f), J_{μ,k}(f) = J_{μ,k}(Sym f), and ∥Sym f∥_{2}^{2} ≤ ∥f∥_{2}^{2} we may restrict our attention to this case.) But while the variance and expectation determines the distribution of a Gaussian random variable, the distribution of a Wiener–Itô integral is not determined by its variance and (zero) expectation. Hence if we want to compare the estimation of degenerate U-statistics by means of their variance with a natural Gaussian counterpart of this problem, then it is natural to consider first the following problem.

Find such an upper estimate for the tail distribution of Wiener–Itô integrals which holds for all of them with a prescribed bound on their variances, and which is sharp in the following sense. There is a Wiener–Itô integral whose variance is not larger than the prescribed bound, and which satisfies a very similar lower estimate. Then the estimate for degenerate U-statistics has to be compared with such an estimate for Wiener–Itô integrals. The following Theorem 2 and Example 3 give an estimate for Wiener–Itô integrals with the desired properties. (These results were proven in [11.) They suggest to compare the upper bound in Theorem 1 with the function const. exp \{−\frac{1}{2} (\frac{u}{σ})^{2/k}\} with some appropriate constant.

Theorem 2. Let us consider a σ-finite measure μ on a measurable space 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 J_{μ,k}(f) introduced in formula (1.6). This random integral satisfies the inequality

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

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

Example 3. Let us have a σ-finite measure μ on some measure 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 J_{μ,k}(f) introduced in formula (1.6).

Then the relation ∫ f(x_{1}, …, x_{k})^{2} μ( dx_{1}) … μ( dx_{k}) = σ^{2} holds, and the random integral J_{μ,k}(f) satisfies the inequality

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

with some constant C̄ > 0.

By Theorem 1 there are some constants α > 0, C_{1} > 0, 1 > C_{2} > 0, C_{1}α < 1 such that under the conditions of this result

P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ A exp \{−\frac{1}{2} (\frac{u}{σ} )^{2/k} (1 − C_{1} (\frac{u}{n^{k/2}σ^{k+1}} )^{1/k})\}
if 0 < u ≤ αn^{k/2}σ^{k+1}

and

P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ A exp \{−C_{2} (\frac{u}{σ} )^{2/k}\} if αn^{k/2}σ^{k+1} < u ≤ n^{k/2}σ^{k+1}.

A comparison of these estimates with Theorem 2 and Example 3 shows that Theorem 1 has a behaviour similar to that of Bernstein’s inequality. For relatively small numbers u > 0, more precisely if 0 < u < εn^{k/2}σ^{k+1} with some ε > 0, the expression in the exponent at the right-hand side of this estimate is very close to −\frac{1}{2} (\frac{u}{σ})^{2/k}, the term suggested by Theorem 2 and Example 3. In the more general case u ≤ n^{k/2}σ^{k+1} a similar, but somewhat worse estimate holds. The term − (\frac{u}{σ})^{2/k} in the upper estimate is multiplied by a constant C_{2} > 0 which may be much smaller than \frac{1}{2}. So the estimate of Theorem 1 — unlike formula (1.2) — has a perturbation type character.

On the other hand it may seem that the estimate (1.2) has the advantage that it yields a bound for the tail-distribution of a degenerate U-statistic for all numbers u > 0, while formula (1.5) holds only under the condition 0 ≤ u ≤ n^{k/2}σ^{k+1}. Nevertheless, formula (1.5) implies such an estimate also for u > n^{k/2}σ^{k+1} which is not weaker than the inequality (1.2) (at least if we do not bother about the value of the universal constants in these estimates). To see this observe that relation (1.3) remains valid if σ^{2} is replaced by any σ̄^{2} ≥ σ^{2}. As a consequence, for n^{k/2} ≥ u > n^{k/2}σ^{k+1} relation (1.5) holds with the replacement of σ by σ̄ = (un^{−k/2})^{1/(k+1)}, since all conditions of Theorem 1 are satisfied with such a choice. It yields that 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}}. On the other hand,

σ^{2/k} (1 + c_{3} (un^{−k/2}σ^{−(k+1)})^{2/k(k+1)}) ≥ c_{3}u^{2/k(k+1)}n^{−1/(k+1)}, hence the right-hand

side of (1.2) can be bounded from below by c_{1}e^{−c_{2}(u^{2}n)^{1/(k+1)}/c_{3}}. Thus relation (1.5) implies relation (1.2) if n^{k/2} ≥ u > n^{k/2}σ^{k+1} with possibly worse constants c̄_{1} = A, c_{2} and c̄_{3} = 2c_{2}(1 + B)^{1/k}. If u > n^{k/2}, then the left-hand side of (1.2) equals zero because of the boundedness of the function f, and relation (1.2) clearly holds.

Actually the condition u ≤ n^{k/2}σ^{k+1} was rather natural in Theorem 1. It can be shown that in the case u ≫ n^{k/2}σ^{k+1} there are such degenerate U-statistics satisfying the conditions of Theorem 1 for which the probability P (n^{−k/2}k!I_{n,k}(f) > u) is much greater than the expression suggested by the limit theorem for degenerate U-statistics together with Theorem 2 and Example 3. Such an example is presented in Examples 4.5 in [10] for k = 2. With some extra work similar examples of degenerate U-statistics of order k could also be constructed for any k = 2, 3, . . ..

Let me say some words about the method of proofs. Theorem 1 will be proved by means of good estimates on high moments of degenerate U-statistics. They can be obtained with the help of a new type of diagram formula which enables us to write the product of degenerate U-statistics as the sum of degenerate U-statistics. Such a formula may be interesting in itself. It is a version of an important result about the representation of a product of Wiener–Itô integrals in the form of sums of Wiener–Itô integrals. It makes possible to adapt the methods in the theory of Wiener–Itô integrals to the study of degenerate U-statistics. It also gives some insight why the tail distributions of degenerate U-statistics and Wiener–Itô integral satisfy similar estimates.

This approach is essentially different from that of earlier papers in this field, e.g. from the proof of paper [2]. I had to choose a different method, because the technique of previous papers was not strong enough to prove Theorem 1. They give only such weaker estimates for high moments of degenerate U-statistics which are not sufficient for our purposes. This weakness has different causes. First, previous proofs apply an estimate called Borell’s inequality in the literature, which does not supply a sharp estimate in certain cases. This has the consequence that we can get only a relatively weak estimate about high moments of degenerate U-statistics in such a way. (See the end of my paper [11] for a more detailed discussion.) Beside this, earlier papers in this field apply a method called the decoupling technique in the literature, and this method has some properties which enable only the proof a weaker version of Theorem 1.

The decoupling technique contains some randomization procedure, and as a more careful analysis shows, its application allows us to prove only relatively weak estimates. The randomization procedure applied in the decoupling technique makes possible to reduce the estimation of the degenerate U-statistic we want to bound to the estimation of another degenerate U-statistic which can be better handled. But this new U-statistic has a larger variance than the original one. As a consequence, this method cannot give such a good estimate which ‘resembles’ to the limit distribution of the original U-statistic. Hence for relatively small numbers u it supplies a weaker estimate for the distribution of degenerate U-statistics than formula 1.5.

Let me still remark that at recent time some new estimates are proved about the tail distribution of degenerate U-statistics. (See [1], [5], [7].) They may supply a better bound in certain cases with the help of some additional quantities related to the properties of the kernel function of the U-statistic. Such problems will be not discussed in this paper, but I would remark that the method of this paper may work also in such investigations. The diagram formula supplies a better estimate for the moments of a degenerate U-statistic if its kernel function has some nice properties. There is some hope that the recent results about the tail distribution of degenerate U-statistics can be proved in such a way.

This paper consists of six sections. In Section 2 the proof of Theorem 1 is reduced to a moment estimate for degenerate U-statistics formulated in that section. To understand the content of this moment estimate better I also present its Wiener–Itô integral counterpart. Theorem 2 follows from this moment estimate for Wiener–Itô integrals in a standard way. This proof will be omitted, since it can be found in [11]. The proof of Example 3 can also be found in [11], hence its proof will be also omitted. Sections 3, 4 and 5 contain the proof of the diagram formula for the product of degenerate U-statistics needed in the proof of the moment estimate in Section 2. The diagram formula about the product of two degenerate U-statistics is formulated in Section 3, and its proof is given in Section 4. Section 5 contains the formulation and proof of the diagram formula for the products of degenerate U-statistics in the general case. In Section 6 the moment estimate given is Section 2 is proved by means of the diagram formula. In such a way the proof of Theorem 1 is completed.

2. The reduction of the proof of Theorem 1 to a moment estimate.

Theorem 1 will be proved by means of the following

Proposition A. 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 (1.3) and (1.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 k 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}.

(2.1)

The constant C = C(k) in formula (2.1) 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).

To understand the content of Proposition A better I formulate its Wiener–Itô integral counterpart in the following

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

E (k!|J_{μ,k}(f)|)^{2M} ≤ 1 · 3 · 5 ⋯ (2kM − 1)σ^{2M} for all M = 1, 2, …  (2.2)

holds.

By the Stirling formula Proposition B implies that

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

for any A > \sqrt{2} if M ≥ M_{0} = M_{0}(A). The right-hand side of formula (2.2) is almost as large as the right-hand side of formula (2.3). Hence the estimate (2.3) gives an almost as good estimate as Proposition B. We shall use this estimate in the sequel because of its simpler form.

Proposition B can be considered as a corollary of a most important result about Wiener–Itô integrals called the diagram formula. This result 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 is equal to the sum of the constant terms (i.e. of the integrals of order zero) in the diagram formula. In such a way the diagram formula yields an explicit (although somewhat complicated) formula about the moments of Wiener–Itô integrals. Proposition B can be proved relatively simply by means of this relation. Since it is written down in paper [11], I omit the details.

We shall see that there is such a version of the diagram formula which expresses the product of degenerate U-statistics as a sum of degenerate U-statistics of different order by means of some appropriately defined diagrams. Proposition A can be proved by means of this version of the diagram formula similarly to Proposition B. The proof of Proposition A with the help of this version of the diagram formula will be given in Section 6. The main difference between the proof of Propositions A and B with the help of the corresponding diagram formula is that in the case of degenerate U-statistics the diagram formula contains some additional new diagrams, and their contribution also has to be estimated. It will be shown that if not too high moments of U-statistics are calculated by means of the diagram formula, then the contribution of the new diagrams is not too large.

To better understand the content of Proposition A let us compare formulas (2.1) and (2.3). These estimates are very similar. The upper bound given for the 2M-th moment of a degenerate U-statistic in formula (2.1) is less than A^{M}-times the upper bound given for the 2M-th moment of the corresponding Wiener–Itô integral in formula (2.3) with some universal constant A > 1. Moreover, the constant A is very close to 1 if the parameter M is relatively small, if M ≤ εnσ^{2} with some small number ε > 0. But the estimate (2.1) holds only for not too large parameters M, because of the condition kM < ηnσ^{2} in it. Because of this condition Proposition A gives a much worse bound for the 2M-th moment of a degenerate U-statistic if M ≫ nσ^{2} than inequality (2.3) yields for the 2M-th moment of the corresponding Wiener–Itô integral. The above mentioned properties of the moment estimates in Proposition A are closely related to the behaviour of the estimate in Theorem 1, in particular to the condition u ≤ n^{k/2}σ^{k+1} in it.

Theorem 2 can be proved by means of the Proposition B and the Markov inequality P (|J_{μ,k}(f)| > u) ≤ \frac{EJ_{μ,k}(f)^{2M}}{u^{2M}} with a good choice of the parameter M. This is a rather standard approach, and this proof is written down in [11]. Hence I omit it. Theorem 1 can be proved similarly with the help of Proposition A and the Markov inequality, but in this case a more careful analysis is needed to find the good choice of the parameter M with which the Markov inequality should be applied. I work out the details.

Proof of Theorem 1 by means of Proposition A. We can write by the Markov inequality and Proposition A with the choice η = \frac{kM}{nσ^{2}} that

\begin{aligned}P (k!n^{−k/2}|I_{n,k}(f)| > u) & ≤ \frac{E (k!n^{−k/2}I_{n,k}(f))^{2M}}{u^{2M}} \\ & ≤ A (\frac{1}{e} · 2kM (1 + C \frac{\sqrt{kM}}{\sqrt{n}σ} )^{2} (\frac{σ}{u} )^{2/k})^{kM} \end{aligned}  (2.4)

for all integers M ≥ M_{0} with some M_{0} = M_{0}(k) and A = A(k).

We shall prove relation (1.5) with the help of estimate (2.4) first in the case D ≤ \frac{u}{σ} ≤ n^{k/2}σ^{k} with a sufficiently large constant D = D(k, C) > 0 depending on k and the constant C in (2.4). To this end let us introduce the numbers M̄,

kM̄ = \frac{1}{2} (\frac{u}{σ} )^{2/k} \frac{1}{1 + B \frac{(\frac{u}{σ})^{1/k}}{\sqrt{n}σ}} = \frac{1}{2} (\frac{u}{σ} )^{2/k} \frac{1}{1 + B (un^{−k/2}σ^{−(k+1)})^{1/k}}  (2.5)

with a sufficiently large number B = B(C) > 0 and M = [M̄], where [x] means the integer part of the number x.

Observe that \sqrt{kM̄} ≤ (\frac{u}{σ})^{1/k}, \frac{\sqrt{kM̄}}{\sqrt{n}σ} ≤ (un^{−k/2}σ^{−(k+1)})^{1/k} ≤ 1, and

(1 + C \frac{\sqrt{kM̄}}{\sqrt{n}σ} )^{2} ≤ 1 + B \frac{\sqrt{kM̄}}{\sqrt{n}σ} ≤ 1 + B (un^{−k/2}σ^{−(k+1)})^{1/k}

with a sufficiently large B = B(C) > 0 if \frac{u}{σ} ≤ n^{k/2}σ^{k}. Hence

\begin{aligned}\frac{1}{e} · 2kM (1 + C \frac{\sqrt{kM}}{\sqrt{n}σ} )^{2} (\frac{σ}{u} )^{2/k} & ≤ \frac{1}{e} · 2kM̄ (1 + C \frac{\sqrt{kM̄}}{\sqrt{n}σ} )^{2} (\frac{σ}{u} )^{2/k} \\ & ≤ \frac{1}{e} · \frac{(1 + C \frac{\sqrt{kM̄}}{\sqrt{n}σ} )^{2}}{1 + B (un^{−k/2}σ^{−(k+1)})^{1/k}} ≤ \frac{1}{e} \end{aligned}  (2.6)

if \frac{u}{σ} ≤ n^{k/2}σ^{k}. If the inequality D ≤ \frac{u}{σ} also holds with a sufficiently large D = D(B, k) > 0, then M = [M̄] ≥ M_{0} because of the definition of [M̄] in formula (2.5) and the relation un^{−k/2}σ^{k+1} ≤ 1. With such a choice the conditions of inequality (2.4) hold. By applying it together with inequality (2.6) we get that

P (k!n^{−k/2}|I_{n,k}(f)| > u) ≤ Ae^{−kM} ≤ Ae^{k}e^{−kM̄}

if D ≤ \frac{u}{σ} ≤ n^{k/2}σ^{k}. This means that inequality (1.5) holds in this case with a preexponential constant Ae^{k}. Since e^{−kM̄} is bounded from below for \frac{u}{σ} ≤ D relation (1.5) holds for all 0 ≤ \frac{u}{σ} ≤ n^{k/2}σ^{k} with a possible increase of the pre-exponential coefficient Ae^{k} in it. Theorem 1 is proved.

Let us observe that the above calculations show that the constant B in formula (1.8) can be chosen independently of the order k of the U-statistics I_{n,k}(f).

3. The diagram formula for the product of two degenerate U-statistics.

To prove Proposition A we need a good identity which expresses the expectation of the product of degenerate U-statistics in a form that can be better handled. Such an identity can be proved by means of a version of the diagram formula for Wiener–Itô integrals where the product of degenerate U-statistics is represented as the sum of degenerate U-statistics with appropriate kernel functions. In such a formula the kernel functions of the sum representation are defined with the help of some diagrams, and to get a useful result we also need a good estimate on their L_{2}-norm.

We shall prove such a result. First we prove its special case about the product of two degenerate U-statistics together with a good estimate on the L_{2}-norm of the kernel functions in the sum representation. Then the result in the general case can be obtained by induction.

In the case of the product of two degenerate U-statistics the result we want to prove can be obtained with the help of the following observation. Let us have a sequence of iid. random variables ξ_{1}, ξ_{2}, … with some distribution μ on a measurable space (X, X) together with two functions f(x_{1}, …, x_{k_{1}}) and g(x_{1}, …, x_{k_{2}}) on (X^{k_{1}}, X^{k_{1}}) and on (X^{k_{2}}, X^{k_{2}}) respectively which are canonical with respect to the probability measure μ. We consider the degenerate U-statistics I_{n,k_{1}}(f) and I_{n,k_{2}}(g) and want to express their normalized product k_{1}!k_{2}!n^{−(k_{1}+k_{2})/2}I_{n,k_{1}}(f)I_{n,k_{2}}(g) as a sum of (normalized) degenerate U-statistics. This product can be presented as a sum of U-statistics in a natural way. Then by writing each term of this sum as a sum of degenerate U-statistics by means of the Hoeffding decomposition we get the desired representation of the product. This result will be formulated in Theorem A.

In this Section Theorem A will be described together with the introduction of the notations needed for its formulation. Its proof will be given in the next Section.

To define the kernel functions of the U-statistics appearing in the diagram formula for the product of two U-statistics first we introduce a class of objects Γ(k_{1}, k_{2}) we shall call coloured diagrams. We define graphs γ ∈ Γ(k_{1}, k_{2}) that contain the vertices (1, 1), (1, 2), …, (1, k_{1}) which we shall call the first row and (2, 1) …, (2, k_{2}) which we shall call the second row of these graphs. From each vertex there starts zero or one edge, and each edge connects vertices from different rows. Each edge will get a colour +1 or −1. Γ(k_{1}, k_{2}) consists of all γ obtained in such a way. These objects γ will be called coloured diagrams.

Given a coloured diagram γ ∈ Γ(k_{1}, k_{2}) let B_{u}(γ) denote the set of upper endpoints (1, j) of the edges of the graph γ, B_{(b,1)}(γ) the set of lower end-points (2, j) of the edges of γ with colour 1, and B_{(b,−1)}(γ) the set of lower end-points (2, j) of the edges of γ with colour −1. (The letter ‘b’ in the index was chosen because of the word below.) Finally, let Z(γ) denote the set of edges with colour 1, W (γ) the set of edges with colour −1 of a coloured graph γ ∈ Γ(k_{1}, k_{2}), and let |Z(γ)| and |W (γ)| denote their cardinality.

Given two functions f(x_{1}, …, x_{k_{1}}) and g(x_{1}, …, x_{k_{2}}) let us define the function

(f ∘ g)(x_{(1,1)}, …, x_{(1,k_{1})}, x_{(2,1)}, …, x_{(2,k_{2})})

= f(x_{(1,1)}, …, x_{(1,k_{1})})g(x_{(2,1)}, …, x_{(2,k_{2})})  (3.1)

Given a function h(x_{u_{1}}, …, x_{u_{r}}) with coordinates in the space (X, X) (the indices u_{1}, …, u_{r} are all different) let us introduce its transforms P_{u_{j}}h and Q_{u_{j}}h by the formulas

(P_{u_{j}}h)(x_{u_{l}}: u_{l} ∈ {u_{1}, …, u_{r}} \ {u_{j}}) = ∫ h(x_{u_{1}}, …, x_{u_{r}})μ( dx_{u_{j}}), 1 ≤ j ≤ r, (3.2)

and

(Q_{u_{j}}h)(x_{u_{1}}, …, x_{u_{r}}) = h(x_{u_{1}}, …, x_{u_{r}})−∫ h(x_{u_{1}}, …, x_{u_{r}})μ( dx_{u_{j}}), 1 ≤ j ≤ r. (3.3)

At this point I started to apply a notation which may seem to be too complicated, but I think that it is more appropriate in the further discussion. Namely, I started to apply a rather general enumeration u_{1}, …, u_{r} of the arguments of the functions we are working with instead of their simpler enumeration with indices 1, …, r. But in the further discussion there will appear an enumeration of the arguments by pairs of integers (l, j) in a natural way, and I found it simpler to work with such an enumeration than to reindex our variables all the time. Let me remark in particular that this means that the definition of the U-statistic with a kernel function f(x_{1}, …, x_{k}) given in formula (1.1) will appear sometimes in the following more complicated, but actually equivalent form: We shall work with kernel function f(x_{u_{1}}, …, x_{u_{k}}) instead of f(x_{1}, …, x_{k}), the random variables ξ_{j} will be indexed by u_{s}, i.e. to the coordinate x_{u_{s}} we shall put the random variables ξ_{j_{us}} with indices 1 ≤ j_{u_{s}} ≤ n, and in the new notation formula (1.1) will look like

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

Let us define for all coloured diagrams γ ∈ Γ(k_{1}, k_{2}) the function α_{γ}(1, j), 1 ≤ j ≤ k_{1}, on the vertices of the first row of γ as α_{γ}(1, j) = (1, j) if no edge starts from (1, j), and α_{γ}(1, j) = (2, j′) if an edge of γ connects the vertices (1, j) and (2, j′). Given two functions f(x_{1}, …, x_{k_{1}}) and g(x_{1}, …, x_{k_{2}}) together with a coloured diagram γ ∈ Γ(k_{1}, k_{2}) let us introduce, with the help of the above defined function α_{γ}(·) and (f ∘ g) introduced in (3.1) the function

\begin{matrix}\overline{(f ∘ g)}_{γ}(x_{(1,j)}, x_{(2,j′)}, j ∈ \{1, …, k_{1}\} \ B_{u}(γ), 1 ≤ j′ ≤ k_{2}) \\ = (f ∘ g)(x_{α_{γ}(1,1)}, …, x_{α_{γ}(1,k_{1})}, x_{(2,1)}, …, x_{(2,k_{2})}). \end{matrix}  (3.4)

(In words, we take the function (f ∘ g), and if there is an edge of γ starting from a vertex (1, j), and it connects this vertex with the vertex (2, j′), then the argument x_{(1,j)} is replaced by the argument x_{(2,j′)} in this function.) Let us also introduce the function

\begin{matrix}(f ∘ g)_{γ} (x_{(1,j)}, x_{(2,j′)}, j ∈ \{1, …, k_{1}\} \ B_{u}(γ), j′ ∈ \{1, …, k_{2}\} \ B_{(b,1)}) \\ = ∏_{(2,j′)∈B_{(b,1)}(γ)} P_{(2,j′)} ∏_{(2,j′)∈B_{(b,−1)}(γ)} Q_{(2,j′)} \\ \overline{(f ∘ g)}_{γ} (x_{(j,1)}, x_{(j′,2)}, j ∈ \{1, …, k_{1}\} \ B_{u}(γ), 1 ≤ j′ ≤ k_{2}) . \end{matrix} (3.5)

(In words, we take the function \overline{(f ∘ g)}_{γ} and for such indices (2, j′) of the graph γ from which an edge with colour 1 starts we apply the operator P_{(2,j′)} introduced in formula (3.2) and for those indices (2, j′) from which an edge with colour −1 starts we apply the operator Q_{(2,j′)} defined in formula (3.3).) Let us also remark that the operators P_{(2,j′)} and Q_{(2,j′)} are exchangeable for different indices j′, hence it is not important in which order we apply the operators P_{(2,j′)} and Q_{(2,j′)} in formula (3.5).

In the definition of the function (f ∘ g)_{γ} those arguments x_{(2,j′)} of the function \overline{(f ∘ g)}_{γ} which are indexed by such a pair (2, j′) from which an edge of colour 1 of the coloured diagram γ starts will disappear, while the arguments indexed by such a pair (2, j′) from which an edge of colour −1 of the coloured diagram γ starts will be preserved. Hence the number of arguments in the function (f ∘ g)_{γ} equals k_{1} + k_{2} − 2|B_{(b,1)}(γ)| − |B_{(b,−1)}(γ)|, where |B_{(b,1)}(γ)| and |B_{(b,−1)}(γ)| denote the cardinality of the lower end-points of the edges of the coloured diagram γ with colour 1 and −1 respectively, In an equivalent form we can say that the number of arguments of (f ∘ g)_{γ} equals k_{1} + k_{2} − (2|Z(γ)| + |W (γ)|).

Now we are in the position to formulate the diagram formula for the product of two degenerate U-statistics.

Theorem A. Let us have a sequence of iid. random variables ξ_{1}, ξ_{2}, … with some distribution μ on some measurable space (X, X) together with two bounded, canonical functions f(x_{1}, …, x_{k_{1}}) and g(x_{1}, …, x_{k_{2}}) with respect to the probability measure μ on the spaces (X^{k_{1}}, X^{k_{1}}) and (X^{k_{2}}, X^{k_{2}}). Let us introduce the class of coloured diagrams Γ(k_{1}, k_{2}) defined above together with the functions (f ∘ g)_{γ} defined in formulas (3.1)— (3.5).

For all γ ∈ Γ the function (f ∘ g)_{γ} is canonical with respect to the measure μ with k(γ) = k_{1}+k_{2}−(2|Z(γ)|+|W (γ)|) arguments, where |Z(γ)| denotes the number of edges with colour 1 and |W (γ)| the number of edges with colour −1 of the coloured diagram γ. The product of the degenerate U-statistics I_{n,k_{1}}(f) and I_{n,k_{2}}(g), n ≥ max(k_{1}, k_{2}), defined in (1.1) satisfies the identity

k_{1}!n^{−k_{1}/2}I_{n,k_{1}}(f)k_{2}!n^{−k_{2}/2}I_{n,k_{2}}(g)

= \begin{matrix}∑ & ′(n) \\ γ∈Γ(k_{1},k_{2}) \end{matrix} \frac{∏_{j=1}^{|Z(γ)|}(n − (k_{1} + k_{2}) + |W (γ)| + |Z(γ)| + j)}{n^{|Z(γ)|}}  (3.6)
n^{−|W (γ)|/2} · k(γ)!n^{−k(γ)/2}I_{n,k(γ)}((f ∘ g)_{γ}),

where ∑^{′(n)} means that summation is taken only for such coloured diagrams γ ∈

Γ(k_{1}, k_{2}) which satisfy the inequality k_{1} + k_{2} − (|Z(γ)| + |W (γ)|) ≤ n, and ∏_{j=1}^{|Z(γ)|} equals

1 in the case |Z(γ)| = 0.

The L_{2}-norm of the functions (f ∘ g)_{γ} is defined by the formula

∥(f ∘ g)_{γ}∥_{2}^{2} = ∫ (f ∘ g)_{γ}^{2}(x_{(1,j)}, x_{(2,j′)}, j ∈ {1, …, k_{1}} \ B_{u}(γ), j′ ∈ {1, …, k_{2}} \ B_{(b,1)})

∏_{(1,j): j∈{1,...,k_{1}}\B_{u}(γ)} μ( dx_{(1,j)}) ∏_{(2,j′): j′∈{1,...,k_{2}}\B_{(b,1)}} μ( dx_{(2,j′)}).

If W (γ) = 0, then the inequality

∥(f ∘ g)_{γ}∥_{2} ≤ ∥f∥_{2}∥g∥_{2}  (3.7)

holds. In the general case we can say that if the functions f and g satisfy formula (1.3), then the inequality

∥(f ∘ g)_{γ}∥_{2} ≤ 2^{|W (γ)|} min(∥f∥_{2}, ∥g∥_{2})  (3.8)

holds. Relations (3.7) and (3.8) remain valid if we drop the condition that the functions f and g are canonical.

Relations (3.7) and (3.8) mean in particular, that we have a better estimate for ∥(f ∘ g)_{γ}∥_{2} in the case when the coloured diagram γ contains no edge with colour −1, i.e. if |W (γ)| = 0, than in the case when it contains at least one edge with colour −1.

Let us understand how we define those terms at the right-hand side of (3.6) for which k(γ) = 0. In this case (f ∘g)_{γ} is a constant, and to make formula (3.6) meaningful we have to define the term I_{n,k(γ)}((f ∘ g)_{γ}) also in this case. The following convention will be used. A constant c will be called a degenerate U-statistic of order zero, and we define I_{n,0}(c) = c.

Theorem A can be considered as a version of the result of paper [9], where a similar diagram formula was proved about multiple random integrals with respect to normalized empirical measures. Degenerate U-statistics can also be presented as such integrals with special, canonical kernel functions. Hence there is a close relation between the results of this paper and [9]. But there are also some essential differences. For one part, the diagram formula for multiple random integrals with respect to normalized empirical measures is simpler than the analogous result about the product of degenerate U-statistics, because the kernel functions in these integrals need not be special, canonical functions. On the other hand, the diagram formula for degenerate U-statistics yields a simpler formula about the expected value of the product of degenerate U-statistics, because the expected value of a degenerate U-statistic of order k ≥ 1 equals zero, while the analogous result about multiple random integrals with respect to normalized empirical measures may not hold. Another difference between this paper and [9] is that here I worked out a new notation which, I hope, is more transparent.

4. The proof of Theorem A.

The proof of Theorem A. Let us consider all possible sets {(u_{1}, u′_{1}), …, (u_{l}, u′_{l})}, 1 ≤ l ≤ min(k_{1}, k_{2}) containing such pairs of integers for which u_{s} ∈ {1, …, k_{1}}, u′_{s} ∈ {1, …, k_{2}}, 1 ≤ s ≤ l, all points u_{1}, …, u_{l} are different, and the same relation holds for the points u′_{1}, …, u′_{l}, too. Let us correspond the diagram containing two rows (1, 1), …, (1, k_{1}) and (2, 1), …, (2, k_{2}) and the edges connecting the vertices (1, u_{s}) and (2, u′_{s}), 1 ≤ s ≤ l to the set of pairs {(u_{1}, u′_{1}), …, (u_{l}, u′_{l})}, and let Γ̄(k_{1}, k_{2}) denote the set of all (non-coloured) diagrams we can obtain in such a way. Let us consider the product k_{1}!I_{n,k_{1}}(f)k_{2}!I_{n,k_{2}}(g), and rewrite it in the form of the sum we get by carrying out a term by term multiplication in this expression. Let us put the terms of this sum into disjoint classes indexed by the elements of the diagrams γ̄ ∈ Γ̄(k_{1}, k_{2}) in the following way: A product f(ξ_{j_{1}}, …, ξ_{j_{k_{1}}} )g(ξ_{j′_{1}}, …, ξ_{j′_{k_{2}}} ) belongs to the class indexed by the graph γ̄ ∈ Γ̄(k_{1}, k_{2}) with edges {((1, u_{1}), (2, u′_{1})), …, ((1, u_{l}), (2, u′_{l}))} if j_{u_{s}} = j′_{u′_{s}}, 1 ≤ s ≤ l, for the indices of the random variables appearing in the above product, and no more coincidence may exist between the indices j_{1}, …, j_{k_{1}}, j′_{1}, …, j′_{k_{2}}. With such a notation we can write

n^{−k_{1}/2}k_{1}!I_{n,k_{1}}(f)n^{−k_{2}/2}k_{2}!I_{n,k_{2}}(g) = \begin{matrix}∑ & ′(n) \\ γ̄∈Γ̄ \end{matrix} n^{−(k_{1}+k_{2})/2}k̄(γ̄)!I_{n,k̄(γ̄)}(\overline{f ∘ g})γ̄), (4.1)

where the functions (\overline{f ∘ g})γ̄ are defined in formulas (3.1) and (3.4). (Observe that although formula (3.4) was defined by means of coloured diagrams, the colours played no role in it. The formula remains meaningful, and does not change if we replace the coloured diagram γ by the diagram γ̄ we get by omitting the colours of its edges.) The quantity k̄(γ̄) equals the number of such vertices of γ̄ from the first row from which no edge starts plus the number of vertices in the second row, and the notation ∑^{′(n)} means that summation is taken only for such diagrams γ̄ ∈ Γ̄ for which n ≥ k̄(γ̄).

Let the set V_{1} = V_{1}(γ̄) consist of those vertices (1, u_{1}) = (1, u_{1})_{γ}, …, (1, u_{s_{1}}) = (1, u_{s_{1}})_{γ} of the first row {(1, 1), …, (1, k_{1})} of the diagram γ̄ from which no edge starts, and let V_{2} = V_{2}(γ̄) contain those vertices (2, v_{1}) = (2, v_{1})_{γ}, …, (2, v_{s_{1}}) = (2, v_{s_{2}})_{γ} from the second row {(2, 1), …, (2, k_{2})} of γ from which no edges start. Then k̄(γ̄) = s_{1} +k_{2}, and the function (\overline{f ∘ g})γ̄ has arguments of the form x_{(1,u_{p})}, (1, u_{p}) ∈ V_{1} and x_{(2,v)}, 1 ≤ v ≤ k_{2}.

Relation (4.1) is not appropriate for our goal, since the functions (\overline{f ∘ g})γ̄ in it may be non-canonical. Hence we apply Hoeffding’s decomposition for the U-statistics I_{n,k̄(γ̄)}(\overline{f ∘ g})γ̄ in formula (4.1) to get the desired representation for the product of degenerate U-statistics. Actually some special properties of the function (\overline{f ∘ g})γ̄ enable us to simplify a little bit this decomposition. (The Hoeffding decomposition is a simple but important result which gives an explicit method to rewrite a general U-statistic in the form of sums of degenerate U-statistics. It has an equivalent reformulation by which an arbitrary (kernel) function of several variables can be rewritten as the sum of canonical functions with different number of variables. It has a concise explanation for instance in the Appendix of [4]. In the subsequent considerations I write down what this result yields in the present situation.)

To carry out this procedure let us observe that a function f(x_{u_{1}}, …, x_{u_{k}}) is canonical if and only if P_{u_{l}}f(x_{u_{1}}, …, x_{u_{k}}) = 0 with the operator P_{u_{l}} defined in (3.2) for all indices u_{l}. Beside this, the condition that the functions f and g are canonical implies the relations P_{(1,u)}(\overline{f ∘ g})γ̄ = 0 for (1, u) ∈ V_{1} and P_{(2,v)}(\overline{f ∘ g})γ̄ = 0 for (2, v) ∈ V_{2}. Moreover, these relations remain valid if we replace the functions (\overline{f ∘ g})γ̄ by such functions which we get by applying the product of some transforms P_{(2,v)} and Q_{(2,v)}, (2, v) ∈ {(2, 1), …, (2, k_{2})} \ V_{2} for them with the transforms P and Q defined in formulas (3.2) and (3.3). (Here we applied such transforms P and Q which are indexed by those vertices of the second row of γ̄ from which some edge starts.)

Beside this, the transforms P_{(2,v)} or Q_{(2,v)} are exchangeable with the operators P_{(2,v′)} or Q_{(2,v′)} if v ≠ v′, P_{(2,v)} + Q_{(2,v)} = I, where I denotes the identity operator, and P_{(2,v)}Q_{(2,v)} = 0, since P_{(2,v)}Q_{(2,v)} = P_{(2,v)} − P_{(2,v)}^{2} = 0. The above relations enable us to make the following decomposition of the function (\overline{f ∘ g})γ̄ to the sum of canonical functions (just as it is done in the Hoeffding decomposition): Let us introduce the class of those coloured diagram Γ(γ̄) which we can get by colouring all edges of the diagram γ either with colour 1 or colour −1. Some calculation shows that

(\overline{f ∘ g})γ̄ = (  ∏_{(2,v)∈\{(2,1),...,(2,k_{2})\}\V_{2}}(P_{(2,v)} + Q_{(2,v)})) (\overline{f ∘ g})γ̄ = ∑_{γ∈Γ(γ̄)}(f ∘ g)_{γ}, (4.2)

where the function (f ∘ g)_{γ} is defined in formula (3.5). We get the right-hand side of relation (4.2) by carrying out the multiplications for the middle term of this expression, and exploiting the properties of the operators P_{(2,v)} and Q_{(2,v)}. Moreover, these properties also imply that the functions (f ∘g)_{γ} are canonical functions of their variables x_{(1,u)}, (1, u) ∈ V_{1} and x_{(2,v)}, (2, v) ∈ B_{(b,−1)}(γ) ∪ V_{2}. Indeed, the above properties of the operators P_{(2,v)} and Q_{(2,v)} imply that P_{(1,u)}(f ∘ g)_{γ} = 0 if (1, u) ∈ V_{1}, and P_{(2,v)}(f ∘ g)_{γ} = 0 if (2, v) ∈ B_{(b,−1)}(γ) ∪ V_{2}.

Let Z(γ) denote the set of edges of colour 1, W (γ) the set of edges of colour −1 in the coloured diagram γ, and let |Z(γ)| and W (γ)| be their cardinality. Then (f ∘ g)_{γ} is a (canonical) function with k(γ) = k_{1} + k_{2} − (|W (γ)| + 2|Z(γ)|) variables, and formula (4.2) implies the following representation of the U-statistic I_{n,k̄(γ̄)} (\overline{f ∘ g})γ̄) in the form of a sum of degenerate U-statistics:

\begin{matrix}n^{−(k_{1}+k_{2})/2}k̄(γ̄)!I_{n,k̄(γ̄)} ((\overline{f ∘ g})γ̄) \\ = n^{−(k_{1}+k_{2})/2} ∑_{γ∈Γ(γ̄)} J_{n}(γ)n^{|Z(γ)|}k(γ)!I_{n,k(γ)} ((f ∘ g)_{γ}) \end{matrix}  (4.3)

with J_{n}(γ) = 1 if |Z(γ)| = 0, and

J_{n}(γ) = \frac{∏_{j=1}^{|Z(γ)|}(n − (k_{1} + k_{2}) + |W (γ)| + |Z(γ)| + j)}{n^{|Z(γ)|}} if |Z(γ)| > 0.

The coefficient J_{n}(γ)n^{|Z(γ)|} appeared in formula (4.3), since if we apply the decomposition (4.2) for all terms (\overline{f ∘ g})γ̄(ξ_{j_{(1,u)}}, ξ_{j_{(2,v)}}, (1, u) ∈ V_{1}, (2, v) ∈ \{1, … k_{2}\}) of the Ustatistic k̄(γ̄)!I_{n,k(γ̄)} ((\overline{f ∘ g})γ̄), then each term (f ∘g)_{γ}(ξ_{j_{(1,u)}}, ξ_{j_{(2,v)}}, (1, u) ∈ V_{1}, (2, v) ∈ V_{2} ∪ V_{1}) of the U-statistic I_{n,k(γ)} ((f ∘ g)_{γ}) appears J_{n}(γ)n^{|Z(γ)|} times. (This is so, because k̄(γ) = k_{1} +k_{2} −(|W (γ)|+2|Z(γ)|) variables are fixed in the term (f ∘g)_{γ} from the k(γ̄) = k_{1}+k_{2}−(|W (γ)|+|Z(γ)|) variables in the term (\overline{f ∘ g})γ̄, and to get formula (4.3) from formula (4.2) the indices of the remaining |Z(γ)| variables can be freely chosen from the indices 1, …, n, with the only restriction that all indices must be different.)

Formula (3.6) follows from relations (4.1) and (4.3). (To see that we wrote the right power of n in this formula observe that n^{−(k_{1}+k_{2})/2}n^{|Z(γ)|} = n^{−k(γ)/2}n^{−|W (γ)|/2}.)

To prove inequality (3.7) in the case |W (γ)| = 0 let us estimate first the value of the function (f ∘ g)_{γ}^{2}(x_{(1,u)}, x_{(2,v)}, (1, u) ∈ V_{1}, (2, v) ∈ V_{2}) by means of the Schwarz inequality. We get that

(f ∘ g)_{γ}^{2}(x_{(1,u)}, x_{(2,v)}, (1, u) ∈ V_{1}, (2, v) ∈ V_{2})

≤ ∫ f^{2}(x_{(1,u)}, x_{(2,v)}, (1, u) ∈ V_{1}, (2, v) ∈ B_{(b,1)}(γ)) ∏_{(2,v)∈B_{(b,1)}(γ)} μ( dx_{(2,v)})

∫ g^{2}(x_{(2,v)}, (2, v) ∈ V_{2} ∪ B_{(b,1)}(γ),) ∏_{(2,v)∈B_{(b,1)}(γ)} μ( dx_{(2,v)})

= ∏_{(2,v)∈B_{(b,1)}(γ)} P_{(2,v)}f^{2}(x_{(1,u)}, x_{(2,v)}, (1, u) ∈ V_{1}, (2, v) ∈ B_{(b,1)}(γ))

∏_{(2,v)∈B_{(b,1)}(γ)} P_{(2,v)}g^{2}(x_{(2,v)}, (2, v) ∈ V_{2} ∪ B_{(b,1)}(γ))

(4.4)

with the operators P defined in formula (3.2).

Let us observe that the two functions at the right-hand side of (4.4) are functions of different arguments. The first of them depends on the arguments x_{(1,u)}, (1, u) ∈ V_{1}, the second one on the arguments x_{(2,v)}, (2, v) ∈ V_{2}. Beside this, as the operators P appearing in their definition are contraction in L_{1}-norm, these functions are bounded in L_{1} norm by ∥f∥_{2}^{2} and ∥g∥_{2}^{2} respectively. Because of the above relations we get formula (3.7) by integrating inequality (4.4) and applying Fubini’s theorem.

To prove inequality (3.8) let us introduce, similarly to formula (3.3), the operators

Q̃_{u_{j}}h(x_{u_{1}}, …, x_{u_{r}}) = h(x_{u_{1}}, …, x_{u_{r}}) + ∫ h(x_{u_{1}}, …, x_{u_{r}})μ( dx_{u_{j}}), 1 ≤ j ≤ r,

in the space of functions h(x_{u_{1}}, …, x_{u_{r}}) with coordinates in the space (X, X). (The indices u_{1}, …, u_{r} are all different.) Observe that both the operators Q̃_{u_{j}} and the operators P_{u_{j}} defined in (3.2) are positive, i.e. these operators map a non-negative function to a non-negative function. Beside this, Q_{u_{j}} ≤ Q̃_{u_{j}}, i.e. Q̃_{u_{j}} − Q_{u_{j}} is a non-negative operator, and the norms of the operators \frac{Q̃_{u_{j}}}{2} and P_{u_{j}} are bounded by 1 both in the L_{1}(μ), the L_{2}(μ) and the supremum norm.

Let us define the function

(f̃ ∘ g)_{γ} (x_{(1,j)}, x_{(2,j′)}, j ∈ {1, …, k_{1}} \ B_{u}(γ), j′ ∈ {1, …, k_{2}} \ B_{(b,1)})

= ∏_{(2,j′)∈B_{(b,1)}(γ)} P_{(2,j′)} ∏_{(2,j′)∈B_{(b,−1)}(γ)} Q̃_{(2,j′)}
\overline{(f ∘ g)}_{γ} (x_{(j,1)}, x_{(j′,2)}, j ∈ \{1, …, k_{1}\} \ B_{u}(γ), 1 ≤ j′ ≤ k_{2})

with the notation of Section 3. We have defined the function (f̃ ∘ g)_{γ} with the help of \overline{(f ∘ g)}_{γ} similarly to the definition of (f ∘ g)_{γ} in (3.5), only we have replaced the operators Q_{(2,j′)} by Q̃_{(2,j′)} in it.

We may assume that ∥g∥_{2} ≤ ∥f∥_{2}. We can write because of the properties of the operators P_{u_{j}} and Q̃_{u_{j}} listed above and the condition sup |f(x_{1}, …, x_{k})| ≤ 1 that

|(f ∘ g)_{γ}| ≤ ( ˜ |f| ∘ |g|)_{γ} ≤ ( ˜ 1 ∘ |g|)_{γ},  (4.5)

where ‘≤’ means that the function at the right-hand side is greater than or equal to the function at the left-hand side in all points, and 1 denotes the function which equals identically 1. Because of relation (4.5) to prove relation (3.8) it is enough to show that

\begin{aligned}∥( ˜ 1 ∘ |g|)_{γ}∥_{2} & = ∥  ∏_{(2,j)∈B_{(b,1)}(γ)} P_{(2,j)} ∏_{(2,j)∈B_{(b,−1)}(γ)} Q̃_{(2,j)} |g(x_{(2,1)}, …, x_{(2,k_{2})})|∥_{2} \\ & ≤ 2^{|W (γ)|}∥g∥_{2}. \end{aligned} (4.6)

But this inequality trivially holds, since the norm of all operators P_{(2,j)} in formula (4.6) is bounded by 1, the norm of all operators Q̃_{(2,j)} is bounded by 2 in the L_{2}(μ) norm, and |B_{(b,−1)}| = |W (γ)|.

5. The diagram formula for the product of several degenerate U-statistics.

The product of more than two degenerate U-statistics can also be expressed in the form of a sum of degenerate U-statistics by means of a recursive application of Theorem A. We shall present this result in Theorem B and prove it together with an estimate about the L_{2}-norm of the kernel functions of the degenerate U-statistics appearing in Theorem B. This estimate will be given in Theorem C. Since the expected value of all degenerate U-statistics of order k ≥ 1 equals zero, the representation of the product of U-statistics in the form of a sum of degenerate U-statistics implies that the expected value of this product equals the sum of the constant terms in this representation. In such a way we get a formula for the expected value of a product of degenerate U-statistics which together with Theorem C will be sufficient to prove Proposition A. But the formula we get in this way is more complicated than the analogous diagram formula for products of Wiener–Itô integrals. To overcome this difficulty we have to work out a good “bookkeeping method”.

Let us have a sequence of iid. random variables ξ_{1}, ξ_{2}, … taking values on a measurable space (X, X) with some distribution μ, and consider L functions f_{l}(x_{1}, …, x_{k_{l}}) on the measure spaces (X^{k_{l}}, X^{k_{l}}), 1 ≤ l ≤ L, canonical with respect to the measure μ. We want to represent the product of L ≥ 2 normalized degenerate U-statistics n^{−k_{l}/2}k_{l}!I_{n,k_{l}}(f_{k_{l}}) in the form of a sum of degenerate U-statistics similarly to Theorem A. For this goal I define a class of coloured diagrams Γ(k_{1}, …, k_{L}) together with some canonical functions F_{γ} = F_{γ}(f_{k_{1}}, …, f_{k_{L}}) depending on the diagrams γ ∈ Γ(k_{1}, …, k_{L}) and the functions f_{l}(x_{1}, …, x_{k_{l}}), 1 ≤ l ≤ L.

The coloured diagrams will be graphs with vertices (l, j) and (l, j, C), 1 ≤ l ≤ L, 1 ≤ j ≤ k_{l}, and edges between some of these vertices which will get either colour 1 or colour −1. The set of vertices {(l, j), (l, j, C), 1 ≤ j ≤ k_{l}} will be called the l-th row of the diagrams. (The vertices (l, j, C) are introduced, because it turned out to be useful to take a copy (l, j, C) of some vertices (l, j). The letter C was chosen to indicate that it is a copy.) From all vertices there starts either zero or one edge, and edges may connect only vertices in different rows. We shall call all vertices of the form (l, j) permissible, and beside this some of the vertices (l, j, C) will also be called permissible. Those vertices will be called permissible from which some edge may start.

We shall say that an edge connecting two vertices (l_{1}, j_{1}) with (l_{2}, j_{2}) or (a permissible) vertex (l_{1}, j_{1}, C) with another vertex (l_{2}, j_{2}) such that l_{2} > l_{1} is of level l_{2}, and (l_{2}, j) will be called the lower end-point of such an edge. (The coloured diagrams we shall define contain only edges with lower end-points of the form (l, j).) We shall call the restriction γ(l) of the diagram γ to level l that part of a diagram γ which contains all of its vertices together with those edges (together with their colours) whose levels are less than or equal to l, and tells which of the vertices (l′, j, C) are permissible for 1 ≤ l′ ≤ l. We shall define the diagrams γ ∈ Γ(k_{1}, …, k_{L}) inductively by defining their restrictions γ(l) to level l for all l = 1, 2, …, L. Those diagrams γ will belong to Γ(k_{1}, …, k_{L}) whose restrictions γ(l) can be defined through the following procedure for all l = 1, 2, …, L.

The restriction γ(1) of a diagram γ to level 1 contains no edges, and no vertex of the form (1, j, C), 1 ≤ j ≤ k_{1}, is permissible. If we have defined the restrictions γ(l − 1) for some 2 ≤ l ≤ L, then those diagrams will be called restrictions γ(l) at level l which can be obtained from a restriction γ(l − 1) in the following way: Take the vertices (l, j), 1 ≤ j ≤ k_{l}, from the l-th row. From each of these vertices there starts either zero or one edge, and they get either colour 1 or colour −1. The other end-point of these edges must be such a vertex (l′, j′) or a permissible vertex (l′, j′, C) with some 1 < l′ < l which is not an end-point of a vertex in γ(l − 1). We define γ(l) first by adjusting the coloured edges constructed in the above way to the (coloured) edges of γ(l − 1), and then defining the set of permissible vertices in γ(l). It contains beside the permissible vertices of γ(l − 1) and the vertices (l, j), 1 ≤ j ≤ k_{l}, those vertices (l, j, C) for which (l, j) is the lower end-point of an edge with colour −1 in γ(l). Γ(k_{1}, …, k_{L}) will consist of all coloured diagrams γ = γ(L) obtained in such a way.

Given a coloured diagram γ ∈ Γ(k_{1}, …, k_{L}) we shall define recursively some (canonical) functions F_{l,γ} with the help of the functions f_{1}, …, f_{l} for all 1 ≤ l ≤ L in the way suggested by Theorem A. Then we put F_{γ} = F_{L,γ} and give the desired representation of the product of the degenerate U-statistics with the help of U-statistics with kernel functions F_{γ} and constants J_{n}(l, γ), γ ∈ Γ(k_{1}, …, k_{L}), 1 ≤ l ≤ L.

Let us fix some coloured diagram γ ∈ Γ(k_{1}, …, k_{L}) and introduce the following notations: Let B_{(b,−1)}(l, γ) denote the set of lower end-points of the form (l, j) of edges with colour −1 and B_{(b,1)}(l, γ) the set of lower end-points of the form (l, j) with colour 1. Let U(l, γ) denote the set of those permissible vertices (l′, j) and (l′, j, C) with l′ ≤ l from which no edge starts in the restriction γ(l) of the diagram γ to level l, i.e. either no edge starts from this vertex, or if some edge starts from it, then its other end-point is a vertex (l′, j) with l′ > l. Beside this, given some integer 1 ≤ l_{1} < l let U(l, l_{1}, γ) denote the restriction of U(l, γ) to its first l_{1} rows, i.e. U(l, l_{1}, γ) consists of those vertices (l′, j) and (l′, j, C) which are contained in U(l, γ), and l′ ≤ l_{1}. We shall define the functions F_{l}(γ) with arguments of the form x_{(l′,j)} and x_{(l′,j,C)} with (l′, j) ∈ U(l, γ) and (l′, j, C) ∈ U(l, γ). For this end put first

F_{1,γ}(x_{(1,1)}, …, x_{(k_{1},1)}) = f_{1}(x_{(1,1)}, …, x_{(k_{1},1)}).  (5.1)

To define the function F_{l,γ} for l ≥ 2 first we introduce a function α_{l,γ}(·) on the set of vertices in U(l − 1, γ) in the following way. If a vertex (l′, j′) or (l′, j′, C) in U(γ, l − 1) is such that it is connected to no vertex (l, j), 1 ≤ j ≤ k_{l}, then α_{l,γ}(l′, j′) = (l′, j′), α_{l,γ}(l′, j′, C) = (l′, j′, C) and if (l′, j′) is connected to a vertex (l, j), then α_{l,γ}(l′, j′) = (l, j), if (l′, j′, C) is connected with a vertex (l, j), then α_{l,γ}(l′, j′, C) = (l, j). We define, similarly to the formula (3.4) the functions

\begin{matrix}F̄_{l,γ}(x_{(l′,j′)}, x_{(l′,j′,C)}, (l′, j′) and (l′, j′, C) ∈ U(l, l − 1, γ), x_{(l,j)}, 1 ≤ j ≤ k_{l}) \\ = F_{l−1,γ}(x_{α_{l,γ}(l′,j′)}, x_{α_{l,γ}(l′,j′,C)}, (l′, j′) and (l′, j′, C) ∈ U(l − 1, γ)) \\ f_{l}(x_{(l,1)}, …, x_{(l,k_{l})}), \end{matrix} (5.2)

i.e. we take the function F_{l−1,γ} ∘ f_{l} and replace the arguments of this function indexed by such a vertex of γ which is connected by an edge with a vertex in the l-th row of γ by the argument indexed with the lower end-point of this edge.

Then we define with the help of the operators P_{u_{j}} and Q_{u_{j}} introduced in (3.2) and (3.3) the functions

¯F̄_{l,γ}(x_{(l′,j′)}, x_{(l′,j′,C)}, (l′, j′) and (l′, j′, C) ∈ U(l, l − 1, γ), x_{(l,j)}, j ∈ {1, …, k_{l}} \ B_{(l,1)}(l, γ))

= ∏_{(l,j)∈B_{(b,1)}(l,γ)} P_{(l,j)} ∏_{(l,j)∈B_{(b,−1)}(l,γ)} Q_{(l,j)}

F̄_{l,γ}(x_{(l′,j′)}, x_{(l′,j′,C)}, (l′, j′) and (l′, j′, C) ∈ U(l, l − 1, γ), x_{(l,j)}, 1 ≤ j ≤ k_{l}),

(5.3)

similarly to the formula (3.5), i.e. we apply for the function F̄_{l}(γ) the operators P_{(l,j)} for those indices (l, j) which are the lower end-points of an edge with colour 1 and the operators Q_{(l,j)} for those indices (l, j) which are the lower end-points of an edge with colour −1.

Finally we define the function F_{l,γ} simply by reindexing some arguments of the function ¯ F̄_{l,γ} to get a function which is indexed by the vertices in U(l, γ). To this end we define the function A_{l,γ}(·) on the set of vertices {(l, j): (l, j) ∈ {(l, 1), …, (l, k_{l})} \ B_{(b,1)}(l, γ) as A_{l,γ}(l, j) = (l, j, C) if (l, j) ∈ B_{(b,−1)}(l, γ), and A_{l,γ}(l, j) = (l, j) if (l, j) ∈ {(l, 1), …, (l, k_{l})} \ (B_{(b,1)}(l, γ) ∪ B_{(b,−1)}(l, γ)). Then we put

\begin{matrix}F_{l,γ}(x_{(l′,j′)}, x_{(l′,j′,C)}, (l′, j′) and (l′, j′, C) ∈ U(l, γ)) \\ = ¯ F̄_{l,γ}(x_{(l′,j′)}, x_{(l′,j′,C)}, (l′, j′) and (l′, j′, C) ∈ U(l, l − 1, γ), \\ x_{A_{l,γ}(l,j)}, (l, j) ∈ \{(l, 1), …, (l, k_{l})\} \ B_{(b,1)}(l, γ)). \end{matrix}  (5.4)

Now we can formulate the following generalization of Theorem A.

Theorem B. Let us have a sequence of iid. random variables ξ_{1}, ξ_{2}, … with some distribution μ on a measurable space (X, X) together with L ≥ 2 bounded functions f_{l}(x_{1}, …, x_{k_{l}}) on the spaces (X^{k_{l}}, X^{k_{l}}), 1 ≤ l ≤ L, canonical with respect to the probability measure μ. Let us introduce the class of coloured diagrams Γ(k_{1}, …, k_{L}) defined above together with the functions F_{γ} = F_{L,γ}(f_{1}, …, f_{L}) defined in formulas (5.1)— (5.4).

Put k(γ(l)) = ∑_{p=1}^{l} k_{p} − ∑_{p=2}^{l}(2|B_{(b,1)}(p, γ)| + |B_{(b,−1)}(p, γ)|), where |B_{(b,1)}(p, γ)| de-

notes the number of lower end-points in the p-th row of γ with colour 1 and |B_{(b,−1)}(p, γ)| is the number of lower end-points in the p-th row of γ with colour −1, 1 ≤ l ≤ L, and define k(γ) = k(γ(L)). Then k(γ(l)) is the number of variables of the function F_{l,γ}, 1 ≤ l ≤ L.

The functions F_{γ} are canonical with respect to the measure μ with k(γ) variables, and the product of the degenerate U-statistics I_{n,k_{l}}(f), n ≥ max_{1≤l≤L} k_{l}, defined in (1.1)

satisfies the identity

∏_{l=1}^{L} k_{l}!n^{−k_{l}/2}I_{n,k_{l}}(f_{k_{l}}) = \begin{matrix}∑ & ′(n, L ) \\ γ∈Γ(k_{1},...,k_{L}) \end{matrix} (∏_{l=1}^{L} J_{n}(l, γ)) n^{−|W (γ)|/2}·k(γ)!n^{−k(γ)/2}I_{n,k(γ)}(F_{γ}),

(5.5) where |W (γ)| = ∑_{l=2}^{L} |B_{(b,−1)}(l, γ)| is the number of edges with colour −1 in the coloured

diagram γ, and ∑^{′(n, L)} means that summation is taken for those γ ∈ Γ(k_{1}, …, k_{L}) which satisfy the relation k(γ(l − 1)) + k_{l} − (|B_{(b,1)}(l, γ)| + |B_{(b,−1)}(l, γ)|) ≤ n for all 2 ≤ l ≤ L. Beside this, the constants J_{n}(l, γ), 1 ≤ l ≤ L, in formula (5.5) are defined by the relations J_{n}(1, γ) = 1, and

J_{n}(l, γ) = \frac{∏_{j=1}^{|B_{(b,1)}(l,γ)|}(n − (k(γ(l − 1)) + k_{l}) + |B_{(b,−1)}(l, γ)| + |B_{(b,1)}(l, γ)| + j)}{n^{|B_{(b,1)}(l,γ)|}}, (5.6)

2 ≤ l ≤ L, if |B_{(b,1)}(l, γ)| ≥ 1, and J_{n}(l, γ) = 1 if |B_{(b,1)}(l, γ)| = 0, where |B_{(b,1)}(l, γ)| and |B_{(b,−1)}(l, γ)| denote the number of those edges in γ with colour 1 and with colour −1 respectively whose lower end-points are in the l-th row of γ.

Let Γ̄(k_{1}, …, k_{L}) denote the class of those coloured diagrams of Γ(k_{1}, …, k_{L}) for which every permissible vertex is the end-point of some edge. A coloured diagram γ ∈ Γ(k_{1}, …, k_{L}) satisfies the relation γ ∈ Γ̄(k_{1}, …, k_{L}) if and only if k(γ) = 0. In this case F_{γ} is constant, and I_{n,k(γ)}(F_{γ}) = F_{γ}. For all other coloured diagrams γ ∈ Γ(k_{1}, …, k_{L}) k(γ) ≥ 0. The identity

E (∏_{l=1}^{L} k_{l}!n^{−k_{l}/2}I_{n,k_{l}}(f_{k_{l}})) = \begin{matrix}∑ & ′(n, L ) \\ γ∈Γ̄(k_{1},...,k_{L}) \end{matrix} (∏_{l=1}^{L} J_{n}(l, γ)) n^{−|W (γ)|/2} · F_{γ}  (5.7)

holds.

Theorem B can be deduced relatively simply from Theorem A by induction with respect to the number L of the functions. Theorem A contains the results of Theorem B in the case L = 2. A simple induction argument together with the formulas describing the functions F_{l,γ} by means of the functions F_{l−1,γ} and f_{l} and Theorem A imply that all functions F_{γ} in Theorem B are canonical. Finally, an inductive procedure with respect to the number L of the functions f_{l} shows that relation (5.5) holds. Indeed, by exploiting that formula (5.5) holds for the product of the first L − 1 degenerate U-statistics, then multiplying this identity with the last U-statistic and applying for each term at the right-hand side Theorem A we get that relation (5.5) also holds for the product L degenerate U-statistics.

A simple inductive procedure with respect to l shows that for all 2 ≤ l ≤ L

the diagram γ(l) contains k(γ(l)) = ∑_{p=1}^{l} k_{l} − ∑_{p=2}^{l}(2|B_{(b,1)}(p, γ)| + |B_{(b,−1)}(p, γ)|) per-

missible vertices in its first l rows which are not an end-point of an edge in γ(l). In particular, k(γ) = 0 if and only if γ ∈ Γ̄(k_{1}, …, k_{L}) with the class of coloured diagrams Γ̄(k_{1}, …, k_{L}) introduced at the end of Theorem B. Since EI_{n,k}(f) = 0 for all degenerate U-statistics of order k ≥ 1, this property together with relation (5.5) imply identity (5.7).

In the proof of Proposition A we shall also need an estimate formulated in Theorem C. It is a simple consequence of inequalities (3.7) and (3.8) in Theorem A.

Theorem C. Let us have L functions f_{l}(x_{1}, …, x_{k_{l}}) on the spaces (X^{k_{l}}, X^{k_{l}}), 1 ≤ l ≤ L, which satisfy formulas (1.3) and (1.4) (if we replace the index k by index k_{l} in these formulas), but these functions need not be canonical. Let us take a coloured diagram γ ∈ Γ(k_{1}, …, k_{L}) and consider the function F_{γ} = F_{L,γ}(f_{1}, …, f_{L}) defined by formulas (5.1)—(5.5). The L_{2}-norm of the function F_{γ} (with respect to a power of the measure μ to the space, where F_{γ} is defined) satisfies the inequality ∥F_{γ}∥_{2} ≤ 2^{|W (γ)|}σ^{(L−U(γ))}, where |W (γ)| denotes the number of edges of colour −1, and U(γ) the number of rows which contain the lower vertex of an edge of colour −1 in the coloured diagram γ.

Proof of Theorem C. We shall prove the inequality

∥F_{l,γ}∥_{2} ≤ 2^{|W (l,γ)|}σ^{(l−U(l,γ))} for all 1 ≤ l ≤ L,  (5.8)

where |W (l, γ)| denotes the number of edges with colour 1, and U(l, γ) is the number of rows containing a lower point of an edge with colour −1 in the coloured diagram γ(l). Formula (5.8) will be proved by means of induction with respect to l. It implies Theorem C with the choice l = L.

Relation (5.8) clearly holds for l = 1. To prove this relation by induction with respect to l for all 1 ≤ l ≤ L let us first observe that sup 2^{−|W (l,γ)|}|F_{l,γ}| ≤ 1 for all 1 ≤ l ≤ L. This relation can be simply checked by induction with respect to l.

If we know relation (5.8) for l − 1, then it follows for l from relation (3.7) if |B_{(b,−1)}(l, γ)| = 0, that is if there is no edge of colour −1 with lower end-point in the l-th row. Indeed, in this case ∥F_{l,γ}(f_{1}, …, f_{l})∥_{2} ≤ ∥F_{l−1,γ}∥_{2}∥f_{l}∥_{2} ≤ ∥F_{l−1,γ}(f_{1}, …, f_{l−1})∥_{2} · σ, |W (l, γ)| = |W (l − 1, γ)|, and U(l, γ) = U(l − 1, γ). Hence relation (5.8) holds in this case.

If |B_{(b,−1)}(l, γ)| ≥ 1, then we can apply formula (3.8) for the expression ∥F_{l,γ}∥_{2} = ∥ ¯F̄_{l,γ}∥_{2} = ∥(F_{l−1,γ} ∘ f_{l})_{γ̃(l)}∥_{2}, where γ̃(l) is that coloured diagram with two rows whose first row consists of the indices of the variables of the function F_{l−1,γ}, its second row consists of the vertices (l, j), 1 ≤ j ≤ k_{l}, and γ̃(l) contains the edges of γ between these vertices together with their colour. Then relation (3.8) implies that ∥F_{l,γ}∥_{2} ≤ 2^{|B_{(b,−1)}|}∥F_{l−1,γ}∥_{2} ≤ 2^{(|W (l−1,γ)|+|B_{(b,−1)}(l,γ)|)}σ^{(l−1−U(l−1,γ))} if |B_{(b,−1)}(l, γ)| ≥ 1. Beside this, |W (l − 1, γ)| + |B_{(b,−1)}(l, γ)| = |W (l, γ)|, and l − 1 − U(l − 1, γ) = l − U(l, γ) in this case. Hence relation (5.8) holds in this case, too.

6. The proof of Proposition A.

Proof of Proposition A. We shall prove relation (2.1) by means of identity (5.7) and Theorem C with the choice L = 2M and f_{l}(x_{1}, …, x_{k_{l}}) = f(x_{1}, …, x_{k}) for all 1 ≤ l ≤ 2M. We shall partition the class of coloured diagrams γ ∈ Γ(k, M) = Γ̄(\underbrace{k, …, k}_{2M times})

with the property that all permissible vertices are the end-points of some edge to classes Γ(k, M, p), 1 ≤ p ≤ M, in the following way: γ ∈ Γ(k, M, p) for a coloured diagram γ ∈ Γ(k, M) if and only if it has 2p permissible vertices of the form (l, j, C). (A coloured diagram γ ∈ Γ(k, M) has even number of such vertices.) First we prove the following estimate:

There exists some constant A = A(k) > 0 and threshold index M_{0} = M_{0}(k) such that for all M ≥ M_{0} and 0 ≤ p ≤ kM the cardinality |Γ(k, M, p)| of the set Γ(k, M, p) can be bounded from above by A2^{2p}\binom{2kM}{2p} (\frac{2}{e})^{kM} (kM)^{kM+p}.

We can bound the number of coloured diagrams in Γ(k, M, p) by calculating first the number of choices of the 2p permissible vertices from the 2kM vertices of the form (l, j, C) which we adjust to the 2kM permissible vertices (l, j) and then by calculating the number of such graphs whose vertices are the above chosen permissible vertices, and from all vertices there starts exactly one edge. (Here we allow to connect vertices from the same row. Observe that by defining the set of permissible vertices (l, j, C) in a coloured diagram γ we also determine the colouring of its edges.) Thus we get that |Γ(k, M, p)| can be bounded from above by \binom{2kM}{2p}1 · 3 · 5 ⋯ (2kM + 2p − 1) =

\binom{2kM}{2p} \frac{(2kM+2p)!}{2^{kM+p}(kM+p)!}. (The appearance of the factor 1 · 3 · 5 ⋯ (2kM + 2p − 1) in this estimate can be explained in a standard way. Let us list the 2kM + 2p vertices in some order. The first vertex can be connected with 2kM + 2p − 1 vertices by an edge. Then the first vertex from which no edge starts can be connected with 2kM + 2p − 3 vertices. Continuing this procedure we get the above product for the number of possible system of edges between the already fixed vertices.) We can write by the Stirling formula, similarly to the estimation of the right-hand side of formula (2.2) that \frac{(2kM+2p)!}{2^{kM+p}(kM+p)!} ≤

A (\frac{2}{e})^{kM+p} (kM + p)^{kM+p} with some constant A > \sqrt{2} if M ≥ M_{0} with some M_{0} = M_{0}(A). Since p ≤ kM we can write (kM + p)^{kM+p} ≤ (kM)^{kM} (1 + \frac{p}{kM} )^{kM} (2kM)^{p} ≤ (kM)^{kM+p}e^{p}2^{p}. The above inequalities imply that

|Γ(k, M, p)| ≤ A\binom{2kM}{2p} (\frac{2}{e})^{kM} (kM)^{kM+p}2^{2p} if M ≥ M_{0},  (6.1)

as we have claimed.

Observe that for γ ∈ Γ(k, M, p) the quantities introduced in the formulation of Theorems B and C satisfy the relations |W (γ)| = 2p, |F_{γ}| = ∥F_{γ}∥_{2} and U(γ) ≤ |W (γ)| = 2p. Hence by Theorem C we have n^{−|W (γ)|/2}|F_{γ}| ≤ 2^{p}n^{−p}σ^{2M−U(γ)} ≤ 2^{p} (nσ^{2})^{−p} σ^{2M} ≤ η^{p}2^{p}(kM)^{−p}σ^{2M} if kM ≤ ηnσ^{2} and σ^{2} ≤ 1.

This estimate together with relation (5.7) and the fact that the constants J_{n}(l, γ) defined in (5.6) are bounded by 1 imply that for kM ≤ ηnσ^{2}

E (n^{−k/2}k!I_{n,k}(f_{k}))^{2M} ≤ ∑_{γ∈Γ(k,M)} n^{−|W (γ)|/2} · |F_{γ}| ≤ ∑_{p=0}^{kM} |Γ(k, M, p)|η^{p}2^{p}(kM)^{−p}σ^{2M}.

Hence by formula (6.1)

E (n^{−k/2}k!I_{n,k}(f_{k}))^{2M} ≤ A (\frac{2}{e})^{kM} (kM)^{kM}σ^{2M} ∑_{p=0}^{kM} \binom{2kM}{2p} (2\sqrt{2η})^{2p}

≤ A (\frac{2}{e})^{kM} (kM)^{kM}σ^{2M} (1 + 2\sqrt{2η})^{2kM}

if kM ≤ ηnσ^{2}. Thus we have proved Proposition A with C = 2\sqrt{2}.

References.

1.) Adamczak, R. (2006) Moment inequalities for U-statistics. Annals of Probability

34 2288–2314 2.) Arcones, M. A. and Giné, E. (1993) Limit theorems for U-processes. Annals of

Probability 21, 1494–1542 3.) Dudley, R. M. (1998) Uniform Central Limit Theorems. Cambridge University

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

and multiple Wiener integrals. Annals of Statistics 11, 739–745 5.) Giné, E., Latała, R. and Zinn, J. (2000) Exponential and moment inequalities for

U-statistics in High dimensional probability II. Progress in Probability 47. 13–38. Birkhäuser Boston, Boston, MA.

6.) Itô, K. (1951) Multiple Wiener integral. J. Math. Soc. Japan 3. 157–164 7.) Latała, R. (2006) Estimates of moments and tails of Gaussian chaoses. Annals of

Probability 34 2315–2331 8.) Major, P. (1981) Multiple Wiener–Itô integrals. Lecture Notes in Mathematics

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

a normalized empirical measure. Studia Scientarum Mathematicarum Hungarica. 42 3. 295–341

10.) Major, P. (2005) Tail behaviour of random multiple random integrals and U-

statistics. Probability Reviews, Vol. 2, 448–505 11.) Major, P. (2006) A multivariate generalization of Hoeffding’s inequality. Electron.

Comm. Probab. 2 220–229