mean zero Cram`er random variables

Vol. LXIX, 2(2000), pp. 137–144

ON LARGE RANDOM ALMOST EUCLIDEAN BASES

R. VERSHYNIN

Abstract. A new class of random proportional embeddings oflⁿ₂ into certain Ba- nach spaces is found. Let (ξi)ⁿ_i=1be i.i.d. mean zero Cram`er random variables. Sup- pose (xi)ⁿ_i=1is a sequence in the unit ball of a Banach space withEkP

iεixik ≥δn.

Then the system ofdcneindependent random vectors distributed asP

iξixiis well equivalent to the euclidean basis with high probability (c depends onξ1 and δ).

A connection with combinatorial discrepancy theory is presented.

1. Sign Embeddings And Short Films

G. Schechtman proved that inlⁿ₁ a certain random choise ofcn vectors is well equivalent to the euclidean basis ([Sch1], see also [M-S, 7.15]). More precisely, by ε_iwe denote the Rademacher random variables, i.e. independent random variables taking values −1 and 1 with probability 1/2, by ei the canonical vectors inRⁿ, and byc₁, c₂, . . . absolute constants. A system (z_i)^k_i=1of vectors in a Banach space is said to be c-equivalent to the euclidean basis if there is a linear operator T: span (zi)→l^k₂ sending eachzi toei, withkTkkT⁻¹k ≤c. Then Schechtman’s theorem says the following. Every system ofdc1neindependent random vectors in l₁ⁿdistributed asPn

j=1εjejisc2-equivalent to the euclidean basis with probability

≥1−exp(−c3n).

This result is generalized here in two directions. Instead of the canonical vector basis of lⁿ₁, we work with arbitrary sequence (x_j)ⁿ_j=1 of vectors in the unit ball B(X) of a Banach spaceX satisfying

(1) E

n

X

j=1

εjxj

≥δn

for someδ >0. This estimate is known as therandomδ-sign embedding from l₁ⁿ condition [F-J-S]. In [Sch1] it was considered in spaces with a good cotype;

our proof does not require cotype restrictions.

Moreover, instead of the Bernoullian distribution of each coordinate, we con- sider arbitrary distribution of a mean zero r.v.ξhaving moment generating func- tion, that isEe^α|ξ|<∞ for someα >0. This is called theCram`er condition,

Received December 2, 1998; revised December 20, 2000.

1980Mathematics Subject Classification(1991Revision). Primary 46B09, 05B20, 41A28.

and is equivalent to the following: there are constantsa,α >0 so that (2) P{|ξ|> t} ≤ae^−αt for allt

(see [P, Lemma III.5]).

Theorem 1.1. Let (ξj)ⁿ_j=1 be independent copies of a mean zero r.v.ξ satis- fying(2);setα1=E|ξ|. Suppose(xj)ⁿ_j=1 is a sequence inB(X)satisfying(1),and sets=√

a/α1αδ. There is a c=c(s)>0 so that the system ofdcneindependent random vectors distributed as Pn

j=1ξ_jx_j is(c₁s)-equivalent to the euclidean basis with probability≥1−2 exp(−c2s⁻²n).

Remarks. 1. One can set c(s) =c₂/s²log(c₁s). We see that Theorem 1.1 is controlled by the only parameters.

2. Actually, we prove that the operator T realizing the equivalence satisfies kTk ≤c3(α1δn)⁻¹, andkT⁻¹k ≤c4

√aα⁻¹n.

J. Elton [E] proved that (1) yields the existence of a subset A ⊂ {1, . . . , n},

|A| ≥ c(δ)n, such that the sequence (xj)_j∈A is c⁰(δ)-equivalent to the canonical vector basis of l₁^|A|. If combined with Schechtman’s theorem, this gives another form of proportional euclidean sections of X (however, with a worse dependence onδ: c(δ)∼δ²/log²(4/δ),c⁰(δ)∼δ⁻³).

For convenience, we restricted ourselves to identically distributed random vari- ablesξ, but the main result can easily be modified to handle the case whenξhave different distributions.

Theorem 1.1 admits an immediate application to random matrices. The next corolary says that the unit cube inRⁿ under the action of a randomk×nmatrix (withk proportional ton) is close to the euclidean ball B₂^k. We denote the unit euclidean ball inR^k byB₂^k.

Corollary 1.2. Supposeξ is a random variable satisfying(1),then there exist c, µ, ν >0such that we have the following. LetAbe thek×nmatrix whose entries are independent random variables distributed asξ. Ifk≤cnthen with probability

≥1−2 exp(−cn)

µB₂^k ⊂n⁻¹A([−1,1]ⁿ)⊂νB₂^k.

Proof. Pass to the dual setting and apply Theorem 1.1 together with Re-

mark 2.

Now we discuss a relation between almost euclidean bases inlⁿ₁ and combina- torial discrepancies. Given a two-coloring χ, say White and Black, of a finite set Ω, thediscrepancydisc (A, χ) of a setA⊂Ω is the number of White points inA minus the number of Black points inA(cf. [A-S], [B-S]). A familyχ= (χj)ⁿ_j=1of two-colorings on Ω is called a filmof lengthn. We define thefilm discrepancy fdisc (A, χ) of a setA⊂Ω as the average _n¹Pn

j=1|disc (A, χj)|.

The problem is to make a shorthomogeneousfilm, so that the film discrep- ancies of any two setsA, B ⊂Ω of equal size be nearly the same: fdisc (A, χ)≈ fdisc (B, χ) (the relationx≈y meansc1x≤y≤c2xfor some absolute constants c₁, c₂>0). Since nobody wants to watch a monochromatic film, we require it to be balanced, that is the density of each shot be nontrivial:|disc (Ω, χj)| ≤(1−c3)|Ω|

for allj and some absolute constantc₃>0.

One might think that balanced homogeneous films must be fairly long compar- ing with|Ω|, but this is unjustified.

Theorem 1.3. Given a finite set Ω, there is a balanced homogeneous film on Ωof length c₁|Ω|.

Proof. We begin with a geometrical interpretation of the problem, as in [Sp].

Letk=|Ω|. A coloringχon Ω is regarded as a sequence (εi)∈ {−1,1}^k, assigning 1 to White and−1 to Black. A setA⊂Ω is identified with its incidence vector (ai)∈ {0,1}^k. Then disc (A, χ) =Pk

i=1εiai.

Now we clarify a relation to Schechtman’s result, that is Theorem 1.1 with ξ_j=ε_j and (x_j) = the canonical vectors inX =lⁿ₁. Letnbe the minimal integer such thatdcne ≥k. In this case we get with probability≥1−2 exp(−c2n)

(3) 1

n

n

X

j=1

k

X

i=1

aiεij

≈X^k

i=1

|ai|^21/2

for all scalars (ai),

whereε_ijare Rademacher random variables (see Remark 2 following Theorem 1.1).

Letχ be a random film of length n, so thatχj = (εij)^k_i=1. Then (3) yields that, with probability≥1−2 exp(−c2n), every set A⊂Ω satisfies fdisc (A, χ)≈p

|A|.

Hence most films are homogeneous.

It suffices to show that most films are also balanced. Consider a random coloring χ= (εi) on Ω. Using a subgaussian tail estimate for Rademacher sums (see [L] or apply Theorem ), we have

Pn

|disc (Ω, χ)| ≤ 1 2|Ω|o

=Pn

k

X

i=1

ε_i

≤k/2o

≥1−2 exp(−k/8).

Then the probability that |disc (Ω, χj)| ≤ ¹₂|Ω| for all j = 1, . . . , n is at least 1−2nexp(−k/8). Since n ≤c₁k, this probability tends to 1 as k → ∞. This

completes the proof.

I do not know whether there are asymptotically shorter balanced homogeneous films.

To prove the main result, we will apply a deviation inequality for sums of independent Banach space valued random variables.

Theorem 1.4. Let X1, . . . , Xn be independent Banach space valued random variables with P{kXik > t} ≤ ae^−αit for all t and i. Let d ≥ maxi≤nα⁻¹_i and b≥aPn

i=1α⁻²_i . Then settingSn =Pn

i=1Xi we have

P

kSnk −EkSnk > t ≤

2 exp(−t²/32b) for0≤t≤4b/d 2 exp(−t/8d) fort≥4b/d.

This result can be derived by truncation from known deviation inequalities for sums of bounded random variables (see e.g. [Le-Ta, Section 6.2]). However, it is more convenient and more instructive to give a direct proof based on martingales, as in [Yu, Sec. 3.3]. A rather short instructive proof is given in§2.

§3 consists of the proof of Theorem 1.1.

This work was supported by C.N.R. (Italy). I am grateful to P. Terenzi and to V. Kadets for discussions.

2. Deviations of Sums In this section we prove Theorem 1.4.

First we recall that problems about Banach space valued independent random variables can often be reduced to a real valued martingale case, see [Le-Ta, Ch. 6.3].

LetAi be theσ-algebra generated by the random variables X1, . . . , Xi,i≤n, andA0be the trivialσ-algebra. The conditional expectation with respect toAiis denoted byE^Ai. Set, for eachi,di=E^AikSnk −E^Ai−1kSnk. Then (di)ⁿ_i=1 forms a real valued martingale difference sequence, andPn

i=1di =kSnk −EkSnk.

Lemma 2.1. For every iand every p≥1 E^Ai−1|di|^p≤2^pEkXik^p almost surely.

Proof. Yurinskii’s inequality states that|d_i| ≤ kX_ik+EkX_ikalmost surely (see [Le-Ta, Lemma 6.16]). Then|di|^p≤2^p−1 kXik^p+ (EkXik)^p

. Hence E^Ai−1|di|^p≤2^p−1 E^Ai−1kXik^p+ (EkXik)^p

= 2^p−1 EkXik^p+ (EkXik)^p

≤2^pEkXik^p,

and we are done.

Proof of Theorem 1.4. Apply Chebyshev’s inequality. For everyλ≥0

(4) P :=Pn

kSnk −EkSnk> to

=PnXⁿ

i=1

di> to

≤e^−λtEexp λ

n

X

i=1

di

.

But

Eexp(λ

n

X

i=1

di) =E

E^An−1exp(λ

n

X

i=1

di)

=E exp(λ

n−1

X

i=1

di)E^An−1exp(λdn)

≤ kE^An−1exp(λdn)k∞Eexp(λ

n−1

X

i=1

di) =· · · (5)

=

n

Y

i=1

kE^Ai−1exp(λdi)k_∞.

So we are to evaluate

E^Ai−1exp(λdi) = 1 +

∞

X

p=2

λ^pE^Ai−1d^p_i

p! (sinceE^Ai−1di= 0)

≤1 +

∞

X

p=2

λ^p2^pEkXik^p

p! (by Lemma 2.1).

Note that

(6) EkX_ik^p= Z ∞

0

P{kX_ik> t}dt^p≤ Z ∞

0

ae^−αitdt^p=aα_i^−pp!

Then for 0≤λ≤αi/4

E^Ai−1exp(λdi)≤1 +a(2λ/αi)²

∞

X

p=2

(2λ/αi)^p−2≤1 +a(2λ/αi)²2≤exp(8λ²aα_i⁻²).

Combining this estimate, (5), and (4), we obtain for 0≤λ≤1/4d

P ≤e^−λt

n

Y

i=1

exp(8λ²aα⁻²_i )≤exp(−λt+ 8λ²b).

The minimum here is attained for λ = t/16b. If t ≤ 4b/d, then the condition λ≤1/4dis satisfied, andP ≤exp(−t²/32b). Ift≥4b/d, then we takeλ:= 1/4d, and getP ≤exp(−t/8d).

Similarly, one obtains the same estimates onP{kSnk −EkSnk<−t}.

3. Random Euclidean Embeddings In this section Theorem 1.1 is proved.

We will use a simple symmetrization lemma, see [Le-Ta, Lemma 6.3].

Lemma 3.1. For every finite sequence (Xi) of Banach space valued mean zero random variables

1 2E

X

i

εiXi

≤E

X

i

Xi

≤2E

X

i

εiXi

.

Next, we need a known generalization of the Khinchine inequality.

Proposition 3.2. Let(ξ_i)be a sequence of real valued i.i.d. mean zero random variables. Then for every finite sequence of numbers (ai)

1

2Apkξ1k_min(2,p)X

i

|ai|²1/2

≤

X

i

aiξi

_p≤2Bpkξ1k_max(2,p)X

i

|ai|²1/2

,

whereAp andBp are the constants from the classical Khinchine inequality.

Actually, we will use the following particular case of the inequality, and give a proof only for this case:

(7) 1

2√ 2kξ1k1

X

i

|ai|^21/2

≤

X

i

aiξi

₁≤ kξ1k2

X

i

|ai|^21/2 .

Proof (sketch). To prove the left-hand side observe that, by Lemma 3.1, E|P

iaiξi| is nearly the same as E|P

iεiaiξi|. Now it is enough to apply par- tial integration and use the classical Khinchine inequality (note thatA₁ = 1/√

2 [Sz]). Since kP

iaiξik1≤ kP

iaiξik2, the right-hand side of (7) follows from the orthogonality of (ξi) inL2(Ω), due to the independentness.

Another simple consequence of the symmetrization is this.

Lemma 3.3. Let (η_i) be a finite sequence of real valued i.i.d. mean zero random variables. Then, for any sequence(xi)in a Banach space,

E

X

i

ηixi

≥1

2kη1k1E

X

i

εixi

.

Proof. By the symmetry,εi|ηi|has the same distribution as εiηi. Using partial integration and the triangle inequality, we have

E

X

i

εiηixi

=E

X

i

εi|ηi|xi

≥E

X

i

εikηik1xi

.

Now it is enough to apply Lemma 3.1 withX_i=η_ix_i. Finally, recall a standard approximation lemma (see [M-S, 4.1]).

Lemma 3.4. Let X be a Banach space, and F:X → R be a non-negative convex homogeneous function. Suppose for some θ-net N of S(X) one has a ≤ F(x)≤b for everyx∈ N. Then

a− θ

1−θb≤F(x)≤ 1 1−θb for everyx∈S(X).

In particular, ifθ≤a/3b, then ¹₂a≤F(x)≤ ³₂b for every x∈S(X).

Proof of Theorem 1.1. Let (ξij) be independent copies of ξ. Let k ≤cn. We are to show that the random vectors yi =n⁻¹Pn

j=1ξijxj, i = 1, . . . , k, are well equivalent to the euclidean basis.

Fixa= (ai)^k_i=1 in the unit sphere S(l^k₂). Consider a sequence of independent random variables

Xij =n⁻¹aiξijxj, i= 1, . . . , k, j= 1, . . . , n, and their sum S(a) = Pk

i=1

Pn

j=1Xij. We will prove that, with high probability, kS(a)k is bounded from above and below for everya.

Theorem 1.4 applied to the sum ofXij helps here. Note thatP{kXijk> t}= P{n⁻¹|ai||ξ|> t} ≤aexp(−αn|ai|⁻¹t), thus we take

d=α⁻¹n⁻¹ and b=a

k

X

i=1 n

X

j=1

α⁻²n⁻²|ai|²=aα⁻²n⁻¹.

Furthermore,

EkS(a)k=n⁻¹E

n

X

j=1

X^k

i=1

a_iξ_ij x_j

≥n⁻¹1 2

k

X

i=1

aiξij

₁E

n

X

j=1

εjxj

(by Lemma 3.3)

≥ 1 4√

2α₁δ (by (7) and the condition on (x_j)).

Conversely, let α₂ = kξk2. Note that α₂ ≤ √ 2√

aα⁻¹, as in (6). Then by the triangle inequality and (7)

EkS(a)k ≤n⁻¹

n

X

j=1

E

k

X

i=1

aiξij

≤α2≤√ 2√

aα⁻¹.

Now set t := ¹

8√

2α1δ ≤ ¹₂EkS(a)k and apply Theorem 1.4. Clearly, t ≤ 4b/dis the case, becauseδ≤1 andα1≤aα⁻¹as in (6). Thus

P{d1≤ kS(a)k ≤d2} ≥1−2 exp(−d3n), whered₁= ¹

8√

2δα₁, d₂= ³₂√ 2√

aα⁻¹, and d₃=c₄(αα₁δ/√

a)²=c₄t⁻².

The preceding observations hold for fixeda. Now letarun over a θ-netN in S(l₂^k),|N | ≤exp(klog 3/θ), whereθ=d1/3d2(there is such a net, cf. [M-S, 2.6]).

Then

P{∀a∈ N, d1≤ kS(a)k ≤d2} ≥1−2 exp(klog 3/θ−d3n).

We conclude by Lemma 3.4,

P{∀a∈S(l₂^k), d₁/2≤ kS(a)k ≤3d₂/2} ≥1−2 exp(klog 3/θ−d₃n).

Ifcwas chosen small enough, then klog 3/θ≤¹₂d3n.

It remains to note thatd2/d1=c5s, and the required (c1s)-equivalence to the

euclidean basis follows.

References

[A-S] Alon N. and Spencer J.,The probabilistic method, Wiley-Interscience, 1992.

[B-S] Beck J. and Sos V. T.,Discrepancy theory, Handbook of combinatorics, North-Holland, 1995, pp. 1405–1446.

[Ch] Chernoff H.,A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statist.23(1952), 493–509.

[E] Elton J.,Sign-embeddings oflⁿ₁, Trans. AMS279(1983), 113–124.

[F-J-S] Figiel T., Johnson W. B. and Schechtman G., Random sign embeddings from lⁿ_r,2< r,∞, Proc. AMS102(1988), 102–106.

[Le-Ta] Ledoux M. and Talagrand M.,Probability in Banach spaces, Springer, 1991.

[L] Lo`eve M.,Probability theory I, 4th ed., Springer, 1977.

[M-S] Milman V. and Schechtman G.,Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Math.1200(1986), Springer.

[P] Petrov V. V.,Sums of independent random variables, Springer, 1975.

[Sch1] Schechtman G.,Random embeddings of euclidean spaces in sequence spaces, Israel J.

Math.40(1981), 187–192.

[Sp] Spencer J.,Six standard deviations suffice, Trans. AMS289(1985), 679–706.

[Sz] Szarek S.,On the best constant in the Khinchine inequality, Studia Math.58(1976), 197–208.

[Yu] Yurinski V.,Sums and Gaussian vectors, Lecture Notes in Math. 1617 (1995), Springer.

R. Vershynin, Faculty of Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot 76100, Israel