A COMPARISON INEQUALITY FOR SUMS OF INDEPENDENT RANDOM VARIABLES^{∗}

STEPHEN J. MONTGOMERY-SMITH AND ALEXANDER R. PRUSS

Abstract. We give a comparison inequality that allows one to estimate the tail probabilities of sums of independent Banach space valued random variables in terms of those of independent identically distributed random variables. More precisely, let X_{1}, …, X_{n} be independent Banach-valued random variables. Let I be a random variable independent of X_{1}, …, X_{n} and uniformly distributed over {1, …, n}. Put X̃_{1} = X_{I}, and let X̃_{2}, …, X̃_{n} be independent identically distributed copies of X̃_{1}. Then, P (∥X_{1} + ⋯ + X_{n}∥ ≥ λ) ≤ cP (∥X̃_{1} + ⋯ + X̃_{n}∥ ≥ λ/c) for all λ ≥ 0, where c is an absolute constant.

The independent Banach-valued random variables X_{1}, …, X_{n} are said to regularly cover (the distribution of) a random variable Y provided that

E[g(Y)] = \frac{1}{n} ∑_{k=1}^{n} E[g(X_{k})],

for all Borel functions g for which either side is defined [8]. An easy way of constructing Y, given the independent Banach-valued random variables X_{1}, …, X_{n}, is to let I be a random variable independent of X_{1}, …, X_{n}, with values in {1, 2, …, n} and with each value having equal probability 1/n, and then put Y = X_{I}. It is easy to see that then X_{1}, …, X_{n} regularly cover Y. This construction will be useful for our proofs.

If the variables are real valued, then the regular covering condition is easily seen to be equivalent to the condition that the distribution

Date: October 15, 1999. 1991 Mathematics Subject Classification. Primary 60G50, 60E15; Secondary

60F15.

Key words and phrases. comparison inequalities, sums of independent random variables, sums of independent identically distributed random variables, rates of convergence in the law of large numbers.

*The first author was supported in part by the NSF and the Research Board of the University of Missouri.

2 STEPHEN J. MONTGOMERY-SMITH AND ALEXANDER R. PRUSS

function F of Y is the arithmetic mean of the respective distribution functions F_{1}, …, F_{n} of X_{1}, …, X_{n}.

A variable X′ is said to be a copy of X if it has the same distribution as X. The main purpose of this paper is then to prove the following result.

Theorem 1. There exists an absolute constant c ∈ (0, ∞) such that if X_{1}, …, X_{n} are independent Banach-valued random variables which regularly cover a random variable X̃_{1}, then:

P (∥X_{1} + ⋯ + X_{n}∥ ≥ λ) ≤ cP (∥X̃_{1} + ⋯ + X̃_{n}∥ ≥ λ/c), (1)

for all λ ≥ 0, where X̃_{2}, …, X̃_{n} are independent copies of X̃_{1}.

Remark 1. In the case where the random variables are symmetric, this was shown in [9] (strictly speaking, it was only shown in the real-valued case, but the proof also works for the Banach-valued case).

Remark 2. The inequality converse to (1) is false, even in the special cases of symmetric real random variables. For, suppose that c is an absolute constant such that

P (|X̃_{1} + ⋯ + X̃_{n}| ≥ λ) ≤ cP (|X_{1} + ⋯ + X_{n}| ≥ λ/c), (2)

for all λ ≥ 0, whenever the conditions of Theorem 1 hold with symmetric variables. Fix any n > max(1, c). Put X_{2} ≡ ⋯ ≡ X_{n} ≡ 0. Let X_{1} be such that P (X_{1} = 1) = P (X_{1} = −1) = \frac{1}{2}. Put λ = n. Then the right hand side of (2) is zero, since |X_{1}+⋯+X_{n}| ≡ 1. But the left hand side of (2) is non-zero, since it is easy to see that P (X̃_{i} = 1) = 1/2n for each i (as the X̃_{i} are identically distributed, and as X̃_{1} can be taken to be X_{I} where I is independent of everything else and uniformly distributed on {1, …, n}), so that P (|X̃_{1} + ⋯ + X̃_{n}| ≥ n) ≥ (1/2n)^{n} > 0.

Remark 3. The main consequence of Theorem 1 is that any upper bound on tail probabilities of sums of independent identically distributed random variables automatically gives a bound on tail probabilities of sums of non-identically distributed independent random variables. Our result explains why upper bounds for sums of independent identically distributed cases have so readily and consistently generalized to non-identically distributed cases. We cannot think of any new applications at this time.

A COMPARISON INEQUALITY 3

Remark 4. For a very simple, though not new, application, we give another proof of one side of a result from [8] on randomly sampled Riemann sums. Let f ∈ L^{2}[0, 1]. For 1 ≤ k ≤ n, let x_{nk} be uniformly distributed over [(k − 1)/n, k/n], and assume x_{n1}, …, x_{nn} are independent for each fixed n. Define the randomly sampled Riemann sum R_{n}f = n^{−1} ∑_{k=1}^{n} f(x_{nk}). Then the result says that R_{n}f converges almost surely to the Lebesgue integral A = ∫_{0}^{1} f. (For a converse in the case where all the x_{nk} are independent, not just for fixed n, see [8].) For, by Borel-Cantelli it suffices to show that

∑_{n=1}^{∞} P (|R_{n}f − A| ≥ ε) < ∞, (3)

for all ε > 0. Let X_{1}, X_{2}, … be independent identically distributed random variables with the same distribution as f. Note that f(x_{n1}), …, f(x_{nn}) regularly cover X_{1}, and f(x_{n1}) − A, …, f(x_{nn}) − A regularly cover X_{1}−A. Since f ∈ L^{2}, we have X_{1} having a finite second moment, and moreover E[X_{1}] = A, so that by the Hsu-Robbins law of large numbers [6] (see also [3, 4]), we have

∑_{n=1}^{∞} P (|(X_{1} − A) + ⋯ + (X_{n} − A)|/n ≥ ε) < ∞,

for all ε > 0. By Theorem 1 and the fact that f(x_{n1})−A, …, f(x_{n1})−A regularly cover X_{1} − A, we obtain (3).

To prove Theorem 1, we need some definitions and lemmata. If X is a random variable, then let X^{s} = X − X′ be the symmetrization of X, where X′ is an independent copy of X. We shall always choose symmetrizations so that we have (X_{1} + ⋯ + X_{k})^{s} = X_{1}^{s} + ⋯ + X_{k}^{s} whenever we need this identity.

Write ∥X∥_{p} = (E[∥X∥^{p}])^{1/p}, where ∥ · ∥ is the norm on the Banach space in which our random variables take values.

The following lemma must surely be well known. However, we could find no reference, and so we include a short proof.

Lemma 1. Let X be a Banach-valued random variable with ∥X∥_{2} < ∞. Then, ∥X∥_{2} ≤ ∥X^{s}∥_{2} + ∥E[X]∥ ≤ 3∥X∥_{2}

Proof. Let X′ be an independent copy of X so that X^{s} = X−X′. Let A be the sigma-algebra generated by X. Then E[X^{s} | A] = X − E[X′] =

4 STEPHEN J. MONTGOMERY-SMITH AND ALEXANDER R. PRUSS

X − E[X], and so

∥X∥_{2} = ∥E[X^{s} + E[X] | A]∥_{2} ≤ ∥X^{s} + E[X]∥_{2} ≤ ∥X^{s}∥_{2} + ∥E[X]∥,

where the first inequality used the fact that conditional expectation is a contraction on the Banach-valued L^{p} spaces, p ≥ 1 (see, e.g., [2, Chapter V, Theorem 4]). The rest of the Lemma follows from the triangle inequality.

Lemma 2. Let X_{1}, …, X_{n} be independent random variables, and let X̃_{1}, …, X̃_{n} be independent identically distributed random variables such that X_{1}, …, X_{n} regularly cover X̃_{1}. Put S_{n} = X_{1} + ⋯ + X_{n} and S̃_{n} = X̃_{1} + ⋯ + X̃_{n}. Then:

∥S_{n}∥_{2} ≤ 12∥S̃_{n}∥_{2}.

Proof. Let I_{1}, …, I_{n} be independent random variables uniformly distributed on the set {1, …, n}. Let {X_{i,j}}_{1≤i,j≤n} and {X′_{i,j}}_{1≤i,j≤n} be independent arrays of independent random variables, with the arrays independent of the I_{i}, and such that X_{i,j} and X′_{i,j} both have the same distribution as X_{j} for all i and j. Without loss of generality we can put X̃_{i} = X_{i,I_{i}}. Set X̃′_{i} = X′_{i,I_{i}}. Let S̃′_{n} = X̃′_{1} + ⋯ + X̃′_{n}. Let (X′_{1}, …, X′_{n}) be an independent copy of (X_{1}, …, X_{n}), and put S′_{n} = X′_{1} + ⋯ + X′_{n}. Observe that X_{1}−X′_{1}, …, X_{n}−X′_{n} regularly cover X̃_{i}−X̃′_{i} for all i, and that moreover the X_{i} − X′_{i} are symmetric. Thus, by [9, Proposition 1] (which though stated for real valued random variables, holds for the Banach-valued case as well, and with the same proof) we have:

∥S_{n} − S′_{n}∥_{2} ≤ 4∥S̃_{n} − S̃′_{n}∥_{2}. (4)

Also, it is clear that E[S_{n}] = E[S̃_{n}]. Combining this with Lemma 1, we see that:

∥S_{n}∥_{2} ≤ ∥S_{n} − S′_{n}∥_{2} + ∥E[S_{n}]∥ ≤ 4∥S̃_{n} − S̃′_{n}∥_{2} + 4∥E[S̃_{n}]∥ ≤ 12∥S̃_{n}∥_{2},

as desired.

The following Lemma is in effect a special case of a result of Hitczenko [5].

Lemma 3. Let X_{1}, …, X_{n} be independent identically distributed Banach-valued random variables with ∥X_{i}∥ < L almost surely for all i. Let S_{k} = X_{1} + ⋯ + X_{k}. Then:

∥S_{n}∥_{1} ≥ c_{1}∥S_{n}∥_{2} − c_{2}L,

where c_{1}, c_{2} ∈ (0, ∞) are absolute constants.

Proof. By the work of Hitczenko [5], we have that if S^{∗} = max_{k} ∥S_{k}∥ and X^{∗} = max_{k} ∥X_{k}∥, then for q ≥ p:

∥S^{∗}∥_{q} ≤ c_{3} \frac{q}{p}(∥S^{∗}∥_{p} + ∥X^{∗}∥_{q}),

for a finite absolute constant c_{3}. By [7, Corollary 4] we have ∥S^{∗}∥_{p} ≤ c_{4}∥S_{n}∥_{p} for an absolute constant c_{4}, as the X_{i} are identically distributed. The desired inequality easily follows from this if we let q = 2 and p = 1.

Proof of Theorem 1. Let I_{1}, …, I_{n}, {X_{i,j}}_{1≤i,j≤n}, {X′_{i,j}}_{1≤i,j≤n}, S′_{n} and S̃′_{n} be as in the proof of Lemma 2. As in that proof, X_{n,1} − X′_{n,1}, …, X_{n,n} − X_{n,n} regularly cover X_{n,I_{k}} − X′_{n,I_{k}} for any fixed k ≤ n. Applying [9, Proposition 1] (which works for Banach-valued variables as already stated), we see that

\begin{aligned}P (∥S_{n} − S′_{n}∥ ≥ λ) & ≤ 8P (∥S̃_{n} − S̃′_{n}∥ ≥ λ/2) \\ & ≤ 8P (∥S̃_{n}∥ ≥ λ/4) + 8P (∥S̃′_{n}∥ ≥ λ/4) \\ & ≤ 16P (∥S̃_{n}∥ ≥ λ/4), \end{aligned} (5)

for all λ, where the second inequality followed from the inequality that P (∥X^{s}∥ ≥ t) ≤ P (∥X∥ ≥ t/2) + P (∥X′∥ ≥ t/2) = 2P (∥X∥ ≥ t/2), where X′ is an independent copy of X such that X^{s} = X − X′. Note that S_{n}^{s} = S_{n} − S′_{n}.

Let M be a median of ∥S_{n}∥. It is easy to see that

P (|∥S_{n}∥ − M| ≥ λ) ≤ 2P (∥S_{n}^{s}∥ ≥ λ), (6)

for all λ. (For, if ∥S_{n}∥ − M ≥ λ, there is at least probability 1/2 that ∥S′_{n}∥ ≤ M in which case ∥S_{n} − S′_{n}∥ ≥ ∥S_{n}∥ − ∥S′_{n}∥ ≥ ∥S_{n}∥ − M ≥ λ and a similar calculation can be done if ∥S_{n}∥ − M ≤ −λ.)

We now claim that in general in our present setting:

P (∥S̃_{n}∥ ≥ εM) > δ, (7)

for absolute constants ε, δ ∈ (0, 1) to be determined later. (They will be determined in accordance with (12), (18), (20), (25) and (26), below). To prove (7), suppose that on the contrary we have:

P (∥S̃_{n}∥ ≥ εM) ≤ δ. (8)

6 STEPHEN J. MONTGOMERY-SMITH AND ALEXANDER R. PRUSS

Since the X̃_{i} are independent and identically distributed, by a maximal inequality for sums of independent and identically distributed random variables [7, Corollary 4] together with (8), we have:

P ( max_{1≤k≤n} ∥S̃_{k}∥ ≥ c_{1}εM) ≤ c_{1}P (∥S̃_{n}∥ ≥ εM) ≤ c_{1}δ, (9)

where c_{1} ∈ [1, ∞) is an absolute constant. By the elementary inequality

P ( max_{1≤k≤n} ∥U_{k}∥ ≥ 2t) ≤ P ( max_{1≤k≤n}∥∑_{i=1}^{k} U_{i}∥ ≥ t),

valid for all t if the U_{i} are independent (since if ∥U_{k}∥ ≥ 2t then ∥ ∑_{i=1}^{k} U_{i}∥ ≥ t or ∥ ∑_{i=1}^{k−1} U_{i}∥ ≥ t), it follows from (9) that

P ( max_{1≤k≤n} ∥X̃_{k}∥ ≥ 2c_{1}εM) ≤ c_{1}δ. (10)

Let L = 2c_{1}εM. Set Y_{k} = X_{k} ·1_{{∥X_{k}∥<L}}. Put Ỹ_{k} = X̃_{k} ·1_{{∥X̃_{k}∥<L}}. Note that Y_{1}, …, Y_{n} regularly cover Ỹ_{k} for each k. Let T_{n} = Y_{1} + ⋯ + Y_{n} and put T̃_{n} = Ỹ_{1} + ⋯ + Ỹ_{n}. By (10), we have:

P (⋃_{k=1}^{n}{X̃_{k} ≠ Ỹ_{k}}) ≤ c_{1}δ. (11)

Let p = P (∥X̃_{k}∥ ≥ L). Note that this does not depend on k since the X̃_{k} are identically distributed. Henceforth we will assume that

δ < 1/(2c_{1}). (12)

Now, if x ∈ [0, 1] is such that 1 − (1 − x)^{n} ≤ 1/2, then x ≤ 2n^{−1}(1 − (1 − x)^{n}). Then, since the left hand side of (11) equals 1 − (1 − p)^{n}, it follows from (11) that

p ≤ 2n^{−1}(1 − (1 − p)^{n}) ≤ 2n^{−1}c_{1}δ.

Combining this with (12) and the condition that X_{1}, …, X_{n} regularly cover X̃_{1}, we see that:

\begin{aligned}P (⋃_{k=1}^{n}\{X_{k} ≠ Y_{k}\}) & ≤ ∑_{k=1}^{n} P (X_{k} ≠ Y_{k}) \\ & = ∑_{k=1}^{n} P (∥X_{k}∥ ≥ L) \\ & = nP (∥X̃_{1}∥ ≥ L) = np ≤ 2c_{1}δ. \end{aligned} (13)

A COMPARISON INEQUALITY 7

Now, by (5), (6) and (8), it follows that

P (|∥S_{n}∥ − M| ≥ 4εM) ≤ 32δ.

Using (13), it then follows that: P (|∥T_{n}∥ − M| ≥ 4εM) ≤ (32 + 2c_{1})δ. (14) Moreover, by (8) and (11): P (∥T̃_{n}∥ ≥ εM) ≤ (1 + c_{1})δ. (15)

Observe that ∥Ỹ_{i}∥ < L almost surely. Lemma 3 then shows that: ∥T̃_{n}∥_{1} ≥ c_{2}∥T̃_{n}∥_{2} − c_{3}L, (16) where c_{2}, c_{3} ∈ (0, ∞) are absolute constants.

Now, by (14) we have: E[∥T_{n}∥^{2}] ≥ [1 − (32 + 2c_{1})δ](1 − 4ε)^{2}M^{2}. (17) Henceforth, we will assume that δ and ϵ are sufficiently small that (1 − (32 + 2c_{1})δ)(1 − 4ε)^{2} ≥ \frac{1}{4}. (18) Using Lemma 2 we see that E[∥T_{n}∥^{2}] ≤ 144E[∥T̃_{n}∥^{2}]. Combining this with (17) and (18), we see that ∥T̃_{n}∥_{2} ≥ M/24. (19) Recall that L = 2c_{1}εM, and choose ϵ ≤ c_{2}/(96c_{1}c_{3}), so that c_{3}L ≤ c_{2}M/48. This assumption is equivalent to: ε ≤ c_{2}/(96c_{1}c_{3}). (20) Thus by (19): c_{3}L ≤ \frac{1}{2}c_{2}∥T̃_{n}∥_{2}. (21) Then, by (16), ∥T̃_{n}∥_{1} ≥ \frac{1}{2}c_{2}∥T̃_{n}∥_{2}. (22) The elementary inequality P (|Ξ| ≥ λE[|Ξ|]) ≥ (1−λ)^{2}(E[|Ξ|])^{2}/E[|Ξ|^{2}] (see, e.g., [1, Exercise 3.3.11]) then implies that P (∥T̃_{n}∥ ≥ \frac{1}{2}∥T̃_{n}∥_{1}) ≥ (1 − \frac{1}{2})^{2} · \frac{1}{4}c_{2}^{2}. (23) Now, by (19) and (22) we have ∥T̃_{n}∥_{1} ≥ c_{2}M/48, so that (23) gives: P (∥T̃_{n}∥ ≥ c_{2}M/96) ≥ c_{2}^{2}/16. (24)

If we choose ε and δ such that

0 < ε ≤ c_{2}/96 (25)

and

0 < (1 + c_{1})δ < c_{2}^{2}/16 (26)

and satisfying the other conditions required in the above argument (namely (12), (18) and (20)), we will obtain from (24) a contradiction to (15). Hence, if we take ε and δ to be absolute constants in (0, 1) satisfying these assumptions, we obtain (7).

Now, combining (5) and (6), we see that:

P (∥S_{n}∥ − M ≥ λ) ≤ 32P (∥S̃_{n}∥ ≥ λ/4), (27)

for all λ. There are now two cases to be considered. Suppose first that λ ≤ 2M. Then using (7):

P (∥S_{n}∥ ≥ λ) ≤ 1 ≤ δ^{−1}P (∥S̃_{n}∥ ≥ εM) ≤ δ^{−1}P (∥S̃_{n}∥ ≥ ελ/2). (28)

On the other hand, suppose that λ > 2M. In that case if ∥S_{n}∥ ≥ λ then ∥S_{n}∥ − M > λ − λ/2 = λ/2, so that

P (∥S_{n}∥ ≥ λ) ≤ P (∥S_{n}∥ − M ≥ λ/2) ≤ 32P (∥S̃_{n}∥ ≥ λ/4), (29)

by (27). Inequality (1) follows from (28) for λ ≤ 2M and from (29) for λ > 2M, if we let c = max(32, 2/ε, δ^{−1}).

References

1. K. L. Chung, “A Course in Probability Theory,” 2nd ed., Academic Press, San Diego, 1974.

2. J. Diestel and J. J. Uhl, Jr., “Vector Measures,” Math. Surveys, vol. 15, Amer. Math. Soc., Providence, RI, 1977.

3. P. Erdős, On a theorem of Hsu and Robbins, Ann. Math. Statist. 20 (1949), 286–291.

4. , Remark on my paper “On a theorem of Hsu and Robbins”, Ann. Math. Statist. 21 (1950), 138.

5. P. Hitczenko, On a domination of sums of random variables by sums of conditionally independent ones, Ann. Probab. 22 (1994), 453–468.

6. P. L. Hsu and H. Robbins, Complete convergence and the law of large numbers, Proc. Nat. Acad. Sci. U.S.A. 33 (1947), 25–31.

7. S. J. Montgomery-Smith, Comparison of sums of independent identically distributed random vectors, Probab. Math. Statist. 14 (1993), 281–285.

8. A. R. Pruss, Randomly sampled Riemann sums and complete convergence in the law of large numbers for a case without identical distribution, Proc. Amer. Math. Soc. 124 (1996), 919–929.

9. , Comparisons between tail probabilities of sums of independent symmetric random variables, Ann. Inst. Poincaré Probab. Statist. 33 (1997), 651–671.

Department of Mathematics, University of Missouri, Columbia, MO 65211, U.S.A.

Department of Philosophy, University of Pittsburgh, Pittsburgh, PA 15260, U.S.A.

E-mail address: stephen@math.missouri.edu
E-mail address: pruss+@pitt.edu
URL: http://www.math.missouri.edu/~stephen
URL: http://www.pitt.edu/~pruss