Georgian Mathematical Journal Volume 8 (2001), Number 2, 237–244

ON THE TAIL ESTIMATION OF THE NORM OF RADEMACHER SUMS^{∗}

S. CHOBANYAN AND H. SALEHI

Abstract. The main aim of this paper is to prove a bilateral inequality for P [∥ ∑_{1}^{n} a_{k}r_{k}∥ > t], where t > 0, (a_{k}) are elements of a normed space, while (r_{k}) are Rademacher functions. Then this inequality is applied for estimation of E∥ ∑_{1}^{n} a_{k}r_{k}∥. As another corollary we give a maximal inequality for exchangeable random variables that recently has been published in [4].

2000 Mathematics Subject Classification: 60B12, 60G09. Key words and phrases: Rademacher sums, tail estimation, exchangeable system of random variables, maximal inequality.

1. The Main Assertion

Theorem. Let (a_{1}, …, a_{2n}) be a collection of elements of a normed space X (real or complex), r_{1}, …, r_{2n} be Rademacher functions (i.i.d. random variables taking only two values −1 and +1 with equal probabilities) defined on a probability space (Ω, A, P).

(a) If ∑_{1}^{2n} a_{k} = 0, then for any t > 0 the following bilateral inequality holds

c m[∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{c} ] ≤ P [∥ ∑_{1}^{2n} a_{k}r_{k}∥ > t]
≤ C m[∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{C} ],  (1)

where c, C are absolute constants, while m is the uniform distribution on the set of all collections of integers 1 ≤ k_{1} < k_{2} < ⋯ < k_{n} ≤ 2n.

(b) The right-hand side inequality takes place in general, without the assump-

tion ∑_{1}^{2n} a_{k} = 0 (may be with a different absolute constant C).

* A general source for this article is the reference [4]; its first author is Professor N. Vakhania to whom this work is dedicated.

ISSN 1072-947X / $8.00 / \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag www.heldermann.de

Proof. First let us prove the left-hand side inequality of (a). Denote by μ the uniform distribution on the set Π of all permutations of {1, …, 2n}. Then we have for any collection of signs θ = (θ_{1}, …, θ_{n})

μ [∥ ∑_{1}^{n} a_{π(k)}∥ > t] = μ [∥ ∑_{1}^{n}(a_{π(k)} − a_{π(n+k)})θ_{k}∥ > 2t]

(since ∑_{1}^{2n} a_{i} = 0). This gives

μ [∥ ∑_{1}^{n} a_{π(k)}∥ > t] = P × μ [∥ ∑_{1}^{n}(a_{π(k)} − a_{π(n+k)})r_{k}∥ > 2t]

≤ P × μ [∥ ∑_{1}^{n} a_{π(k)}r_{k}∥ > t] + P × μ [∥ ∑_{1}^{n} a_{π(n+k)}r_{k}∥ > t]

(due to the Lévy inequality and Fubini theorem)

P × μ [∥ ∑_{1}^{n} a_{π(k)}r_{k}∥ > t] + P × μ [∥ ∑_{1}^{n} a_{π(k)}r_{k}∥ > t]

≤ 4P × μ [∥ ∑_{1}^{2n} a_{π(k)}r_{k}∥ > t] .

Now the use of the obvious equality

μ [∥ ∑_{1}^{n} a_{π(k)}∥ > t] = m [∥ ∑_{1}^{n} a_{k_{l}} ∥ > t], t > 0,

proves the left-hand side inequality of (1) with c = \frac{1}{4} .

To prove the right-hand side inequality of (a), denote

ξ(ω) = ∑_{1}^{2n} a_{k}r_{k}(ω) , η(π, ω) = ∑_{1}^{n}(a_{π(2k−1)} − a_{π(2k)})r_{π(2k−1)}(ω) , (2)

where π : {1, …, 2n} → {1, …, 2n} is a permutation. One can easily verify that

\frac{1}{(2n)!} ∑_{π} η(π, ω) = \frac{n}{2n − 1}ξ(ω) .  (3)

As above, μ denotes the uniform distribution on the set Π of all permutations. Then (3) means that E_{μ} η(π, ω) = \frac{n}{2n−1} ξ(ω), where E_{Q} denotes the expectation w.r.t. the probability measure Q; we omit the index when Q is assumed.

Let us exploit the following Kahane inequality for a positive random variable Y:

P [Y > λEY] ≥ (1 − λ)^{2} \frac{(EY)^{2}}{EY^{2}} ,

ON THE TAIL ESTIMATION OF THE NORM 239

where 0 < λ < 1 is any real (see [3, Ch. I]). Then for any λ we can write

μ \{π : ∥η(π, ω)∥ > λ\frac{n}{2n − 1}∥ξ(ω)∥\} ≥ μ \{π : ∥η(π, ω)∥ > λE_{μ}∥η(π, ω)∥\}
≥ \frac{(1 − λ)^{2}(E_{μ} ∥η(π, ω)∥)^{2}}{E_{μ} ∥η(π, ω)∥^{2}} ≥ \frac{(1 − λ)^{2} ∥ξ(ω)∥^{2}}{4E_{μ} ∥η(π, ω)∥^{2}} .  (4)

On the other hand, for any s > 0, by the Markov inequality, P {ω : (E_{μ}∥η(π, ω)∥^{2})^{1/2}I_{[∥ξ(ω)∥>t]} > s}

≤ \frac{(E_{P} E_{μ} ∥η∥^{2})^{1/2}P^{1/2}[∥ξ(ω)∥ > t]}{s} .  (5)

According to the definition of η(π, ω) (see (2)), and the triangle inequality,

(E_{P} ∥η(π, ω)∥^{2})^{1/2} ≤ (E_{P} ∥ ∑_{1}^{n} a_{π(2k−1)}r_{π(2k−1)}∥^{2})^{1/2}

+ (E_{P} ∥ ∑_{1}^{n} a_{π(2k)}r_{π(2k)}∥^{2})^{1/2}

(by the Levy inequality)

≤ 2(2E_{P} ∥ ∑_{1}^{2n} a_{k}r_{k}∥^{2})^{1/2} ,

which results in

E_{P} ∥η(π, ω)∥^{2} ≤ 8E_{P} ∥ ∑_{1}^{2n} a_{k}r_{k}∥^{2} .

Now we can go on in (5):

≤ \frac{1}{s} 8(E∥ξ∥^{2})^{1/2} P^{1/2}[∥ξ∥ > t] .  (6)

Assume that E∥ξ∥^{2} = 1 and put s = c_{0}P^{−1/2}[∥ξ∥ > t] . Then (6) gives

P [(E_{μ}∥η(π, ω)∥^{2})^{1/2} > s ; ∥ξ(ω)∥ > t] ≤ \frac{8}{c_{0}} P [∥ξ∥ > t] .

P [(E_{μ}∥η(π, ω)∥^{2})^{1/2} ≤ s ; ∥ξ(ω)∥ > t] ≥ P [∥ξ(ω)∥ > t]

− \frac{8}{c_{0}} P [∥ξ(ω)∥ > t] = (1 − \frac{8}{c_{0}} )P [∥ξ(ω)∥ > t] .  (7)

Let us now introduce the event

A = {ω : E_{μ}∥η(π, ω)∥^{2} ≤ s ; ∥ξ(ω)∥ > t} .

According to (7),

P (A) ≥ (1 − \frac{8}{c_{0}} )P [∥ξ(ω)∥ > t] ,

and according to (4) we have, for any ω ∈ A,

μ\{π : ∥η(π, ω)∥ > \frac{λt}{2}\} ≥ \frac{(1 − λ)^{2}t^{2}}{2s^{2}} = \frac{(1 − λ)^{2}t^{2}}{2c_{0}^{2}} P [∥ξ∥ > t] .

Integrating both sides with respect to ω we get

P × μ \{(π, ω) : ∥η(π, ω)∥ > \frac{λt}{2}\} ≥ \frac{(1 − λ)^{2}t^{2}}{2c_{0}^{2}} P^{2}[∥ξ∥ > t]

(using another Kahane inequality P [∥ ∑ a_{k}r_{k}∥ > 2t] ≤ 4P^{2}[∥ ∑ a_{k}r_{k}∥ > t] from [2, Ch. 2])

≥ C_{1}(1 − λ)^{2}t^{2}P [∥ξ∥ > 2t] ,

where C_{1} = \frac{1}{8}(1 − \frac{8}{c_{0}} )\frac{1}{c_{0}^{2}} ≤ \frac{1}{3756}.

The last inequality gives us that for each t > 0 , 0 < λ < 1,

P [∥ξ∥ > t] ≤ \frac{C_{2}}{(1 − λ)^{2}t^{2}} P × μ [∥η∥ > \frac{λt}{4}]
= \frac{C_{2}}{(1 − λ)^{2}t^{2}} m [∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{λt}{8}] ,  (8)

where C_{2} is an absolute constant (e.g., C_{2} = 3756 × 4 = 15024 fits). The inequality is fine for large t’ s. We have to get rid of t^{−2} for small t’ s. Fix any 0 < t_{0} < 1 . Then (8) implies that for any t > t_{0}

P × μ [∥η∥ > \frac{λt}{2}] ≥ \frac{(1 − λ)^{2}t_{0}^{2}}{C_{2}} P [∥ξ∥ > t].  (9)

Now let t ≤ t_{0} and use the Kahane inequality to show that

P × μ [∥η∥ > tE∥η(π, ω)∥] ≥ (1 − t)^{2} \frac{(E∥η(π, ω)∥)^{2}}{E∥η(π, ω)∥^{2}}
≥ (1 − t)^{2}(\frac{n}{2n − 1})^{2} \frac{(E∥ξ∥)^{2}}{4E∥ξ∥^{2}}  (10)

(the Khinchine–Kahane inequality \frac{E∥ξ∥}{(E∥ξ∥^{2})^{1/2}} ≥ 2^{−1/2} , see [3] )

≥ \frac{1}{32}(1 − t_{0})^{2}P [∥ξ∥ > t] .

Further, for left-hand side in (10) we have

P × μ [∥η∥ > tE∥η(π, ω)∥] ≤ P × μ [∥η∥ > t\frac{n}{2n − 1}E∥ξ∥]

≤ P × μ[∥η∥ > \frac{t}{2} \frac{E∥ξ∥}{(E∥ξ∥^{2})^{1/2}} ] ≤ P × μ [∥η∥ > \frac{t}{2\sqrt{2}}].

So, for any t ≤ t_{0} < 1

P [∥ξ∥ > t] ≤ \frac{32}{(1 − t_{0})^{2}} P × μ [∥η∥ > \frac{t}{2\sqrt{2}}].  (11)

Now (9) and (11) imply the existence of an absolute constant C such that the inequality

P [∥ξ∥ > t] ≤ CP × μ[∥η∥ > \frac{2t}{C} ] = Cm [∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{C} ]

holds true for any t > 0 .

So, inequality (1) is proved under the condition that E∥ξ∥^{2} = 1. For a general collection (a_{1}, …, a_{2n})⊂X we apply (1) to (a_{1}/(E∥ξ∥^{2})^{1/2}, …, a_{2n}/(E∥ξ∥^{2})^{1/2}) and use the fact that (1) is true for any t > 0 . The part (a) of the Theorem is proved.

Proof of part (b). Let (a_{1}, …, a_{2n}) ⊂ X be an arbitrary collection. In order to reduce the issue to a), consider the collection (b_{1}, …, b_{2n}) , where b_{k} =

a_{k} − ā , ā = \frac{1}{2n}(a_{1} + ⋯ + a_{2n}). Since ∑_{1}^{2n} b_{k} = 0 , we can write according to (a):

P [∥ ∑_{1}^{2n} a_{k}r_{k}∥ − ∥ ∑_{1}^{2n} a_{k}∥ > t]

≤ Cm [∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ + \frac{1}{2}∥a_{1} + ⋯ + a_{2n}∥ > \frac{t}{C} ]

≤ Cm [∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ + \frac{1}{2}∥a_{k_{1}} + ⋯ + a_{k_{n}}∥

+ \frac{1}{2}∥a_{k′_{1}} + ⋯ + a_{k′_{n}}∥ > \frac{t}{C} ]

≤ C(m [3 ∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{C} ] + m[∥a_{k′_{1}} + ⋯ + a_{k′_{n}}∥ > \frac{t}{C} ])

≤ 2C m [∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{3C} ] .

So that as a new absolute constant in (b) one can choose 3C.

2. Corollaries

Estimates for moments of the norm of Rademacher sums.

Corollary 1. Let (a_{1}, …, a_{2n}) be any collection of a normed space X, Φ : R^{+} → R^{+} be any continuous increasing function, Φ(0) = 0. Then

(a)

EΦ(∥ ∑_{1}^{2n} a_{k}r_{k}∥) ≤ C \frac{(n!)^{2}}{(2n)!} ∑_{k_{1}<···<k_{n}} Φ(C∥a_{k_{1}} + ⋯ + a_{k_{n}}∥) ,

where C is an absolute constant.

(b) If ∑_{1}^{2n} a_{k} = 0, then

c \frac{(n!)^{2}}{(2n)!} ∑_{k_{1}<···<k_{n}} Φ(c∥a_{k_{1}} + ⋯ + ak_{n}∥) ≤ EΦ(∥ ∑_{1}^{2n} a_{k}r_{k}∥) ,

where c is another absolute constant.

Proof. (a). According to the part (b) of the Theorem and the integration by parts formula,

E Φ(∥ ∑_{1}^{2n} a_{k}r_{k}∥) = ∫_{0}^{∞}P [∥ ∑_{1}^{2n} a_{k}r_{k}∥ > t] μΦ(t)

≤ ∫_{0}^{∞}Cm[∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{C} ] dΦ(t)

= CEΦ(C∥a_{k_{1}} + ⋯ + a_{k_{n}}∥) = C \frac{(n!)^{2}}{(2n)!} ∑_{k_{1}<···<k_{n}} Φ(C∥a_{k_{1}} + ⋯ + a_{k_{n}}∥) .

The part (b) can be derived from Theorem (a) in a similar way.

A maximal inequality for exchangeable systems of random variables. Let X be a separable Banach space. A system (ξ_{1}, …, ξ_{n}) of X-valued random variables is called exchangeable if for any permutation π : {1, …, n} → {1, …, n} the distribution of (ξ_{π(1)}, …, ξ_{π(n)}) is the same as that of (ξ_{1}, …, ξ_{n}). Concerning the issues of probability in a Banach space the reader is referred to [5].

In [1] we have proved the following maximal inequality for exchangeable systems of random variables with ∑_{1}^{n} ξ_{k} = 0 :

cP [∥ ∑ ξ_{k}r_{k}∥ > \frac{t}{c}] ≤ P [ max_{k≤n} ∥ξ_{1}+⋯+ξ_{k}∥ > t] ≤ CP [∥ ∑ ξ_{k}r_{k}∥ > \frac{t}{C} ], (12)

where (r_{n}) is a system of Rademacher r.v.’s independent of ξ’s, t > 0 is arbitrary, c and C are absolute constants.

As before μ stands for the uniform distribution on the set Π of all permutations π : {1, …, 2n} → {1, …, 2n}.

Given a collection (a_{1}, …, a_{2n}) ⊂ X, we can introduce the following system of exchangeable random variables ξ_{k} : Π → X : ξ_{k}(π) = a_{π(k)} , k = 1, …, 2n.

If ∑_{1}^{2n} a_{k} = 0, then the right-hand side of (1) for this system takes the form

μ [ max_{k≤2n} ∥a_{π(1)} + ⋯ + a_{π(k)}∥ > t] ≤ CP [∥ ∑_{1}^{2n} a_{k}r_{k}∥ > \frac{t}{C} ]

(and using Theorem)

≤ C_{1} m[∥a_{k_{1}} + ⋯ + a_{k_{n}}∥ > \frac{t}{C_{1}} ] = C_{1}μ[∥a_{π(1)} + ⋯ + a_{π(n)}∥ > \frac{t}{C_{1}} ] . (13)

Corollary 2 (Pruss, [4]).

(a) Let (a_{1}, …, a_{2n}) be any collection of vectors of a normed space X (not

necessarily with ∑_{1}^{2n} a_{k} = 0). Then for any t > 0

μ[ max_{k≤2n} ∥a_{π(1)} + ⋯ + a_{π(k)}∥ > t] ≤ C μ[∥a_{π(1)} + ⋯ + a_{π(n)}∥ > \frac{t}{C} ] (14)

for some absolute constant C.

(b) For any exchangeable system (ξ_{1}, …, ξ_{2n}) of X-valued random variables and any t > 0,

P [ max_{k≤2n} ∥ξ_{1} + ⋯ + ξ_{k}∥ > t] ≤ CP [∥ξ_{1} + ⋯ + ξ_{n}∥ > \frac{t}{C} ] ,

where C is an absolute constant.

Proof. According to (13), (a) holds true when ∑_{1}^{2n} a_{k} = 0. Now let (a_{1}, …, a_{2n})

be an arbitrary collection. Then for the new collection (b_{1}, …, b_{2n}), b_{k} = a_{k} −ā, k = 1, …, 2n, (14) is applicable, i.e.,

μ [ max_{k≤2n} ∥(a_{π(1)} − ā) + ⋯ + (a_{π(k)} − ā)∥ > t]

≤ C μ[∥a_{π(1)} + ⋯ + a_{π(n)} − (a_{1} + ⋯ + a_{2n})\frac{1}{2}∥ > \frac{t}{C} ]

≤ C μ[∥\frac{1}{2}(a_{π(1)} + ⋯ + a_{π(n)})∥ + ∥a_{π(n+1)} + ⋯ + a_{π(2n)}∥ > \frac{t}{C} ]

≤ C(μ[∥a_{π(1)} + ⋯ + a_{π(n)}∥ > \frac{t}{C} ] + μ[∥a_{π(n+1)} + ⋯ + a_{π(2n)}∥ > \frac{t}{2C} )

≤ 2Cμ[∥a_{π(1)} + ⋯ + a_{π(n)}∥ > \frac{t}{2C} ] .  (15)

Let us transform the left-hand side of (15)

μ[ max_{k≤2n} ∥(a_{π(1)} − ā) + ⋯ + (a_{π(k)} − ā)∥ > t]

≥ μ[| max_{k≤2n} ∥a_{π(1)} + … a_{π(k)}∥ − ∥a_{1} + ⋯ + a_{2n}∥| > t]

≥ μ[ max_{k≤2n} ∥a_{π(1)} + ⋯ + a_{π(k)}∥ > t] − μ[∥a_{1} + ⋯ + a_{2n}∥ > \frac{t}{2}]

≥ μ[ max_{k≤2n} ∥a_{π(1)} + ⋯ + a_{π(k)}∥ > t]

− μ[∥a_{π(1)} + ⋯ + a_{π(n)}∥ > \frac{t}{4}] − μ[∥a_{π(n+1)} + ⋯ + a_{π(2n)}∥ > \frac{t}{4}] .

This along with (15) proves (a).

(b) We have

P [ max_{k≤2n} ∥ξ_{1} + ⋯ + ξ_{k}∥ > t]

(due to the exchangeability)

= P × μ[ max_{k≤2n} ∥ξ_{π(1)} + ⋯ + ξ_{π(k)}∥ > t]

(due to the part (a))

≤ CP × μ[∥ξ_{π(1)} + ⋯ + ξ_{π(n)}∥ > \frac{t}{C} ]

(due to the Fubini theorem and exchangeability)

= CP [∥ξ_{1} + ⋯ + ξ_{n}∥ > \frac{t}{C} ] .

References

1. S. Chobanyan, H. Salehi, Exact maximal inequalities for exchangeable systems of random variables. Teoriya Veroyat. i Primenen. 45(2000), No. 3, 555–567.

2. J.-P. Kahane, Some random series of functions. D.C. Heat and Company, Lexington, Massachusetts, 1968.

3. R. Latała and K. Oleszkiewicz, On the best constant in the Khinchine–Kahane inequality. Studia Math. 109(1994), 101–104.

4. A. R. Pruss, A maximal inequality for partial sums of finite exchangeable sequence of random variables. Proc. Amer. Math. Soc. 126(1998), No. 6, 1811–1819.

5. N. N. Vakhania, V. I. Tarieladze, and S. A. Chobanyan, Probability distributions on Banach spaces. D. Reidel Publishing Co., Dordrecht, 1987.

(Received 15.02.2001)

Authors’ addresses:

S. Chobanyan Muskhelishvili Institute of Computational Mathematics Georgian Academy of Science 8, Akuri St., Tbilisi 380093 Georgia Department of Statistics and Probability Michigan State University A 419 Wells Hall, East Lansing, MI 48824, U.S.A. E-mail: chobanyan@stt.msu.edu

H. Salehi Department of Statistics and Probability Michigan State University A 415 Wells Hall, East Lansing, MI 48824, U.S.A. E-mail: salehi@stt.msu.edu