BOUNDS ON THE TAIL PROBABILITY OF

U-STATISTICS AND QUADRATIC FORMS

Victor H. de la Peña and S. J. Montgomery-Smith

It is very common for expressions of the form:

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

to appear in Probability theory. Here {X_{i}} is a sequence of independent random variables taking values in a measurable space (S, S), and {f_{i_{1}...i_{k}}} is a sequence of measurable functions from S^{k} into a Banach Space (B, ∥ · ∥). Special cases of this type of random variable appear, for example, in Statistics in the form of U-statistics and quadratic forms. Throughout we will refer to them as generalized U-statistics.

There is great interest in decoupling such quantities, that is, by replacing the above quantity by the expression

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

where {X_{i}^{(1)}}, {X_{i}^{(2)}}, …, {X_{i}^{(k)}} are k independent copies of {X_{i}}.

Decoupling inequalities allow one to compare expressions of the first kind with expressions of the second kind. Such results permit the almost direct transfer of results for sums of independent random variables to the case of generalized Ustatistics. The reason being that conditionally on {X_{i}^{(2)}}, ..., {X_{i}^{(k)}}, the second sum above is a sum independent random variables. It is important to remark that such results have led to the development of several optimal results in the functional theory of U-Statistics (cf. [1] and [7]) and various other areas including the study of the invertibility of large matrices (cf. [2]), stochastic integration (cf. [10]), the study of integral operators on Lebesgue-Bochner spaces (cf. a result of T. R. McConnell and D. Burkholder found in [3]). Aside from those directly cited in this paper, other important contributors to the area of decoupling inequalities include A. de Acosta, P. Hitczenko, J. Jacod, A. Jakubowski, O. Kallenberg, M. Klass, W. Krakowiak, G. Pisier, J. Rosinski, and J. Szulga. Due to space restrictions, we refer the reader to [10] for a more complete account.

In this paper, we announce a result, which allows one to compare the tail probabilities of the above quantities. In particular, this inequality represents the definitive

Typeset by AMS-TEX

1991 Mathematics Subject Classification. AMS 1991 subject classifications: Primary 60E15.

Secondary 60D05, 60E05.

Key words and phrases. U-statistics, Quadratic Forms, Decoupling.

Both authors were supported by NSF grants.

generalization of the decoupling inequalities for multilinear forms of McConnell and Taqqu [11] and the more general decoupling inequalities for expectations of convex functions of U-statistics introduced in [4].

Theorem 1. There is a constant C_{k} > 0, depending only on k, such that for all n ≥ k,

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

(1)  ≤ 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), for all t > 0.

Moreover, the reverse inequality holds if the functions satisfy the condition

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

for all permutations π of {1, …, k}. That is,

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

(2)

≥ \frac{1}{C_{k}} P (\frac{1}{C_{k}} ∥ ∑_{1≤i_{1}≠···≠i_{k}≤n} f_{i_{1}...i_{k}}(X_{i_{1}}^{(1)}, …, X_{i_{k}}^{(k)})∥ ≥ t), for all t > 0.

Note that the expression i_{1} ≠ ⋯ ≠ i_{k} means that i_{r} ≠ i_{s} for all 1 ≤ r ≠ s ≤ k.

An example to illustrate this result can be found in the study of random graphs (see also [5]). Given a sequence of independent random points {X_{i}} in R^{N}, we might consider a measure of clustering

D_{1} = ∑_{1≤i≠j≤n} d(X_{i}, X_{j}),

where d(x, y) denotes the distance between x and y. The above result allows us to compare D_{1}, which measures the distance ‘within’ the graph formed by the random cluster of points {X_{i}}, to a quantity D_{2}, which is a measure of the distance ‘between’ the two independent clusters {X_{i}} and {X̃_{i}},

D_{2} = ∑_{1≤i≠j≤n} d(X̃_{i}, X_{j}),

where {X̃_{i}} is an independent copy of {X_{i}}. Then we have for all t > 0 that,

C_{2}^{−1}P (|D_{1}| ≥ C_{2}t) ≤ P (|D_{2}| ≥ t) ≤ C_{2}P (|D_{1}| ≥ C_{2}^{−1}t).

Other examples where U-statistics are used in graph theory may be found in [8].

We will prove the Theorem in the special case that k = 2. For ease of notation, let us suppose that X̃_{i} = X_{i}^{(1)}, and denote X_{i} = X_{i}^{(2)}. The proof of the more general result will appear elsewhere. We will use a sequence of lemmas. Following [6], our point of departure is equation (4) below which provides a partial decoupling result and focuses attention on a polarized version of the U-statistic kernel as the key element in the development of a solution of the problem at hand. Let

(3) T_{n} = ∑_{1≤i≠j≤n}{f_{ij}(X_{i}, X_{j}) + f_{ij}(X_{i}, X̃_{j}) + f_{ij}(X̃_{i}, X_{j}) + f_{ij}(X̃_{i}, X̃_{j})},

then by using the triangle inequality one obtains that,

(4)  \begin{matrix}P (∥ ∑_{1≤i≠j≤n} f_{ij}(X_{i}, X_{j}) + f_{ij}(X̃_{i}, X̃_{j})∥ ≥ t) ≤ \\ P (∥T_{n}∥ ≥ \frac{t}{3}) + 2P (∥ ∑_{1≤i≠j≤n} f_{ij}(X_{i}, X̃_{j})∥ ≥ \frac{t}{3}). \end{matrix}

This observation reduces the proof (1) to the problem of obtaining the bounds (5)

P (∥ ∑_{1≤i≠j≤n} f_{ij}(X_{i}, X_{j})∥ ≥ t) ≤ cP (c∥ ∑_{1≤i≠j≤n} f_{ij}(X_{i}, X_{j})+f_{ij}(X̃_{i}, X̃_{j})∥ ≥ t), and

(6)  P (∥T_{n}∥ ≥ t) ≤ cP (c∥ ∑_{1≤i≠j≤n} f_{ij}(X̃_{i}, X_{j})∥ ≥ t).

We obtain (5) by means of Lemma 1 (possibly of independent interest). The proof of (6) is somewhat involved. In obtaining it, we used (conditionally) an extension of the Paley-Zygmund inequality found in [10] in combination with a symmetrization identity similar to the one introduced in [12].

Lemma 1. Let X, Y be two i.i.d. random variables. Then

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

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

P (∥X∥ ≥ t)

= P (∥(X + Y) + (X + Z) − (Y + Z) ≥ 2t)

≤ P (∥X + Y ∥ ≥ \frac{2t}{3}) + P (∥X + Z∥ ≥ \frac{2t}{3}) + P (∥Y + Z∥ ≥ \frac{2t}{3})

= 3P (∥X + Y ∥ ≥ \frac{2t}{3}).

It is to be remarked that the very desirable ‘Universal Symmetrization Lemma’, P (∥X∥ ≥ t) ≤ cP (c∥X − Y ∥ ≥ t) is not true. This makes the above result all the more surprising.

The following is an observation found in Section 6.2 of [10] will be used in combination with Lemma 2 in proving Theorem 1.

Proposition 1. Let Y be any mean zero random variable with values in a Banach Space (B, ∥ · ∥). Then, for all a ∈ B, P (∥a + Y ∥ ≥ ∥a∥) ≥ \frac{κ}{4}, where, κ = inf_{x′∈B′} \frac{(E|x′(Y)|)^{2}}{E(x′(Y))^{2}} .

As a consequence of the above we obtain the following lemma.

Lemma 2. Let x, a_{i}, b_{ij} all belong to a Banach space (B, ∥ · ∥), with b_{ii} = 0. Let {ϵ_{i}} be a sequence of independent and symmetric Bernoulli random variables, that is, P (ϵ_{i} = 1) = P (ϵ_{i} = −1) = \frac{1}{2}. Then, for a universal constant c > 0,

P (∥x + ∑_{i=1}^{n} a_{i}ϵ_{i} + ∑_{1≤i≠j≤n} b_{ij}ϵ_{i}ϵ_{j}∥ ≥ ∥x∥) ≥ c^{−1}.

Proof. Suppose that a_{i}, b_{ij} are in R, then it follows easily from (1.4) of [9] (see also sections 6.2 and 6.5 of [10]) that

(E| ∑_{i=1}^{n} a_{i}ϵ_{i} + ∑_{1≤i≠j≤n} b_{ij}ϵ_{i}ϵ_{j}|^{4})^{\frac{1}{4}} ≤ c(E| ∑_{i=1}^{n} a_{i}ϵ_{i} + ∑_{1≤i≠j≤n} b_{ij}ϵ_{i}ϵ_{j}|^{2})^{1/2},

for some constant c > 0. Next, observe that ∥ξ∥_{4} ≤ c∥ξ∥_{2} implies that ∥ξ∥_{2} ≤ c^{2}∥ξ∥_{1} (since E(ξ)^{2} ≤ (E|ξ|)^{2/3} · (E(ξ)^{4})^{1/3}) . The result then follows by Proposition 1.

Proof of Theorem 1. We first transform the problem of proving (6) into a problem dealing (conditionally) with a non-homogeneous binomial in Bernoulli random variables. Let {ϵ_{i}} be a sequence of independent and symmetric Bernoulli random variables independent of {X_{i}}, {X̃_{i}}. Let (Z_{i}, Z̃_{i}) = (X_{i}, X̃_{i}) if ϵ_{i} = 1 and (Z_{i}, Z̃_{i}) = (X̃_{i}, X_{i}) if ϵ_{i} = −1. Then,

(8) \begin{aligned}4f_{ij}(Z̃_{i}, Z_{j}) & = \{(1 − ϵ_{i})(1 + ϵ_{j})f_{ij}(X_{i}, X_{j}) + (1 + ϵ_{i})(1 + ϵ_{j})f_{ij}(X̃_{i}, X_{j}) \\ & + (1 − ϵ_{i})(1 − ϵ_{j})f_{ij}(X_{i}, X̃_{j}) + (1 + ϵ_{i})(1 − ϵ_{j})f_{ij}(X̃_{i}, X̃_{j})\}. \end{aligned}

Setting G = σ(X_{i}, X̃_{i}; i = 1, ..., n) we get

(9) 4E(f_{ij}(Z̃_{i}, Z_{j})|G) = {f_{ij}(X_{i}, X_{j}) + f_{ij}(X̃_{i}, X_{j}) + f_{ij}(X_{i}, X̃_{j}) + f_{ij}(X̃_{i}, X̃_{j})}.

¿From Lemma 2, (3), (8) and (9), and letting x = T_{n}, it follows that for some c > 0,

P (4∥ ∑_{1≤i≠j≤n} f_{ij}(Z̃_{i}, Z_{j})∥ ≥ ∥T_{n}∥|G) ≥ c^{−1}.

Integrating over the set {∥T_{n}∥ ≥ t} we get

\frac{1}{c}P (∥T_{n}∥ ≥ t) ≤ P (4∥ ∑_{1≤i≠j≤n} f_{ij}(Z̃_{i}, Z_{j})∥ ≥ t) = P (4∥ ∑_{1≤i≠j≤n} f_{ij}(X̃_{i}, X_{j})∥ ≥ t),

since the sequence {(X_{i}, X̃_{i}), i = 1, ..., n} has the same distribution as {(Z_{i}, Z̃_{i}), i = 1, ..., n}. The proof is completed by using this inequality along with (4) and (5).

The proof of (2) is similar and uses an analogue of (8) concerning 4f(Z_{i}, Z_{j}). In obtaining this bound, one does not need to use Lemma 1. Instead one uses the symmetry condition on the functions f_{ij}, introduced after (1) and equation (3) to get,

P (∥ ∑_{1≤i≠j≤n} f_{ij}(X̃_{i}, X_{j})∥ ≥ t) = P (∥ ∑_{1≤i≠j≤n} f_{ij}(X_{i}, X̃_{j}) + f_{ij}(X̃_{i}, X_{j})∥ ≥ 2t)

≤ P (∥T_{n}∥ ≥ \frac{2}{3}t) + 2P (∥ ∑_{1≤i≠j≤n} f_{ij}(X_{i}, X_{j})∥ ≥ \frac{2}{3}t).

References

1. M. Arcones and E. Giné, Limit theorems for U-processes, Ann. Probab. 21 (3) (1993), 1495– 1592.

2. J. Bourgain and L. Tzafriri, Invertibility of “large” submatrices with applications to the geometry of Banach spaces and harmonic analysis, Israel J. Math. 57 (3) (1987), 137–224.

3. D. Burkholder, A geometric condition that implies the existence of certain singular integrals of Banach-space-valued functions, Conference on Harmonic Analysis in Honor of A. Zygmund (W. Beckner, A.P. Calderon, R. Fefferman, P. Jones, eds.), Wadsworth, 1983, pp. 270–286.

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

5. V.H. de la Peña, Nuevas desigualdades para U-estadísticas y gráficas aleatorias, Proceedings of the fourth Latin American Congress of Probability and Math. Stat. (CLAPEM), México City, September 1990, 1992.

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

7. E. Giné and J. Zinn, A remark on convergence in distribution of U-statistics, Ann. Probab. (to appear) (1992).

8. S. Janson and K. Nowicki, The asymptotic distributions of generalized U-statistics with applications to random graphs, Probab. Theory Relat. Fields 90 (1991), 341–375.

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

10. S. Kwapien and W. Woyczynski, Random series and stochastic integrals: simple and multiple, Birkhauser, NY, 1992.

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

12. D. Nolan and D. Pollard D, U-processes: rates of convergence, Annals of Stat. 15 (2) (1987), 780–799.

Department of Statistics, Columbia University, New York, New York 10027

E-mail address: vp@wald.stat.columbia.edu

Department of Mathematics, University of Missouri, Columbia, Missouri 65211

E-mail address: stephen@mont.cs.missouri.edu