Decoupling Inequalities for the Tail Probabilities of Multivariate U-statistics

by Victor H. de la Peña^{1} and S. J. Montgomery-Smith ^{2} Columbia University and University of Missouri, Columbia

Abstract

In this paper we present a decoupling inequality that shows that multivariate Ustatistics can be studied as sums of (conditionally) independent random variables. This result has important implications in several areas of probability and statistics including the study random graphs and multiple stochastic integration. More precisely, we get the following result: Theorem 1. Let {X_{j}} be a sequence of independent random variables in a measurable space (S, S), and let {X_{i}^{(j)}}, j = 1, ..., k be k independent copies of {X_{i}}. Let f_{i_{1}i_{2}...i_{k}} be families of functions of k variables taking (S ×...×S) into a Banach space (B, ||·||). Then, for all n ≥ k ≥ 2, t > 0, there exist numerical constants C_{k} depending on k only so that,

P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t)

≤ C_{k}P (C_{k}|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, ..., X_{i_{k}}^{(k)})|| ≥ t).

The reverse bound holds if in addition, the following symmetry condition holds almost surely

f_{i_{1}i_{2}...i_{k}}(X_{i_{1}}, X_{i_{2}}, ..., X_{i_{k}}) = f_{i_{π(1)}i_{π(2)}...i_{π(k)}}(X_{i_{π(1)}}, X_{i_{π(2)}}, ..., X_{i_{π(k)}}),

for all permutations π of (1, ..., k).

1. Introduction In this paper we provide the multivariate extension of the tail probability decoupling

inequality for generalized U-statistics of order two and quadratic forms presented in de la Peña and Montgomery-Smith (1993). This type of inequality permits the transfer of some results for sums of independent random variables to the case of U-statistics. Our work builds mainly on recent work of Kwapien and Woyczynski (1992) as well as on results for U-statistics from Giné and Zinn (1992) and papers dealing with inequalities for multilinear forms of symmetric and hypercontractive random variables in de la Peña, Montgomery-Smith and Szulga (1992), and de la Peña (1992). It is to be remarked that the decoupling inequalities for multilinear forms introduced in McConnell and Taqqu (1986) provided us with our first exposure to this decoupling problem. For a more expanded list of references on the subject see, for example, Kwapien and Woyczynski (1992).

1,2 Supported in part by NSF grants. 2 Supported by the University of Missouri Research Board. AMS 1991 subject classifications: Primary 60E15. Secondary 60D05. Key words and phrases: U-statistics, Decoupling.

2. Main Result

Theorem 1. Let {X_{i}} be a sequence of independent random variables in a measurable space (S, S), and let {X_{i}^{(j)}}, j = 1, ..., k be k independent copies of {X_{i}}. Let f_{i_{1}i_{2}...i_{k}} be families of functions of k variables taking (S ×...×S) into a Banach space (B, ||·||). Then, for all n ≥ k ≥ 2, t > 0, there exist numerical constants C_{k}, C̃_{k} depending on k only so that,

P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t)

≤ C_{k}P (C_{k}|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, ..., X_{i_{k}}^{(k)})|| ≥ t).

If in addition, the following symmetry condition holds almost surely

f_{i_{1}i_{2}...i_{k}}(X_{i_{1}}, X_{i_{2}}, ..., X_{i_{k}}) =
f_{i_{π(1)}i_{π(2)}...i_{π(k)}}(X_{i_{π(1)}}, X_{i_{π(2)}}, ..., X_{i_{π(k)}})

for all permutations π of (1, ..., k), then

P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, ..., X_{i_{k}}^{(k)})|| ≥ t)

≤ C̃_{k}P (C̃_{k}|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t).

Note: In this paper we use the notation {i_{1} ≠ i_{2} ≠ ... ≠ i_{k}} to denote that all of i_{1}, ..., i_{k} are different.

3. Preliminary Results Throughout this paper we will be using two results found in earlier work. The first

one comes from de la Peña and Montgomery-Smith (1993). For completeness we reproduce the proof here. Lemma 1. Let X, Y be two i.i.d. random variables. Then

(1)  P (||X|| ≥ t) ≤ 3P (||X + Y || ≥ \frac{2t}{3}).

Proof: Let X, Y, Z be i.i.d. random variables. Then

P (||X|| ≥ t)
= P (||(X + Y) + (X + Z) − (Y + Z)|| ≥ 2t)
≤ P (||X + Y || ≥ 2t/3) + P (||X + Z|| ≥ 2t/3) + P (||Y + Z|| ≥ 2t/3)
= 3P (||X + Y || ≥ 2t/3).

The second result comes from Kwapien and Woyczynski (1992) and can also be found in de la Peña and Montgomery-Smith (1993).

Proposition 1. Let Y be any mean zero random variable with values in a Banach space (B, || · ||). Then, for all aϵB,

(2)  P (||a + Y || ≥ ||a||) ≥ \frac{κ}{4},

where κ = inf_{x′ϵB′} \frac{(E|x′(Y)|)^{2}}{E(x′(Y))^{2}} . (Here B′ denotes the family of linear functionals on B.) Proof: Note first that if ξ is a random variable for which Eξ = 0, then P (ξ ≥ 0) ≥ \frac{1}{4} \frac{(E|ξ|)^{2}}{E(ξ^{2})} . From this, we deduce that P (x′(Y) ≥ 0) ≥ \frac{1}{4} \frac{(E|X′(Y)|)^{2}}{E(X′(Y))^{2}} The result then follows, because if x′ϵB′ is such that ||x′|| = 1 and x′(a) = ||a||, then {||a + Y || ≥ ||a||} contains {x′(a + Y) ≥ x′(a)} = {x′(Y) ≥ 0}. Lemma 2. Let x, a_{i_{1}}, a_{i_{1}i_{2}}, ..., a_{i_{1}i_{2}...i_{k}} belong to a Banach space (B, || · ||). Let {ϵ_{i}} be a sequence of symmetric Bernoulli random variables. Then,

P (||x + ∑_{r=1}^{k} ∑_{1≤i_{i}≠i_{2}≠...≠i_{r}≤n} a_{i_{1}...i_{r}}ϵ_{i_{1}}...ϵ_{i_{r}}|| ≥ ||x||) ≥ c_{k}^{−1},

for a universal constant 1 < c_{k} < ∞ depending on k only. Proof: Suppose that x, a_{i_{1}}, a_{i_{1}i_{2}}, ..., a_{i_{1}i_{2}...i_{k}} are in R, then since the ϵ’s are hypercontractive, by equation (1.4) of Kwapien and Szulga (1991) and the easy argument of the proof of Lemma 3 in de la Peña and Montgomery-Smith (1993), for some σ > 0, we get

(E| ∑_{r=1}^{k} ∑_{1≤i_{1}≠...≠i_{r}≤n} a_{i_{1}...i_{r}}ϵ_{i_{1}}...ϵ_{i_{r}}|^{4})^{\frac{1}{4}}

= (E| ∑_{r=1}^{k} ∑_{1≤i_{1}<...<i_{r}≤n} b_{i_{1}...i_{r}}ϵ_{i_{1}}...ϵ_{i_{r}}|^{4})^{\frac{1}{4}}

≤ σ^{−k}(E| ∑_{r=1}^{k} ∑_{1≤i_{1}<...<i_{k}≤n} b_{i_{1}...i_{r}}ϵ_{i_{1}}...ϵ_{i_{r}}|^{2})^{\frac{1}{2}}

= σ^{−k}(E| ∑_{r=1}^{k} ∑_{1≤i_{1}≠...≠i_{k}≤n} a_{i_{1}...i_{r}}ϵ_{i_{1}}...ϵ_{i_{r}}|^{2})^{\frac{1}{2}} ,

where b_{i_{1}...i_{r}} = ∑_{π∈S_{r}} a_{i_{π(1)}...i_{π(r)}}, and S_{r} denotes the set of all permutations of {1, ..., r}.

Next, observe that ||ξ||_{4} ≤ σ^{−2}||ξ||_{2} implies that ||ξ||_{2} ≤ σ^{−4}||ξ||_{1}. Take x′ϵB′ so that ||x′|| = 1 and x′(x) = ||x||, then

P (||x + ∑_{r=1}^{k} ∑_{1≤i_{i}≠i_{2}≠...≠i_{r}≤n} a_{i_{1}...i_{r}}ϵ_{i_{1}}...ϵ_{i_{r}}|| ≥ ||x||)

≥ P (x′(x) + ∑_{r=1}^{k} ∑_{1≤i_{i}≠i_{2}≠...≠i_{r}≤n} x′(a_{i_{1}...i_{r}})ϵ_{i_{1}}...ϵ_{i_{r}} ≥ x′(x))

= P (∑_{r=1}^{k} ∑_{1≤i_{i}≠i_{2}≠...≠i_{r}≤n} x′(a_{i_{1}...i_{r}})ϵ_{i_{1}}...ϵ_{i_{r}} ≥ 0) ≥ c_{k}^{−1}

Note: Throughout this paper we will use c_{k} and C_{k} to denote numerical constants that depend on k only and may change from application to application.

4. Proof of the Upper Bound: Our proof of this result is obtained by applying the argument used in the proof of the

upper bound in the bivariate case plus an inductive argument. Let {σ_{i}} be a sequence of independent symmetric Bernoulli random variables, P (σ_{i} = 1) = \frac{1}{2} and P (σ_{i} = −1) = \frac{1}{2}. Consider random variables (Z_{i}^{(1)}, Z_{i}^{(2)}) such that (Z_{i}^{(1)}, Z_{i}^{(2)}) = (X_{i}^{(1)}, X_{i}^{(2)}) if σ_{i} = 1 and (Z_{i}^{(1)}, Z_{i}^{(2)}) = (X_{i}^{(2)}, X_{i}^{(1)}) if σ_{i} = −1. Then (1 + σ_{i}) and (1 − σ_{i}) are either 0 or 2 and these random variables can be used to transform the problem from one involving X’s to one involving Z’s. Let us first illustrate the argument in the case that k = 3. 2^{3}f_{i_{1}i_{2}i_{3}}(Z_{i_{1}}^{(1)}, Z_{i_{2}}^{(1)}, Z_{i_{3}}^{(2)}) =

{(1 + σ_{i_{1}})(1 + σ_{i_{2}})(1 + σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(2)})

+(1 + σ_{i_{1}})(1 + σ_{i_{2}})(1 − σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(1)})

+(1 + σ_{i_{1}})(1 − σ_{i_{2}})(1 + σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(2)})

(3)  +(1 − σ_{i_{1}})(1 + σ_{i_{2}})(1 + σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(2)})

+(1 + σ_{i_{1}})(1 − σ_{i_{2}})(1 − σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(1)})

+(1 − σ_{i_{1}})(1 + σ_{i_{2}})(1 − σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(1)})

+(1 − σ_{i_{1}})(1 − σ_{i_{2}})(1 + σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(2)})

+(1 − σ_{i_{1}})(1 − σ_{i_{2}})(1 − σ_{i_{3}})f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(1)})},

where the sign “+” is chosen if the superscript of X_{i} agrees with that of Z_{i}, and “−” otherwise. Next, set T_{n,3} = ∑_{1≤i_{1}≠i_{2}≠i_{3}≤n}

{f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(2)}) + f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(1)})

+f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(2)}) + f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(2)})

+f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(1)}) + f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(1)}, X_{i_{3}}^{(1)})

+f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(2)}) + f_{i_{1}i_{2}i_{3}}(X_{i_{1}}^{(2)}, X_{i_{2}}^{(2)}, X_{i_{3}}^{(1)})}.

Letting G_{2} = σ(X_{i}^{(1)}, X_{i}^{(2)}, i = 1, ..., n) we get

T_{n,3} = 2^{3} ∑_{1≤i_{1}≠i_{2}≠i_{3}≤n} E(f_{i_{1}i_{2}i_{3}}(Z_{i_{1}}^{(1)}, Z_{i_{2}}^{(1)}, Z_{i_{3}}^{(2)})|G_{2}).

More generally, for any 1 ≤ l_{1}, ..., l_{k} ≤ 2, one can obtain the expansion 2^{k}f_{i_{1}...i_{k}}(Z_{i_{1}}^{(l_{1})}, ..., Z_{i_{k}}^{(l_{k})})

(4)  = ∑_{1≤j_{1},...,j_{k}≤2}(1±σ_{i_{1}})...(1±σ_{i_{k}})f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})}).

The appropriate extension of T_{n,3} is

T_{n,k} = ∑_{1≤i_{1}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤2} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})}).

Again,

T_{n,k} = 2^{k} ∑_{1≤i_{1}≠...≠i_{k}≤n} E(f_{i_{1}...i_{k}}(Z_{i_{1}}^{(l_{1})}, ..., Z_{i_{k}}^{(l_{k})})|G_{2}).

From Lemma 1 we get,

P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t) ≤

3P (3|| ∑_{1≤i_{1}≠...≠i_{k}≤n}{f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, ..., X_{i_{k}}^{(1)}) + f_{i_{1}...i_{k}}(X_{i_{1}}^{(2)}, ..., X_{i_{k}}^{(2)})}|| ≥ 2t) =

3P (3||T_{n,k} + ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, ..., X_{i_{k}}^{(1)}) + f_{i_{1}...i_{k}}(X_{i_{1}}^{(2)}, ..., X_{i_{k}}^{(2)}) − T_{n,k}|| ≥ 2t) ≤

{3P (3||T_{n,k}|| ≥ t)

+3P (3|| ∑_{1≤i_{1}≠...≠i_{k}≤n} ∑_{1≤j_{1},...j_{k}≤2, not all j’s equal} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})})|| ≥ t)}

≤ {3P (3||T_{n,k}|| ≥ t)

(5) + ∑_{1≤j_{1},...,j_{k}≤2, not all j’s equal} C_{k}P (C_{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})})|| ≥ t)}.

(Recall that C_{k}, c_{k} are numerical constants that depend on k only and may change from application to application.)

Observe also that using (4) and the fact that the σ’s are independent from the X’s, Lemma 2 with x = T_{n,k} gives for any fixed 1 ≤ l_{1}, ..., l_{k} ≤ 2,

(6)  P (2^{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(Z_{i_{1}}^{(l_{1})}, ..., Z_{i_{k}}^{(l_{k})})|| ≥ ||T_{n,k}|| |G_{2}) ≥ c_{k}^{−1},

Integrating over {||T_{n,k}|| ≥ t} and using the fact that {(X_{i}^{(1)}, X_{i}^{(2)}) : i = 1, ..., n} has the same joint distribution as {(Z_{i}^{(1)}, Z_{i}^{(2)}) : i = 1, ..., n} we obtain that

(7)  P (2^{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(l_{1})}, ..., X_{i_{k}}^{(l_{k})})|| ≥ t).

= P (2^{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(Z_{i_{1}}^{(l_{1})}, ..., Z_{i_{k}}^{(l_{k})})|| ≥ t) ≥ c_{k}^{−1}P (||T_{n,k}|| ≥ t)

It is obvious that the upper bound decoupling inequality holds for the case of Ustatistics of order 1. Assume that it holds for U-statistics of orders 2, ..., k − 1. Putting (5) and (7) together with 1 ≤ l_{1}, ..., l_{k} ≤ 2, not all l’s equal we get, P (|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t) ≤ {3P (3||T_{n,k}|| ≥ t)

+ ∑_{1≤j_{1},...,j_{k}≤2, not all j’s equal} C_{k}P (C_{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})})|| ≥ t)}

≤ ∑_{1≤j_{1},...,j_{k}≤2, not all j’s equal} C_{k}P (C_{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})})|| ≥ t)

≤ C_{k}P (C_{k}|| ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, ..., X_{i_{k}}^{(k)})|| ≥ t),

where again, the last line follows by the decoupling result for U-statistics of orders 2, ..., k−1 of the inductive hypothesis. Since the statement “not all j’s equal” means that there are less than k j’s equal, the variables whose j’s are equal can be decoupled using (conditionally on the other variables) the decoupling inequalities for U-statistics of order 2, ..., k − 1.

Next we give the proof of the lower bound.

5. Proof of the Lower Bound

In order to show the lower bound we require the following result.

Lemma 3. Let 1 ≤ l ≤ k. Then there is a constant C_{k} such that

P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t)

≥ C_{k}^{−1}P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤l} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, X_{i_{2}}^{(j_{2})}, ..., X_{i_{k}}^{(j_{k})})|| ≥ C_{k}t).

Proof: Let \{δ_{r}\}, r = 1, ..., l, be a sequence of random variables for which P (δ_{r} = 1) = \frac{1}{l} and P (δ_{r} = 0) = 1 − \frac{1}{l}, and ∑_{r=1}^{l} δ_{r} = 1. Set ϵ_{r} = δ_{r} − \frac{1}{l} for r = 1, ..., l. Then, it is easy to see that there exists σ_{l} > 0 depending only upon l such that for any real number x_{0} and any sequence of real constants {a_{i}}

(8)  ||x_{0} + ∑_{r=1}^{l} a_{r}ϵ_{r}||_{4} ≤ ||x_{0} + σ_{l}^{−1} ∑_{r=1}^{l} a_{r}ϵ_{r}||_{2}.

One can also use the results of Section 6.9 of Kwapien and Woyczynski (1992) (Pg. 180,

181) to assert this since the ϵ’s satisfy the conditions 1. through 3. stated there.

Let {(δ_{i1}, ..., δ_{il}), i = 1, ..., n} be n independent copies of (δ_{1}, ..., δ_{l}). As before, we define

(9)  ϵ_{ij} = δ_{ij} − \frac{1}{l}.

Since the vectors E_{i} = (ϵ_{i1}, ..., ϵ_{il}) are independent, by an argument given in Kwapien and Szulga (1991), for i = 1, ..., n, for all constants x_{0}, a_{ij} in R,

(10) ||x_{0} + ∑_{i=1}^{n} ∑_{r=1}^{l} a_{ir}ϵ_{ir}||_{4} ≤ ||x_{0} + σ_{l}^{−1} ∑_{i=1}^{n} ∑_{r=1}^{l} a_{ir}ϵ_{ir}||_{2} ≤ σ_{l}^{−1}||x_{0} + ∑_{i=1}^{n} ∑_{r=1}^{l} a_{ir}ϵ_{ir}||_{2},

and recentering, we obtain

(11)  ||x_{0} + ∑_{i=1}^{n} ∑_{r=1}^{l} a_{ir}δ_{ir}||_{4} ≤ σ_{l}^{−1}||x_{0} + ∑_{i=1}^{n} ∑_{r=1}^{l} a_{ir}δ_{ir}||_{2}.

Next we use the sequence E_{i}, i = 1, ..., n in defining the analogue of the Z’s used in our proof of the upper bound.

For each i, let Z_{i} = X_{i}^{(j)} if δ_{ij} = 1. Then, {Z_{i}, i = 1, ..., n} has the same joint distribution as {X_{i}^{(1)}, i = 1, ..., n} and

f_{i_{1}...i_{k}}(Z_{i_{1}}, .., Z_{i_{k}}) = ∑_{1≤j_{1},j_{2},...,j_{k}≤l} δ_{i_{1}j_{1}}...δ_{i_{k}j_{k}}f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})}).

The fact that Eδ_{i_{r}j_{r}} = \frac{1}{l} for all i_{r}, j_{r} gives,

E(f_{i_{1}...i_{k}}(Z_{i_{1}}, ..., Z_{i_{k}})|G_{l}) = (\frac{1}{l})^{k} ∑_{1≤j_{1},...,j_{k}≤l} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ..., X_{i_{k}}^{(j_{k})}),

where G_{l} = σ((X_{i}^{(1)}, ..., X_{i}^{(l)}), i = 1, ..., n). Let U_{n} = ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}i_{2}...i_{k}}(Z_{i_{1}}, ..., Z_{i_{k}})

= ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤l} δ_{i_{1}j_{1}}...δ_{i_{k}j_{k}}f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ⋯, X_{i_{k}}^{(j_{k})}).

Let D_{i} = (δ_{i1}, ...., δ_{il}). Since the D’s are independent of the X’s, if we let

g_{i_{1}...i_{k}}(D_{i_{1}}, ..., D_{i_{k}})

= ∑_{1≤j_{1},...,j_{k}≤l} δ_{i_{1}j_{1}}...δ_{i_{k}j_{k}}f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, ⋯, X_{i_{k}}^{(j_{k})}).

then, since

f_{i_{1}...i_{k}}(X_{i_{1}}, ..., X_{i_{k}}) = f_{i_{(π(1))}...i_{(π(k))}}(X_{i_{π(1)}}, ..., X_{i_{π(k)}}),

we have that,

g_{i_{1}...i_{k}}(D_{i_{1}}, ..., D_{i_{k}}) = g_{i_{(π(1))}...i_{(π(k))}}(D_{i_{π(1)}}, ..., D_{i_{π(k)}}).

Therefore, the two sided decoupling inequality in de la Peña (1992) can be applied and, for every convex increasing function Φ, every G_{l}-measurable function T, and k independent copies D_{i}^{(r)}, r = 1, ..., k of D_{i} there exists numerical constants A_{k}, B_{k} so that

E(Φ(A_{k}||T + ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} g_{i_{1}...i_{k}}(D_{i_{1}}, ..., D_{i_{k}})||)|G_{l})

≤ E(Φ(||T + ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} g_{i_{1}...i_{k}}(D_{i_{1}}^{(1)}, ..., D_{i_{k}}^{(k)})||)|G_{l})

≤ E(Φ(B_{k}||T + ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} g_{i_{1}...i_{k}}(D_{i_{1}}, ..., D_{i_{k}})||)|G_{l}).

This result with (11) shows that conditionally on G_{l}

(12)  ||U_{n} − T_{n}||_{4} ≤ σ_{l}^{−k} \frac{B_{k}}{A_{k}} ||U_{n} − T_{n}||_{2},

where

T_{n} = E(U_{n}|G_{l}) = (\frac{1}{l})^{k} ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤l} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, X_{i_{2}}^{(j_{2})}, ..., X_{i_{k}}^{(j_{k})}).

(See also the proofs of Lemma 2 and Lemma 6.5.1 of Kwapien and Woyczynski (1992)). Thus we have that,

(13)  P (||U_{n}|| ≥ ||T_{n}|||G_{l}) ≥ c_{k}^{−1}.

This follows from the use of (12) and Proposition 1 with a = T_{n} and Y = U_{n} − T_{n}. We also use the fact that for any random variable ξ and positive constant c, ||ξ||_{4} ≤ c||ξ||_{2} implies that ||ξ||_{2} ≤ c^{2}||ξ||_{1} (See also the proof of Lemma 2 for the approach to transfer the problem from one on Banach space valued random variables to one on real valued).

Integrating (13) over the set {||T_{n}|| ≥ t} we get P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, X_{i_{2}}^{(1)}, ..., X_{i_{k}}^{(1)})|| ≥ t)

= P (|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(Z_{i_{1}}, Z_{i_{2}}, ..., Z_{i_{k}})|| ≥ t)

≥ c_{k}^{−1}P (C_{k}|| ∑_{1≤i_{1}≠i_{2}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤l} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, X_{i_{2}}^{(j_{2})}, ..., X_{i_{k}}^{(j_{k})})|| ≥ t),

and Lemma 3 is proved.

The end of the proof of the lower bound follows by using induction and the iterative procedure introduced to obtain the proof of the lower bound multivariate decoupling inequality in de la Peña (1992). We give a different expression of the same proof, motivated by ideas from de la Peña, Montgomery-Smith and Szulga (1992). We will use S_{k} to denote the set of permutations of {1, ..., k}.

The Mazur-Orlicz formula tells us that for any 1 ≤ j_{1}, ..., j_{k} ≤ k that

∑_{0≤δ_{1},...,δ_{k}≤1}(−1)^{k−δ_{1}−...−δ_{k}}δ_{j_{1}} … δ_{j_{k}}

is 0 unless j_{1}, ..., j_{k} is a permutation of 1, ..., k, in which case it is 1. Hence

∑_{π∈S_{k}} f_{i_{1}...i_{k}}(X_{i_{1}}^{(π(1))}, …, X_{i_{k}}^{(π(k))})

= ∑_{0≤δ_{1},...,δ_{k}≤1}(−1)^{k−δ_{1}−...−δ_{k}} ∑_{1≤j_{1},...,j_{k}≤k} δ_{j_{1}} … δ_{j_{k}}f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, …, X_{i_{k}}^{(j_{k})}).

By the symmetry properties on f,

∑_{1≤i_{1}≠...≠i_{k}≤n}f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, …, X_{i_{k}}^{(k)})

= \frac{1}{k!} ∑_{1≤i_{1}≠...≠i_{k}≤n} ∑_{0≤δ_{1},...,δ_{k}≤1}(−1)^{k−δ_{1}−...−δ_{k}} ∑_{1≤j_{1},...,j_{k}≤k} δ_{j_{1}} … δ_{j_{k}}f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, …, X_{i_{k}}^{(j_{k})}).

Therefore,

Pr(∥ ∑_{1≤i_{1}≠...≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, …, X_{i_{k}}^{(k)})∥ ≥ t)

≤ ∑_{0≤δ_{1},...,δ_{k}≤1} Pr(∥ ∑_{1≤i_{1}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤k} δ_{j_{1}} … δ_{j_{k}}f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, …, X_{i_{k}}^{(j_{k})})∥ ≥ k!t/2^{k})

= ∑_{l=1}^{k} \binom{k}{l} Pr(∥ ∑_{1≤i_{1}≠...≠i_{k}≤n} ∑_{1≤j_{1},...,j_{k}≤l} f_{i_{1}...i_{k}}(X_{i_{1}}^{(j_{1})}, …, X_{i_{k}}^{(j_{k})})∥ ≥ k!t/2^{k}),

and this combined with Lemma 3 is sufficient to show the result.

7. References

1. de la Peña, V. H. (1992). Decoupling and Khintchine’s inequalities for U-statistics. Ann. Probab. 20 4, 1877-1892.

2. de la Peña, V. H., Montgomery-Smith and Szulga, J. (1992). Contraction and decoupling inequalities for multilinear forms and U-statistics. Preprint.

3. de la Peña, V. H. and Montgomery-Smith (1993). Bounds on the tail probability of U-statistics and quadratic forms. Preprint.

4. Giné, E. and Zinn, J. (1992). A remark on convergence in distribution of U-statistics. Preprint.

5. Kwapien, S. Szulga, J. (1991). Hypercontraction methods in moment inequalities for series of independent random variables in normed spaces. Ann. Probab. 19 (1), 369-379.

6. Kwapien, S. and Woyczynski, W. (1992). Random Series and Stochastic Integrals: Single and Multiple. Birkhauser.

7. McConnell, T. and Taqqu, M. (1986). Decoupling inequalities for multilinear forms in independent symmetric random variables. Ann. Probab. 14(3), 943-954.