Comparison of Sums of Independent Identically Distributed Random Variables

S.J. Montgomery-Smith*

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

ABSTRACT: Let S_{k} be the k-th partial sum of Banach space valued independent identically distributed random variables. In this paper, we compare the tail distribution of ∥S_{k}∥ with that of ∥S_{j}∥, and deduce some tail distribution maximal inequalities.

The main result of this paper was inspired by the inequality from [dP–M] that says that Pr(∥X_{1}∥ > t) ≤ 5 Pr(∥X_{1} + X_{2}∥ > t/2) whenever X_{1} and X_{2} are independent identically distributed. Such results for L_{p} (p ≥ 1) such as ∥X_{1}∥_{p} ≤ ∥X_{1} + X_{2}∥_{p} are straightforward, at least if X_{2} has zero expectation. This inequality is also obvious if either X_{1} is symmetric, or X_{1} is real valued positive. However, for arbritary random variables, this result is somewhat surprizing to the author. Note that the identically distributed assumption cannot be dropped, as one could take X_{1} = 1 and X_{2} = −1.

In this paper, we prove a generalization to sums of arbritarily many independent identically distributed random variables. Note that all results in this paper are true for Banach space valued random variables. The author would like to thank Victor de la Peña for helpful conversations.

Theorem 1. There exist universal constants c_{1} = 3 and c_{2} = 10 such that if X_{1}, X_{2}, … are independent identically distributed random variables, and if we set

S_{k} = ∑_{i=1}^{k} X_{i},

then for 1 ≤ j ≤ k

Pr(∥S_{j}∥ > t) ≤ c_{1} Pr(∥S_{k}∥ > t/c_{2}).

* Research supported in part by N.S.F. Grant DMS 9201357.

A.M.S. (1991 ) subject classification: 60-02 , 60G50.

SUMS OF I.I.D.R.V.

This result cannot be asymptotically improved. Consider, for example, the case where X_{1} = 1 with very small probability, and is zero otherwise. This shows that for the inequality to be true for all X_{1}, it must be that c_{2} must be larger than some universal constant for all j and k. Also, it is easy to see that c_{1} must be larger than some universal constant because it is easy to select X_{1} and t so that Pr(∥S_{j}∥ > t) is close to 1.

However, Latałla [L] has been able to obtain the same theorem with c_{1} = 4 and c_{2} = 5, or c_{1} = 2 and c_{2} = 7. In the case j = 1 and k = 2, he has shown that Pr(∥X_{1}∥ > t) ≤ 2 Pr(∥X_{1} + X_{2}∥ > 2t/3), and these constants cannot be improved.

In order to show this result, we will use the following definition. We will say that x is a t-concentration point for a random variable X if Pr(∥X − x∥ ≤ t) > 2/3.

Lemma 2. If x is a t-concentration point for X, and y is a t-concentration point for Y, and z is a t-concentration point for X + Y, then ∥x + y − z∥ ≤ 3t.

Proof:

Pr(∥x + y − z∥ > 3t) ≤ Pr(∥X − x + Y − y − (X + Y − z)∥ > 3t)
≤ Pr(∥X − x∥ > t) + Pr(∥Y − y∥ > t) + Pr(∥X + Y − z∥ > t)
< 1.

Hence Pr(∥x + y − z∥ ≤ 3t) > 0. Since x, y and z are fixed vectors, the result follows.

Corollary 3. If X_{1}, X_{2}, … are independent identically distributed random variables, and if the partial sums S_{j} = ∑_{i=1}^{j} X_{i} have t-concentration points s_{j} for 1 ≤ j ≤ k, then ∥ks_{j} − js_{k}∥ ≤ 3(k + j)t.

Proof: We prove the result by induction. It is obvious if j = k. Otherwise,

∥js_{k} − ks_{j}∥ ≤ ∥js_{k−j} − (k − j)s_{j}∥ + ∥js_{k} − js_{k−j} − js_{j}∥
≤ 3(k − j + j)t + 3jt = 3(k + j)t.

(The observant reader will notice that we are, in fact, following the steps of Euclid’s algorithm. The same proof could show ∥ks_{j} − js_{k}∥ ≤ 3(j + k − 2h)t where h is the highest common factor of j and k.)

MONTGOMERY-SMITH

Proof of Theorem 1: We consider three cases. First suppose that Pr(∥S_{k−j}∥ > 9t/10) ≤ 1/3. Note that S_{k} − S_{j} is independent of S_{j}, and identically distributed to S_{k−j}. Then

Pr(∥S_{j}∥ > t) ≤ 3/2 Pr(∥S_{j}∥ > t and ∥S_{k} − S_{j}∥ ≤ 9t/10) ≤ 3/2 Pr(∥S_{k}∥ > t/10). For the second case, suppose that there is a 1 ≤ i ≤ k such that S_{i} does not have any

(t/10)-concentration point. Then

Pr(∥S_{i} + X_{i+1} + … + X_{k}∥ > t/10 | σ(X_{i+1}, …, X_{k})) ≥ 1/3,

and hence Pr(∥S_{k}∥ > t/10) ≥ 1/3 ≥ 1/3 Pr(∥S_{i}∥ > t).

Finally, we are left with the third case where Pr(∥S_{k−j}∥ > 9t/10) > 1/3, and S_{i} has a (t/10)-concentration point s_{i} for all 1 ≤ i ≤ k. Clearly ∥s_{k−j}∥ ≥ 8t/10. Also, by Corollary 3,

∥s_{k}∥ ≥ \frac{k}{k − j} ∥s_{k−j}∥ − \frac{3(2k − j)t}{10(k − j)} ≥ \frac{8kt}{10(k − j)} − \frac{6kt}{10(k − j)} ≥ \frac{2t}{10}.

Therefore, Pr(∥S_{k}∥ ≥ t/10) ≥ Pr(∥S_{k} − s_{k}∥ ≤ t/10) ≥ 2/3 ≥ 2/3 Pr(∥S_{j}∥ > t), and we are done.

One might be emboldened to conjecture the following. Suppose that X_{1}, X_{2}, … are independent identically distributed random variables, and that α_{i} > 0. Let

S_{k} = ∑_{i=1}^{k} α_{i}X_{i}.

Then one might conjecture that there is a universal constant such that for 1 ≤ j ≤ k

Pr(∥S_{j}∥ > t) ≤ c Pr(∥S_{k}∥ > t/c). As it turns out, this is not the case. Let Y_{1}, Y_{2}, … be real valued independent identi-

cally distributed random variables such that

Pr(Y_{i} = N − 1) = 1/N
Pr(Y_{i} = −1) = (N − 1)/N.

Then by the central limit theorem, there exists M ≥ N^{3} such that

Pr (|\frac{1}{M^{2/3}} ∑_{i=1}^{M} Y_{i}| > \frac{1}{N} ) ≤ \frac{1}{N} .

Now let X_{i} = Y_{i} + 1/M^{1/3}, and let

S_{M} = \frac{1}{M^{2/3}} ∑_{i=1}^{M} X_{i}.

Then Pr(|S_{M}| > 1/2) ≥ 1 − 1/N, whereas Pr(|S_{M} + X_{M+1}| > 3/N) ≤ 2/N.

Theorem 1 has several corollaries.

Corollary 4. There is a universal constant c such that if X_{1}, X_{2}, … are independent identically distributed random variables, and if we set

S_{k} = ∑_{i=1}^{k} X_{i},

then

Pr( sup_{1≤j≤k} ∥S_{j}∥ > t) ≤ c Pr(∥S_{k}∥ > t/c).

Latalo [L] has been able to obtain this result with c_{1} = 4 and c_{2} = 6, or with c_{1} = 2 and c_{2} = 8.

Proof: This follows from Proposition 1.1.1 of [K–W], that states that if X_{1}, X_{2}, … are independent (not necessarily identically distributed), and if S_{k} = ∑_{i=1}^{k} X_{i}, then

Pr( sup_{1≤j≤k} ∥S_{j}∥ > t) ≤ 3 sup_{1≤j≤k} Pr(∥S_{j}∥ > t/3).

It is also possible to prove this result directly using the techniques of the proof of Theorem 1. The third case only requires that Pr(∥S_{k−j}∥ > 9t/10) > 1/3 for one j = 1, 2, …, k. Hence, for the first case we may assume that Pr(∥S_{k} − S_{j}∥ > 9t/10) ≤ 1/3 for all 1 ≤ j ≤ k. Let A_{j} be the event {∥S_{i}∥ ≤ t for all i < j and ∥S_{j}∥ > t}. Then

Pr(A_{j}) ≤ 3/2 Pr(A_{j} and ∥S_{k} − S_{j}∥ ≤ 9t/10) ≤ 3/2 Pr(A_{j} and ∥S_{j}∥ > t/10).

Summing over j, the result follows.

Corollary 5. There is a universal constant c such that if X_{1}, X_{2}, … are independent identically distributed random variables, and if |α_{i}| ≤ 1, then

Pr (∥∑_{i=1}^{k} α_{i}X_{i}∥ > t) ≤ c Pr (∥∑_{i=1}^{k} X_{i}∥ > t/c) .

Proof: The technique used in this proof is well known (see for example [KW], Proposition 1.2.1), but is included for completness.

By taking real and imaginary parts of α_{i}, we may suppose that the α_{i} are real. Without loss of generality, 1 ≥ α_{1} ≥ … ≥ α_{k} ≥ −1. Then we may write α_{j} = −1 + ∑_{i=j}^{k} σ_{i}, where σ_{i} ≥ 0. Thus ∑_{i=1}^{k} |σ_{i}| ≤ 2, and hence

∥∑_{j=1}^{k} α_{j}X_{i}∥ = ∥∑_{j=1}^{k}(−1 + ∑_{i=j}^{k} σ_{i})X_{i}∥

= ∥−(∑_{i=1}^{k} X_{i}) + (∑_{j=1}^{k} σ_{j} ∑_{i=1}^{j} X_{i})∥

≤ ∥∑_{i=1}^{k} X_{i}∥ + (∑_{j=1}^{k} |σ_{j}|) sup_{1≤j≤k} ∥∑_{i=1}^{j} X_{i}∥.

Applying Corollary 4, the result follows.

Corollary 6. There are universal constants c_{1} and c_{2} such that if X_{1}, X_{2}, … are independent identically distributed random variables, and if we set

S_{k} = ∑_{i=1}^{k} X_{i},

then for 1 ≤ k ≤ j

Pr(∥S_{j}∥ > t) ≤ c_{1}j/k Pr(∥S_{k}∥ > kt/c_{2}j).

Proof: Let m be the least integer such that mk ≥ j. By Theorem 1, it follows that Pr(∥S_{j}∥ > t) ≤ c Pr(∥S_{mk}∥ > t/c). That Pr(∥S_{mk}∥ > t) ≤ m Pr(∥S_{k}∥ > t/m) is straightforward.

The example where X_{1} is constant shows that c_{2} cannot be made smaller than some universal constant. The example where X_{1} = 1 with very small probability and is zero otherwise shows the same is true for c_{1}.

References

dP–M V.H. de la Peña and S.J. Montgomery-Smith, Bounds on the tail probability of U-statistics

and quadratic forms, preprint.

K–W S. Kwapień and W.A. Woyczyński, Random Series and Stochastic Integrals: Simple and

Multiple, Birkhauser, NY (1992).

L  R. Latała, A paper, Warsaw University Preprint (1993).