The Distribution of Rademacher Sums

S.J. Montgomery-Smith, Department of Mathematics, University of Missouri at Columbia, Columbia, MO 65211, U.S.A.

Abstract We find upper and lower bounds for Pr (∑ ±x_{n} ≥ t), where x_{1}, x_{2}, … are real numbers. We express the answer in terms of the K-interpolation norm from the theory of interpolation of Banach spaces.

Acknowledgements All the work in this paper appears in my Ph.D. thesis [6], taken at Cambridge University under the supervision of Dr. D.J.H. Garling, to whom I would like to express my thanks. I would also like to express my gratitude to the Science and Engineering Research Council, who financed my studies in Cambridge.

Primary A.M.S. Classification 60C05

Secondary A.M.S. Classification 60G50, 60J15

Key Words and Phrases Rademacher Sum, Holmstedt’s formula.

Revised August 30, 1989 Introduction Throughout this paper, we let ε_{1}, ε_{2}, … be independent Bernoulli random variables (that is, Pr(ε_{n} = 1) = Pr(ε_{n} = −1) = 1/2). We are going to look for upper and lower bounds for Pr (∑ ε_{n}x_{n} > t), where x_{1}, x_{2}, … is a sequence of real numbers such that x = (x_{n})_{n=1}^{∞} ∈ l_{2}.

Our first upper bound is well known (see, for example, Chapter II, §59 of [5]):

Pr (∑ ε_{n}x_{n} > t ∥x∥_{2}) ≤ e^{− \frac{1}{2} t^{2}}.  (1)

However, if ∥x∥_{1} < ∞, this cannot also provide a good lower bound, because then we have another upper bound:

Pr (∑ ε_{n}x_{n} > ∥x∥_{1}) = 0.  (2)

To look for lower bounds, we might first consider using some version of the central limit theorem. For example, using Theorem 7.1.4 of [2], it can be shown that for some constant c we have

|Pr (∑ ε_{n}x_{n} > t ∥x∥_{2}) − \frac{1}{\sqrt{2π}} ∫_{t}^{∞} e^{− \frac{1}{2} s^{2}} ds| ≤ c (\begin{matrix}∥x∥ & _{3} \\ ∥x∥ & _{2} \end{matrix} )^{3}.

Thus, for some constant c we have that if t ≤ c^{−1}(log ∥x∥_{3} / ∥x∥_{2})^{\frac{1}{2}} , then

Pr (∑ ε_{n}x_{n} > t ∥x∥_{2}) ≥ c^{−1} ∫_{t}^{∞} e^{− \frac{1}{2} s^{2}} ds ≥ \frac{c^{−2}e^{− \frac{1}{2} t^{2}}}{t} .

However, we should hope for far more. From (1) and (2), we could conjecture something like

Pr (∑ ε_{n}x_{n} > c^{−1} inf{∥x∥_{1} , t ∥x∥_{2}}) ≥ c^{−1}e^{−ct^{2}}.

Actually such a conjecture is unreasonable—one should not take infimums of norms, but instead one should consider the following quantity:

K(x, t; l_{1}, l_{2}) = K_{1,2}(x, t) = inf{ ∥x′∥_{1} + t ∥x′′∥_{2} : x′, x′′ ∈ l_{2}, x′ + x′′ = x}.

This norm is well known to the theory of interpolation of Banach spaces (see, for example [1] or [3]). For small t, this norm looks a lot like t ∥x∥_{2}, but as t gets much larger, it starts to look more like ∥x∥_{1}. In fact, there is a rather nice approximate formula due to T. Holmstedt (Theorem 4.1 of [3]): if we write (x_{n}^{∗})_{n=1}^{∞} for the sequence (|x_{n}|)_{n=1}^{∞} rearranged into decreasing order, then

c^{−1}K_{1,2}(x, t) ≤ ∑_{n=1}^{⌊t^{2}⌋} x_{n}^{∗} + t ( ∑_{n=⌊t^{2}⌋+1}^{∞}(x_{n}^{∗})^{2})^{\frac{1}{2}} ≤ K_{1,2}(x, t),

where c is a universal constant.

In this paper, we will prove the following result.

Theorem. There is a constant c such that for all x ∈ l_{2} and t > 0 we have

Pr (∑ ε_{n}x_{n} > K_{1,2}(x, t)) ≤ e^{− \frac{1}{2} t^{2}}

and

Pr (∑ ε_{n}x_{n} > c^{−1}K_{1,2}(x, t)) ≥ c^{−1}e^{−ct^{2}}.

An interesting example is x = (n^{−1})_{n=1}^{∞}. Then c^{−1} log t ≤ K_{1,2}(x, t) ≤ c log t, and hence

c^{−1} exp(− exp(ct)) ≤ Pr (∑ ε_{n}n^{−1} > t) ≤ c exp(− exp(c^{−1}t)).

This is quite different behaviour then that which we might have expected from the central limit theorem.

We might also consider x = (n^{− \frac{1}{p}})_{n=1}^{∞}, where 1 < p < 2. This example leads us to deduce Proposition 2.1 of [7]. More involved methods allow us to rederive the results of [8] (which include the above mentioned result from [7]). We do not go into details.

We also deduce the following corollary.

Corollary. There is a constant c such that for all x ∈ l_{2} and 0 < t ≤ ∥x∥_{2} / ∥x∥_{∞} we have

Pr (∑ ε_{n}x_{n} > c^{−1}t ∥x∥_{2}) ≥ c^{−1}e^{−ct^{2}}.

Proof: It is sufficient to show that there is a constant c such that if 0 < t ≤ ∥x∥_{2} / ∥x∥_{∞}, then

K_{1,2}(x, t) ≤ t ∥x∥_{2} ≤ c K_{1,2}(x, t).

The left hand inequality follows straight away from the definition of K_{1,2}(x, t). The right hand side follows easily from Holmstedt’s formula; obviously if t < 1, and otherwise because

∑_{n=1}^{⌊t^{2}⌋} x_{n}^{∗} ≥ ⌊t^{2}⌋\frac{∥x∥_{2}}{t} ≥ \frac{t}{2} ∥x∥_{2} .

Proof of Theorem In order to prove the theorem, we will need some new norms on l_{2}, and a few lemmas. Definition. For x ∈ l_{2} and t > 0, define the norm

J(x, t; l_{∞}, l_{2}) = J_{∞,2}(x, t) = max{∥x∥_{∞} , t ∥x∥_{2}}.

Lemma 1. For t > 0, the spaces (l_{2}, K_{1,2}( · , t)) and (l_{2}, J_{∞,2}( · , t^{−1})) are dual to one another, that is, for x ∈ l_{2} we have

K_{1,2}(x, t) = sup { ∑ x_{n}y_{n} : y ∈ l_{2}, J_{∞,2}(y, t^{−1}) ≤ 1} .

Proof: This is elementary (see, for example Chapter 3, Exercise 1–6 of [1]). Definition. For x ∈ l_{2} and t ∈ N, define the norm

∥x∥_{P (t)} = sup \{ ∑_{m=1}^{t} ( ∑_{n∈B_{m}} |x_{n}|^{2})^{\frac{1}{2}} \} ,

where the supremum is taken over all disjoint subsets, B_{1}, B_{2}, …, B_{t} ⊆ N. Lemma 2. If x ∈ l_{2} and t^{2} ∈ N, then

∥x∥_{P (t^{2})} ≤ K_{1,2}(x, t) ≤ \sqrt{2} ∥x∥_{P (t^{2})} .

Proof: To show the first inequality, note that we have

∥x∥_{P (t^{2})} ≤ ∥x∥_{1} and ∥x∥_{P (t^{2})} ≤ t ∥x∥_{2} .

Hence

K_{1,2}(x, t) = inf{ ∥x′∥_{1} + t ∥x′′∥_{2} : x′ + x′′ = x}
≥ inf{ ∥x′∥_{P (t^{2})} + ∥x′′∥_{P (t^{2})} : x′ + x′′ = x}
≥ ∥x∥_{P (t^{2})} ,

where the last step follows by the triangle inequality.

For the second inequality, we start by using Lemma 1. For any δ > 0, let y ∈ l_{2} be such that

(1 − δ)K_{1,2}(x, t) ≤ ∑ x_{n}y_{n} and J_{∞,2}(y, t^{−1}) = 1.

Now pick numbers n_{0}, n_{1}, n_{2}, …, n_{t^{2}} ∈ {0, 1, 2, …, ∞} by induction as follows: given 0 = n_{0} < n_{1} < … < n_{m}, let

n_{m+1} = 1 + sup { ν : ∑_{n=n_{m}+1}^{ν} |y_{n}|^{2} ≤ 1} .

Since ∥y∥_{∞} ≤ 1, we have that ∑_{n=n_{m}+1}^{n_{m+1}} |y_{n}|^{2} ≤ 2. Also, as ∥y∥_{2} ≤ t, it follows that n_{t^{2}} = ∞. Therefore

(1 − δ)K_{1,2}(x, t) ≤ ∑ x_{n}y_{n}

≤ ∑_{m=1}^{t^{2}} ( ∑_{n=n_{m−1}+1}^{n_{m}} |y_{n}|^{2})^{\frac{1}{2}} ( ∑_{n=n_{m−1}+1}^{n_{m}} |x_{n}|^{2})^{\frac{1}{2}}

≤ \sqrt{2} ∥x∥_{P (t^{2})} .

Since this is true for all δ > 0, the result follows.

The following lemma is due to Paley and Zygmund.

Lemma 3. If x ∈ l_{2}, then given 0 < λ < 1 we have

Pr (∑ ε_{n}x_{n} > λ ∥x∥_{2}) ≥ \frac{1}{3}(1 − λ^{2})^{2}.

Proof: See Chapter 3, Theorem 3 of [4].

Now we proceed with the proof of the theorem. First we will show that

Pr (∑ ε_{n}x_{n} > K_{1,2}(x, t)) ≤ e^{− \frac{1}{2} t^{2}}.

Given δ > 0, let x′, x′′ ∈ l_{2} be such that x′ + x′′ = x, and

(1 + δ)K_{1,2}(x, t) > ∥x′∥_{1} + t ∥x′′∥_{2} .

Then

Pr (∑ ε_{n}x_{n} > (1 + δ)K_{1,2}(x, t)) ≤ Pr (∑ ε_{n}x′_{n} > ∥x′∥_{1})
+ Pr (∑ ε_{n}x′′_{n} > t ∥x′′∥_{2})

≤ 0 + e^{− \frac{1}{2} t^{2}}, where the last inequality follows from equations (1) and (2) above. Letting δ → 0, the result follows.

Now we show that for some constant c we have

Pr (∑ ε_{n}x_{n} > c^{−1}K_{1,2}(x, t)) ≥ c^{−1}e^{−ct^{2}}.

First, let us assume that t^{2} ∈ N. Given δ > 0, let B_{1}, B_{2}, …, B_{t^{2}} ⊆ N be disjoint subsets such that ⋃_{m=1}^{t^{2}} B_{m} = N and

∥x∥_{P (t^{2})} ≤ (1 + δ) ∑_{m=1}^{t^{2}} ( ∑_{n∈B_{m}} |x_{n}|^{2})^{\frac{1}{2}} .

Then Pr (∑ ε_{n}x_{n} > \frac{1}{2}K_{1,2}(x, t)) ≥ Pr (∑ ε_{n}x_{n} > \frac{1}{\sqrt{2}} ∥x∥_{P (t^{2})})

≥ Pr ( ∑_{m=1}^{t^{2}} ∑_{n∈B_{m}} ϵ_{n}x_{n} ≥ \frac{1}{\sqrt{2}}(1 + δ) ∑_{m=1}^{t^{2}} ( ∑_{n∈B_{m}} |x_{n}|^{2})^{\frac{1}{2}} )

≥ ∏_{m=1}^{t^{2}} Pr ( ∑_{n∈B_{m}} ε_{n}x_{n} ≥ \frac{1}{\sqrt{2}}(1 + δ) ( ∑_{n∈B_{m}} |x_{n}|^{2})^{\frac{1}{2}} )

≥ (\frac{1}{3} (1 − \frac{1}{2}(1 + δ)^{2})^{2})^{t^{2}} ,

where the last step is from Lemma 3. If we let δ → 0, then we see that

Pr (∑ ε_{n}x_{n} > \frac{1}{2}K_{1,2}(x, t)) ≥ exp(−(log 12) t^{2}).

This proves the result for t^{2} ∈ N. For t ≥ 1, note that

K_{1,2}(x, t) ≤ K_{1,2}(x, ⌈t⌉)  and  ⌈t⌉^{2} ≤ 4t^{2},

and hence the result follows (with c = 4 log 12). For t < 1, the result may be deduced straightaway from Holmstedt’s formula and Lemma 3.

References

[1] C. Bennett and R. Sharpley, Interpolation of Operators, Academic Press.
[2] K.L. Chung, A Course in Probability Theory (2nd. Ed.), Academic Press.

[3] T. Holmstedt, Interpolation of quasi-normed spaces, Math. Scand. 26 (1970), 177–199.

[4] J-P. Kahane, Some Random Series of Functions, Cambridge studies in advanced mathematics 5.

[5] P-A. Meyer, Martingales and Stochastic Integrals I, Springer-Verlag 284.

[6] S.J. Montgomery-Smith, The Cotype of Operators from C(K), Ph.D. thesis, Cambridge, August 1988.

[7] G. Pisier, De nouvelles caractérisations des ensembles de Sidon, Mathematical Analysis and Applications, Advances in Math. Suppl. Stud., 7B (1981), 686–725.

[8] V.A. Rodin and E.M. Semyonov, Rademacher series in symmetric spaces, Analyse Math. 1 (1975), 207–222.