A MULTIVARIATE GENERALIZATION OF HOEFFDING’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: In this paper a multivariate version of Hoeffding’s inequality is proved about the tail distribution of homogeneous polynomials of Rademacher functions with an optimal constant in the exponent of the upper bound. The proof is based on an estimate about the moments of homogeneous polynomials of Rademacher functions which can be considered as an improvement of Borell’s inequality in a most important special case.

1. Introduction. Formulation of the main result.

This paper contains a multivariate version of Hoeffding’s inequality. Hoeffding’s inequality has the following form. (see e. g. [3], Proposition 1.3.5.)

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

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

P (Z > u) ≤ exp \{−\frac{u^{2}}{2V^{2}} \} for all u > 0.  (1.1)

To formulate its multivariate version first some notations will be introduced. Let us fix two positive integers k and n, n ≥ k, and some real numbers a(j_{1}, …, j_{k})

for all sets of arguments {j_{1}, …, j_{k}} such that 1 ≤ j_{l} ≤ n, 1 ≤ l ≤ k, and j_{l} ≠ j_{l′} if l ≠ l′ in such a way that the numbers a(j_{1}, …, j_{k}) are symmetric functions of their arguments, i.e. a(j_{1}, …, j_{k}) = a(j_{π(1)}, …, j_{π(k)}) for all permutations π ∈ Π_{k} of the set {1, …, k}.

Let us define with the help of the above real numbers and a sequence of independent random variables ε_{1}, …, ε_{n}, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, the random variable

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

and the number

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

The following result will be proved.

Theorem 1. (The multivariate version of Hoeffding’s inequality). The random variable Z defined in formula (1.2) satisfies the inequality

P (|Z| > u) ≤ A exp \{−\frac{1}{2} (\frac{u}{V} )^{2/k}\} for all u ≥ 0  (1.4)

with the constant V defined in (1.3) and some constants A > 0 depending only on the parameter k in the expression Z.

I make some comments about this result.

The condition that the coefficients a(j_{1}, …, j_{k}) are symmetric functions of their variables does not mean a real restriction, since by replacing all coefficients a(j_{1}, …, j_{k}) by a_{Sym}(j_{1}, …, j_{k}) = \frac{1}{k!} ∑_{π∈Π_{k}} a(j_{π(1)}, …, j_{π(k)}) in formula (1.2), where Π_{k} denotes the

set of all permutations of the set {1, …, k} we do not change the random variable Z. Beside this, the above symmetrization of the coefficients in formula (1.2) decreases the number V introduced in formula (1.3).

The identities EZ = 0, EZ^{2} = k!V^{2} hold. Thus Theorem 1 yields an estimate on the tail behaviour of a homogeneous polynomial of order k of independent random variables ε_{1}, …, ε_{j}, P (ε_{j} = 1) = P (ε_{j} = −1) = \frac{1}{2}, 1 ≤ j ≤ n, with the help of the variance of this polynomial. Such an estimate may be useful in the study of degenerate U-statistics. Thus for instance in paper [10] a weaker form of Theorem 1 played an important role. In Lemma 2 of that paper such a weaker version of the estimate (1.4) was proved, where the constant \frac{1}{2} in the exponent at its right-hand side was replaced by the number \frac{k}{2e(k!)^{1/k}}. This estimate, which is a fairly simple consequence of Borell’s inequality was satisfactory in that paper. (Borell’s inequality together with its relation to the problem of this paper will be discussed in Section 3.) However, the question arose whether it can be improved. In particular, I was interested in the question whether such an estimate holds which a comparison with the Gaussian case suggests. In the case k = 1 it is natural to compare the tail behaviour of Z with that of V η, where η is a random variable with standard normal distribution. Theorem A gives an estimate suggested by such a comparison.

If Z is a homogeneous random polynomial of order k defined in (1.2), then it is natural to compare its tail distribution with that of V H_{k}(η), where η has standard normal distribution, and H_{k}(·) is the k-th Hermite polynomial with leading coefficient 1. Theorem 1 yields an estimate suggested by such a comparison. The next example shows that this estimate is sharp. It also explains, why it is natural to compare the random variable Z with V H_{k}(η).

Define for all n = k, k + 1, … the random variables Z = Z_{n} by means of formula (1.2) with the coefficients

a(j_{1}, …, j_{k}) = a_{n}(j_{1}, …, j_{k}) = \frac{V}{\sqrt{n(n − 1) ⋯ (n − k + 1)}}.

For the sake of simplicity let us assume that the random variables ε_{j}, j = 1, …, n, in formula (1.2) are given in the form ε_{j} = h(ζ_{j}), 1 ≤ j ≤ n, where ζ_{1}, …, ζ_{n} are independent random variables, uniformly distributed in the interval [0, 1], and h(x) = −1 if 0 ≤ x < \frac{1}{2}, h(x) = 1 if \frac{1}{2} ≤ x ≤ 1. (Such a representation of the random variables ε_{j} is useful for us, because it enables us to apply the subsequent limit theorem about degenerate U-statistics of iid. random variables with non-atomic distribution.)

In this example ^{\frac{\sqrt{n(n−1)···(n−k+1)}}{k!}}Z_{n} are degenerate U-statistics with kernel function f(x_{1}, …, x_{k}) = h(x_{1}) … h(x_{k}) and a sequence ζ_{1}, …, ζ_{n} of iid. random variables with uniform distribution on the interval [0, 1]. EZ_{n}^{2} = k!V^{2}, and a limit theorem about degenerate U-statistics (see e.g. [4]) implies that the random variables Z_{n} converge in distribution to the k-fold Wiener–Itô integral

Z^{(0)} = V ∫ h(x_{1}) … h(x_{k})W ( dx_{1}) … W (dx_{k})

as n → ∞, where W (·) is a Wiener process on the interval [0, 1].

Moreover, the random variable Z^{(0)} has a simpler representation. Namely, by Itô’s formula for multiple Wiener–Itô integrals (see e.g. [7]) it can be written in the form Z^{(0)} = V H_{k}(η), where H_{k}(·) is the k-th Hermite polynomial with leading coefficient 1, and η = ∫ h(x)W ( dx) is a random variable with standard normal distribution. Simple calculation shows that there are some constants C > 0 and D > 0 such that P (H_{k}(η) > u) ≥ Cu^{−1/k}e^{−u^{2/k}/2} if u > D. (Actually, this estimate is proved in [11].) Hence

lim_{n→∞} P (Z_{n} > u) = P (H_{k}(η) > \frac{u}{V} ) ≥ C (\frac{V}{u} )^{1/k} exp \{−\frac{1}{2} (\frac{u}{V} )^{2/k}\} if \frac{u}{V} ≥ D

with some appropriate constants C > 0 and D > 0. This inequality implies that the estimate (1.4) is essentially sharp. It does not hold with a smaller constant in the exponent at its right-hand side; this upper bound can be improved at least with a pre-exponential factor.

Theorem 1 will be proved in Section 2. It is a fairly simple consequence of a good estimate on the moments of the random variable Z formulated in Theorem 2. These moments will be estimated by means of two lemmas. The first of them, Lemma 1, enables us to bound the moments of Z by those of an appropriate polynomial of independent standard Gaussian random variables. There is a diagram formula to calculate the moments of polynomials of Gaussian random variables. This makes the estimation of the moments of Gausian random variables relatively simple. This is done in Lemma 2. Actually it turned out that it is simpler to rewrite these polynomials in the form of a multiple Wiener–Itô integral and to apply the diagram formula for multiple Wiener–Itô integrals. To make the explanation complete I give a more detailed description of the diagram formula at the end of Section 2. In the final part of this work, in Section 3, I try to explain the background of the proof of Theorem 1 in more detail. In particular, I make some comments about the role of the Gaussian bounding of moments in Lemma 1 and compare the moment estimates obtained by means of the method of this paper with the estimates supplied by Borell’s inequality.

2. The proof of Theorem 1.

Theorem 1 will be obtained as a consequence of the following Theorem 2.

Theorem 2. The random variable Z defined in formula (1.2) satisfies the inequality

EZ^{2M} ≤ 1 · 3 · 5 ⋯ (2kM − 1)V^{2M} for all M = 1, 2, …  (2.1)

with the constant V defined in formula (1.3).

Theorem 2 will be proved with the help of two lemmas. To formulate them, first the following random variable Z̄ will be introduced.

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

where η_{1}, …, η_{n} are iid. random variables with standard normal distribution, and the numbers a(j_{1}, …, j_{k}) agree with those in formula (1.2). Now we state

Lemma 1. The random variables Z and Z̄ defined in formulas (1.2) and (2.2) satisfy the inequality

EZ^{2M} ≤ EZ̄^{2M} for all M = 1, 2, ….  (2.3)

and

Lemma 2. The random variable Z̄ defined in formula (2.2) satisfies the inequality

EZ̄^{2M} ≤ 1 · 3 · 5 ⋯ (2kM − 1)V^{2M} for all M = 1, 2, …  (2.4)

with the constant V defined in formula (1.3).

Theorem 2 is a straightforward consequence of Lemmas 1 and 2. So to get this result it is enough to prove Lemmas 1 and 2.

Proof of Lemma 1. We can write, by carrying out the multiplications in the expressions EZ^{2M} and EZ̄^{2M}, by exploiting the additive and multiplicative properties of the expectation for sums and products of independent random variables together with the identities Eε_{j}^{2p+1} = 0 and Eη_{j}^{2p+1} = 0 for all p = 0, 1, … that

EZ^{2M} = ∑_{(j_{1},··· ,j_{l}, m_{1},...,m_{l}): 1≤j_{s}≤n, m_{s}≥1 for all 1≤s≤l with some k≤l≤kM, m_{1}+···+m_{l}=kM} A(j_{1}, …, j_{l}, m_{1}, …, m_{l})Eε_{j_{1}}^{2m_{1}} ⋯ Eε_{j_{l}}^{2m_{l}}

(2.5)

and

EZ̄^{2M} = ∑_{(j_{1},...,j_{l}, m_{1},...,m_{l}): 1≤j_{s}≤n, m_{s}≥1 for all 1≤s≤l with some k≤l≤kM, m_{1}+···+m_{l}=kM} B(j_{1}, …, j_{l}, m_{1}, …, m_{l})Eη_{j_{1}}^{2m_{1}} ⋯ Eη_{j_{l}}^{2m_{l}}

(2.6) with some coefficients A(j_{1}, …, j_{l}, m_{1}, …, m_{l}) and B(j_{1}, …, j_{l}, m_{1}, …, m_{l}) such that

|A(j_{1}, …, j_{l}, m_{1}, …, m_{l})| ≤ B(j_{1}, …, j_{l}, m_{1}, …, m_{l}).  (2.7)

The coefficients A(·, ·, ·) and B(·, ·, ·) could have been expressed in an explicit form, but we do not need such a formula. What is important for us is that A(·, ·, ·) can be expressed as the sum of certain terms, and B(·, ·, ·) as the sum of the absolute value of the same terms, hence relation (2.7) holds. (There may be such indices (j_{1}, …, j_{l}, m_{1}, …, m_{l}) for which the sum defining A(·, ·, ·) and B(·, ·, ·) with these indices is empty. The value of an empty sum will be defined as zero. As empty sums appear for some index in (2.5) and (2.6) simultaneously, their appearance causes no problem.) Since Eε_{j}^{2m} ≤ Eη_{j}^{2m} for all parameters j and m, formulas (2.5), (2.6) and (2.7) imply Lemma 1.

Proof of Lemma 2. I found simpler to construct an appropriate multiple Wiener–Itô integral Z̃ whose distribution agrees with that of the random variable Z̄ defined in (2.2) and to estimate its moment. To do this, let us consider a white noise W (·) on the unit interval [0, 1], i.e. let us take a set of (jointly) Gaussian random variables W (A) indexed by the measurable sets A ⊂ [0, 1] such that EW (A) = 0, EW (A)W (B) = λ(A ∩ B) with the Lebesgue measure λ on the real line. (We also need the relation W (A ∪ B) = W (A) + W (B) with probability 1 if A ∩ B = ∅, but this relation is the consequence of the previous ones. Indeed, they yield that E(W (A ∪ B) − W (A) − W (B))^{2} = 0 if A ∩ B = ∅, and this implies the desired identity.) Let us introduce the random variables η_{j} = n^{1/2}W ([\frac{j−1}{n}, \frac{j}{n})), 1 ≤ j ≤ n, together with the function f(t_{1}, …, t_{k}), with arguments 0 ≤ t_{s} < 1 for all indices 1 ≤ s ≤ k, defined as

f(t_{1}, …, t_{k}) = \{ \begin{matrix}n^{k/2}|a(j_{1}, …, j_{k})| if t_{s} ∈ [\frac{j_{s} − 1}{n}, \frac{j_{s}}{n} ) , and j_{s} ≠ j_{s′} if s ≠ s′, \\ 1 ≤ j_{s} ≤ n, 1 ≤ s ≤ k \\ 0 if t_{s} ∈ [\frac{j_{s} − 1}{n}, \frac{j_{s}}{n} ) , and j_{s} = j_{s′} for some s ≠ s′, \\ 1 ≤ j_{s} ≤ n, 1 ≤ s ≤ k \end{matrix}

and the k-fold Wiener–Itô integral

Z̃ = ∫ f(t_{1}, …, t_{k})W ( dt_{1}) … W ( dt_{k})  (2.8)

of this (elementary) function f. (For the definition of Wiener–Itô integrals see e.g. [6] or [8].)

Observe that the above defined random variables η_{1}, …, η_{n} are independent with standard normal distribution. Hence the definition of the Wiener–Itô integral of elementary functions and the definition of the function f imply that the distributions of the random integral Z̃ and of the random variable Z̄ introduced in (2.2) agree. Beside this, the identity

∫ f^{2}(t_{1}, …, t_{k}) dt_{1} … dt_{k} = V^{2}  (2.9)

also holds with the number V defined in formula (1.3). Since the distribution of the random variables Z̄ and Z̃ agree, formulas (2.8), (2.9) together with the following estimate about the moments of Wiener–Itô integrals complete the proof of Lemma 2.

In this estimate a function f of k variables and a σ-finite measure μ on some measurable space (X, X) are considered which satisfy the inequality

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

with some σ^{2} < ∞. The moments of the k-fold Wiener–Itô integral

J_{μ,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 reference measure μ satisfy the inequality

E (k!J_{μ,k}(f))^{2M} ≤ 1 · 3 ⋯ (2kM − 1)σ^{2M}  (2.10)

for all M = 1, 2, . . .. This result can be got relatively simply from the diagram formula for the product of Wiener–Itô integrals, and it is actually proven in Proposition A of paper [11]. It can be obtained as a straightforward consequence of the results in Lemma 7.31 and Theorem 7.33 of the book [6]. For the sake of completeness I explain this result at the end of this section.

After the proof of Theorem 2 with the help of the diagram formula it remained to derive Theorem 1 from it.

Proof of Theorem 1. By the Stirling formula we get from the estimate of Theorem 2 that

EZ^{2M} ≤ \frac{(2kM)!}{2^{kM}(kM)!}V^{2M} ≤ K (\frac{2}{e})^{kM} (kM)^{kM}V^{2M}  (2.11)

for any K > \sqrt{2} if M ≥ M_{0}(K). Hence the Markov inequality yields the estimate

P (Z > u) ≤ \frac{EZ^{2M}}{u^{2M}} ≤ K (\frac{2kM}{e} (\frac{V}{u} )^{2/k})^{kM}  (2.12)

for all K > \sqrt{2} if M ≥ M_{0}(K). Put kM̄ = kM̄(u) = \frac{1}{2} (\frac{u}{V} )^{2/k}, and M = M(u) = [M̄], where [x] denotes the integer part of the number x. Let us choose the number u_{0} as the solution of the identity \frac{1}{2k} (\frac{u_{0}}{V} )^{2/k} = M_{0}(K) + 1. Formula (2.12) can be applied with M = M(u) for u ≥ u_{0}, and it yields that

P (Z > u) ≤ Ke^{−kM} ≤ Ke^{k}e^{−kM̄} = Ke^{k} exp \{−\frac{1}{2} (\frac{u}{V} )^{2/k}\} if u ≥ u_{0}. (2.13)

Formula (2.13) means that relation (1.4) holds for u ≥ u_{0} with the constant A = Ke^{k}. Hence relation (1.4) holds with a sufficiently large constant A > 0 for all u ≥ 0.

Estimation of the moments of a Wiener–Itô integral by means of the diagram formula.

Let us have m real-valued functions f_{j}(x_{1}, …, x_{k_{j}}), 1 ≤ j ≤ m, on a measurable space (X, X , μ) with some σ-finite non-atomic measure μ such that

∫ f_{j}^{2}(x_{1}, …, x_{k_{j}})μ( dx_{1}) … μ( dx_{k_{j}}) < ∞ for all 1 ≤ j ≤ m.  (2.14)

A white noise μ_{W} with reference measure μ can be introduced on (X, X). It is an ensemble of jointly Gaussian random variables μ_{W} (A) indexed by the measurable sets A ∈ X such that μ(A) < ∞ with the property Eμ_{W} (A) = 0 and Eμ_{W} (A)μ_{W} (B) = μ(A ∩ B). Also the Wiener–Itô integrals

k_{j}!J_{μ,k}(f_{j}) = ∫ f_{j}(x_{1}, …, x_{k_{j}})μ_{W} ( dx_{1}) … μ_{W} ( dx_{k_{j}})

of these functions with respect to the white noise μ_{W} can be defined if they satisfy relation (2.14). The definition of these integrals is rather standard, (see e.g [6] or [8]). First they are defined with respect to simple, so-called elementary functions in a natural way, and then they are extended to general functions by means of an L_{2}-isomorphism. I omit the details.

A most important result in the theory of multiple Wiener–Itô integrals is the socalled diagram formula, which expresses the product of multiple Wiener–Itô integrals in the form of a sum of Wiener–Itô integrals of different order. (The number of variables of the kernel function in a Wiener–Itô integral is called the order of this integral.) The kernel functions of the integrals in the sum representation of a product of Wiener–Itô integrals are defined by means of diagrams. This is the reason for the name ‘diagram formula’.

All Wiener–Itô integrals of order k ≥ 1 have expectation zero, hence if the product of Wiener–Itô integrals is written in the form of a sum of Wiener–Itô integrals, then the expectation of the product can be calculated as the sum of the constant terms in its sum representation. In the present paper only this consequence of the diagram formula will be needed, hence only this result will be described.

This result will be formulated by means of the notion of (closed) diagrams. The class of closed diagrams will be denoted by Γ = Γ(k_{1}, …, k_{m}). A diagram γ ∈ Γ(k_{1}, …, k_{m}) consists of vertices of the form (j, l), 1 ≤ j ≤ m, 1 ≤ l ≤ k_{j}, and edges ((j, l), (j′, l′)), 1 ≤ j, j′ ≤ m, 1 ≤ l ≤ k_{j}, 1 ≤ l′ ≤ k′_{j}. The set of vertices of the form (j, l) with a fixed number j is called the j-th row of the diagram. All edges ((j, l), (j′, l′)) of a diagram γ ∈ Γ connect vertices from different rows, i.e. j ≠ j′. It is also demanded that from all vertices of a diagram γ there starts exactly one edge. The class Γ(k_{1}, …, k_{m}) of (closed) diagrams contains the diagrams γ with the above properties. If j < j′ for an edge ((j, l), (j′, l′)) ∈ γ, then (j, l) is called the upper and (j′, l′) the lower end point of this edge. Let U(γ) denote the upper and L(γ) the lower end points of a diagram γ ∈ Γ(k_{1}, …, k_{m}). Define the function α_{γ}(j, l) = (j, l) if (j, l) is the upper end point and α_{γ}(j, l) = (j′, l′) if (j, l) is the lower end point of an edge ((j, l), (j′l′)) of a diagram γ ∈ Γ(k_{1}, …, k_{m}).

For the sake of simpler notations let us rewrite the functions f_{j} with reindexed variables in the form f_{j}(x_{j,1}, …, x_{j,k_{j}}), 1 ≤ j ≤ m, and define the function

F (x_{j,l}, 1 ≤ j ≤ m, 1 ≤ l ≤ k_{j}) = ∏_{j=1}^{m} f_{j}(x_{j,1}, …, x_{j,k_{j}}).

Define with the help of the functions F and α_{γ} the constants

F_{γ} = ∫ F (x_{α_{γ}(j,l)}, 1 ≤ j ≤ m, 1 ≤ l ≤ k_{j}) ∏_{(j,l)∈U(γ)} μ( dx_{j,l})  (2.15)

for all γ ∈ Γ(k_{1}, …, k_{m}).

The expected value of the product of Wiener–Itô integrals k_{j}!J_{μ,k}(f_{j}), 1 ≤ j ≤ m, can be expressed with the help of the above quantities F_{γ}. The following result holds.

Formula about the expected value of products of Wiener–Itô integrals. Let us consider the Wiener–Itô integrals k_{j}!J_{μ,k}(f_{j}) of some functions f_{j}, 1 ≤ j ≤ m, satisfying relation (2.14). The expected value of this product satisfies the identity

E (∏_{j=1}^{m} k_{j}!J_{μ,k}(f_{j})) = ∑_{γ∈Γ(k_{1},...,k_{m})} F_{γ}

with the numbers F_{γ} defined in (2.15). These numbers satisfy the inequality

F_{γ}^{2} ≤ ∏_{j=1}^{m} ∥f_{j}∥^{2} for all γ ∈ Γ(k_{1}, …, k_{m})

with the square of the L_{2}-norm ∥f_{j}∥^{2} = ∫ f_{j}^{2}(x_{1}, …, x_{k_{j}})μ( dx_{1}) … μ( dx_{k_{j}}) of the functions f_{j}, 1 ≤ j ≤ m.

Let us consider the above result in the special case m = 2M and f_{j} = f for all 1 ≤ j ≤ m with a square integrable function f of k variables. Let Γ(k, M) denote the class of diagrams Γ(k_{1}, …, k_{m}) in this case, and |Γ(k, M)| the number of diagrams it contains. The above result yields the estimate

E (k!J_{μ,k}(f))^{2M} ≤ |Γ(k, M)|∥f∥^{2M}.  (2.16)

It is not difficult to see that |Γ(k, M)| ≤ 1 · 3 · 5 ⋯ (2kM − 1). Indeed, if we omit the restriction that the edges of a diagram can connect only vertices from different rows, then the number of diagrams with 2M rows and k vertices in each row equals 1 · 3 · 5 ⋯ (2kM − 1). Relation (2.16) together with this observation imply (2.10).

It is also worth mentioning that the estimate (2.16) is sharp in the following sense. If f(x_{1}, …, x_{k}) = f(x_{1}) ⋯ f(x_{k}) with some square integrable function f, then relation (2.16) holds with identity. In this case k!J_{μ,k}(f) equals const. H_{k}(η) with some standard normal random variable η and the k-th Hermite polynomial H_{k}(·) because of Itô’s formula for multiple Wiener–Itô integrals.

3. Some remarks about the results.

The proof of Theorem 1 was based on an estimate of the (high) moments of the homogeneous random polynomial Z of Rademacher functions defined in (1.2). Although bounds on the tail distribution of sums of independent random variables are generally proved by means of a good estimate on the moment generating function, in the present problem it was more natural to estimate the moments because of the following reason.

As the example discussed in Section 1 shows, if Z is a random polynomial of order k, then the tail distribution P (Z > u) should behave for large numbers u as e^{−const. u^{−α(k)}} with α(k) = \frac{2}{k}. In the case k ≥ 3 a random variable with such a tail distribution has no finite moment generating function. Hence the estimation of the moment generating function does not work in such cases. On the other hand, a good estimate of the (high) moments of the random variable Z is sufficient to prove Theorem 1. It has to be shown that the high moments of Z are not greater than constant times the appropriate moments of a random variable with tail distribution e^{−const. u^{−α(k)}}. Here the same constant is in the exponent as in the exponent of the upper bound in Theorem 1.

Theorem 2 contains a good estimate on all even moments of a homogeneous polynomial of Rademacher functions of order k, and it can be considered as a Gaussian type estimate. (It has the same order as the moments of a k-order Hermite polynomial of a standard normal random variable multiplied with a constant.) The moments of degenerate U-statistics were also studied. Proposition B of paper [11] contains a result in this direction. It turned out that high moments of degenerate U-statistics show a worse behaviour. Only their not too high moments satisfy a good ‘Gaussian type’ estimate. This difference has a deeper cause. There are degenerate U-statistics which have a relatively bad tail behaviour at high levels. Such examples can be found in Example 2.4 for sums of independent random variables and in Example 4.5 for degenerate U-statistics of order 2 in paper [9]. In such cases much worse moment estimates hold than in Theorem 2.

Lemma 1 made possible to reduce the estimation of the moments (and as a consequence the tail of distribution) of a homogeneous polynomial of Rademacher functions to the estimation of the moments of a homogeneous polynomial of Gaussian random variables. This result provided a good tail distribution estimate at all high levels. It can be generalized to other polynomials of independent random variables with good moment behaviour. On the other hand, general U-statistics may have a much worse tail behaviour at high levels than the behaviour suggested by a Gaussian comparison. It would be interesting to get a better understanding about the question when a U-statistic has such a good tail behaviour at all levels which a Gaussian comparison suggests, and when it has a relatively bad tail behaviour at very high level. At any rate, the fact that homogeneous polynomials of Rademacher functions satisfy a good ‘Gaussian type’ estimate at all levels u > 0 has an important consequence. This property was needed for the application of an important symmetrization argument in paper [10]. This symmetrization argument made possible to get a good estimate on the supremum of degenerate U-statistics also in such cases when other methods do not work.

There is another result, called Borell’s inequality, which makes possible to bound the high moments, and as a consequence the tail distribution of a homogeneous polynomial of Rademacher functions. Actually, this estimate is a simple consequence of the hypercontractive inequality for Rademacher functions proved by A. Bonami [1] and L. Gross [5] independently of each other. It may be interesting to compare the estimates provided by Borell’s inequality with those of the present paper.

Borell’s inequality, (see e.g. [2]) states the following estimate.

Theorem B. (Borell’s inequality). The moments of the random variable Z defined in formula (1.2) satisfy the inequality

E|Z|^{p} ≤ (\frac{p − 1}{q − 1})^{kp/2} (E|Z|^{q})^{p/q} if 1 < q ≤ p < ∞.

Let us apply Borell’s inequality with the choice p = 2M and q = 2 for the random variable Z defined in (1.2). It gives the bound EZ^{2M} ≤ (2M − 1)^{kM}(EZ^{2})^{M} ≤ A(k)(2M)^{kM}(k!)^{M}V^{2M} with the constant A(k) = e^{−k/2}. (The expression in the last part of this inequality is slightly larger than the middle term, but this has no importance in the subsequent consideration.) On the other hand, Theorem 2, more precisely its consequence relation (2.11), yields the bound EZ^{2M} ≤ K(2M)^{kM} (\frac{k}{e} )^{kM} V^{2M} with some appropriate constant K = K(k) > 0 not depending on M. It can be seen that the inequality (\frac{k}{e} )^{k} < k! holds for all integers k ≥ 1. This means that the estimate of the present paper yields a const. · α^{M}-times smaller bound for the moment EZ^{2M} than the estimate given by Borell’s inequality, where α = \frac{1}{k!} (\frac{k}{e} )^{k} < 1. As a consequence, Borell’s inequality can give the right type of estimate for the tail distribution of the random variable Z, but it cannot give the optimal constant in the exponent. In such large deviation type estimates the moment estimates based on the diagram formula seem to work better.

References

1.) Bonami, A. (1970) Étude des coefficients de Fourier des fonctions de L^{p}(G). Ann.

Inst. Fourier (Grenoble) 20 335–402 2.) Borell, C. (1979) On the integrability of Banach space valued Walsh polynomials.

Séminaire de Probabilités XIII, Lecture Notes in Math. 721 1–3. Springer, Berlin. 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.) Gross, L. (1975) Logarithmic Sobolev inequalities. Amer. J. Math. 97, 1061–1083 6.) Janson, S. (1997) Gaussian Hilbert spaces. Cambridge Tracts in Mathematics, 129.

Cambridge University Press, Cambridge 7.) Itô K. (1951) Multiple Wiener integral. J. Math. Soc. Japan 3. 157–164 8.) Major, P. (1981) Multiple Wiener–Itô integrals. Lecture Notes in Mathematics

849, Springer Verlag, Berlin Heidelberg, New York, 9.) Major, P. (2005) Tail behaviour of multiple random integrals and U-statistics.

Probability Reviews. 448–505 10.) Major, P. (2006) An estimate on the maximum of a nice class of stochastic integrals.

Probability Theory and Related Fields., 134, 489–537 11.) Major, P. (2006) On a multivariate version of Bernstein’s inequality. Submitted to

Journal of Electronic Probability