Lévy’s inequality, Rademacher sums, and Kahane’s inequality

1 Lévy’s inequality

Let $(\mathrm{\Omega },𝒜,P)$ be a probability space. A random variable is a Borel measurable function $\mathrm{\Omega }\to ℝ$. For a random variable $X$, we denote by $X_{*}P$ the pushforward measure of $P$ by $X$. $X_{*}P$ is a Borel probability measure on $ℝ$, called the distribution of $X$. A random variable $X$ is called symmetric when the distribution of $X$ is equal to the distribution of $-X$. Because the collection $\{(-\mathrm{\infty },a]:a\in ℝ\}$ generates the Borel $\sigma$-algebra of $ℝ$, the statement that $X_{*}P={(-X)}_{*}P$ is equivalent to the statement that for all $a\in ℝ$,

$$P(\{\omega \in \mathrm{\Omega }:X(\omega )\le a\})=P(\omega \in \mathrm{\Omega }:-X(\omega )\le a\}).$$

The following is Lévy’s inequality.

Theorem 1 (Lévy’s inequality).

Suppose that ${\chi }_k$, $k\mathrm{\ge }\mathrm{1}$, are independent symmetric random variables, that $U$ is a real or complex Banach space, and that $u_k\mathrm{\in }U$, $k\mathrm{\ge }\mathrm{1}$. Then for each $a\mathrm{>}\mathrm{0}$ and for each $n\mathrm{\ge }\mathrm{1}$,

$$P(\underset{1\le k\le n}{\max }\parallel \sum _{1\le j\le k}{\chi }_j{u}_j\parallel \ge a)\le 2\cdot P(\parallel \sum _{1\le j\le n}{\chi }_j{u}_j\parallel \ge a).$$

Proof.

Let $S_0=0$ and for $1\le k\le n$,

$$S_k(\omega )=\sum _{j=1}^k{\chi }_j(\omega )u_j,\omega \in \mathrm{\Omega }.$$

For $1\le k\le n$, the function $\omega \mapsto ({\chi }_1(\omega ),\mathrm{\dots },{\chi }_k(\omega ))$ is Borel measurable $\mathrm{\Omega }\to {ℝ}^k$. The function $(t_1,\mathrm{\dots },t_k)\mapsto {\sum }_{j=1}^k{t}_j{u}_j$ is continuous ${ℝ}^k\to U$. And the function $u\mapsto \parallel u\parallel$ is continuous $U\to ℝ$. Therefore $\omega \mapsto \parallel S_k(\omega )\parallel$, the composition of these functions, is Borel measurable $\mathrm{\Omega }\to ℝ$. This then implies that $\omega \mapsto {\max }_{1\le k\le n}\parallel S_k(\omega )\parallel$ is Borel measurable $\mathrm{\Omega }\to ℝ$. Let

$$A=\{\omega \in \mathrm{\Omega }:\underset{1\le k\le n}{\max }\parallel S_k(\omega )\parallel \ge a\},B=\{\omega \in \mathrm{\Omega }:\parallel S_n(\omega )\parallel \ge a\},$$

for which $B\subset A$. For $1\le k\le n$, let

It is apparent that that $A_1,\mathrm{\dots },A_n$ are pairwise disjoint and that $A={\bigcup }_{k=1}^n{A}_k$.

For $1\le k\le n$, let

$$T_{n,k}(\omega )=S_k(\omega )-\sum _{j=k+1}^n{\chi }_j(\omega )u_j=\sum _{j=1}^k{\chi }_j(\omega )u_j-\sum _{j=k+1}^n{\chi }_j(\omega )u_j,\omega \in \mathrm{\Omega },$$

in other words, $S_n+T_{n,k}=2S_k$. Let

$$U_k=A_k\cap B,V_k=A_k\cap \{\omega \in \mathrm{\Omega }:\parallel T_{n,k}(\omega )\parallel \ge a\}.$$

If $\omega \in A_k$, then

$$\parallel S_n(\omega )+T_{n,k}(\omega )\parallel =2\parallel S_k(\omega )\parallel \ge 2a,$$

which implies that at least one of the inequalities $\parallel S_n(\omega )\parallel \ge a$ or $\parallel T_{n,k}(\omega )\parallel \ge a$ is true. Therefore

$$A_k=U_k\cup V_k.$$

Because ${\chi }_1,\mathrm{\dots },{\chi }_n$ are independent, the random vector $X=({\chi }_1,\mathrm{\dots },{\chi }_n):\mathrm{\Omega }\to {ℝ}^n$ has the pushforward measure

$$X_{*}P=\chi _1{}_{*}P\times \mathrm{\cdots }\times \chi _n{}_{*}P,$$

and for each $1\le k\le n$, the random vector $X_k=({\chi }_1,\mathrm{\dots },{\chi }_k,-{\chi }_{k+1},\mathrm{\dots },-{\chi }_n):\mathrm{\Omega }\to {ℝ}^n$ has the pushforward measure

$$X_k{}_{*}P=\chi _1{}_{*}P\times \mathrm{\cdots }\chi _k{}_{*}P\times {(-{\chi }_{k+1})}_{*}P\times \mathrm{\cdots }{(-{\chi }_n)}_{*}P,$$

and because each ${\chi }_j$ is symmetric, these pushforward measures are equal. Define ${\sigma }_k:{ℝ}^k\to ℝ$ by

$${\sigma }_k(t_1,\mathrm{\dots },t_k)=\parallel \sum _{j=1}^k{t}_j{u}_j\parallel ,(t_1,\mathrm{\dots },t_k)\in {ℝ}^k,$$

define ${\sigma }_0=0$, and set

$H_k$

$\cap \{(t_1,\mathrm{\dots },t_n)\in {ℝ}^n:{\sigma }_k(t_1,\mathrm{\dots },t_k)\ge a,{\sigma }_n(t_1,\mathrm{\dots },t_n)\ge a\}.$

Because each ${\sigma }_j$ is continuous, $H_k$ is a Borel set in ${ℝ}^n$. Then we have

$P(U_k)$ $=P(A_k\cap B)$

$=P(X^{-1}(H_k))$

$=(X_{*}P)(H_k)$

$=(X_k{}_{*}P)(H_k)$

$=P(X_k^{-1}(H_k))$

$=P(A_k\cap \{\omega \in \mathrm{\Omega }:\parallel T_{n,k}(\omega )\parallel \ge a\})$

$=P(V_k);$

among the above equalities, the two equalities that deserve chewing on are

$$P(A_k\cap B)=P(X^{-1}(H_k))\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}P(X_k^{-1}(H_k))=P(A_k\cap \{\omega \in \mathrm{\Omega }:\parallel T_{n,k}(\omega )\parallel \ge a\}).$$

Thus we have

$$P(A_k)=P(U_k\cup V_k)\le P(U_k)+P(V_k)=2P(U_k)=2P(A_k\cap B).$$

Therefore

$P(A)$ $={\displaystyle \sum _{k=1}^n}P(A_k)$

$\le {\displaystyle \sum _{k=1}^n}2P(A_k\cap B)$

$=2P(A\cap B)$

$=2P(B),$

proving the claim. ∎

2 Rademacher sums

Suppose that ${ϵ}_n:(\mathrm{\Omega },𝒜,P)\to (ℝ,{ℬ}_{ℝ},\lambda )$, $n\ge 1$, are independent random variables each with the Rademacher distribution: for each $n$,

$$ϵ_n{}_{*}P=\frac{1}{2}{\delta }_{-1}+\frac{1}{2}{\delta }_1,$$

in other words, $P({ϵ}_n=1)=\frac{1}{2}$ and $P({ϵ}_n=-1)=\frac{1}{2}$.

We now use Lévy’s inequality to prove the following for independent random variables with the Rademacher distribution.

Theorem 2.

Suppose that $X$ is a real or complex Banach space, and that $x_k\mathrm{\in }X$, $k\mathrm{\ge }\mathrm{1}$. Then for each $a\mathrm{>}\mathrm{0}$ and for each $n\mathrm{\ge }\mathrm{1}$,

$$P(\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel \ge 2a)\le 4{\left(P(\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel \ge a)\right)}^2.$$

Proof.

Let $S_0=0$ and for $1\le k\le n$, define

$$S_k(\omega )=\sum _{1\le j\le k}{ϵ}_j(\omega )x_j,\omega \in \mathrm{\Omega }.$$

Let

$$A=\{\underset{1\le k\le n}{\max }\parallel S_k\parallel \ge a\},B=\{\parallel S_n\parallel \ge a\},C=\{\parallel S_n\parallel \ge 2a\}.$$

Lévy’s inequality tells us that $P(A)\le 2P(B)$.

For $1\le k\le n$, let

and

$$C_k=\{\parallel S_n-S_{k-1}\parallel \ge a\}.$$

If $\omega \in A_k\cap C$, then

$$\parallel S_n(\omega )-S_{k-1}(\omega )\parallel \ge \parallel S_n(\omega )\parallel -\parallel S_{k-1}(\omega )\parallel \ge 2a-a=a,$$

hence $A_k\cap C\subset C_k$. Then because $C\subset A$ and because $A$ is the disjoint union of $A_1,\mathrm{\dots },A_n$,

$$P(C)=P(A\cap C)=P\left(\bigcup _{k=1}^n(A_k\cap C)\right)=\sum _{k=1}^{n}P(A_k\cap C)\le \sum _{k=1}^{n}P(A_k\cap C_k).$$

Let $1\le k\le n$. $P({ϵ}_k^2=1)=1$, so for almost all $\omega \in \mathrm{\Omega }$,

$$\parallel \sum _{j=k}^n{ϵ}_j(\omega )x_j\parallel =\parallel {ϵ}_k(\omega )\sum _{j=k}^n{ϵ}_j(\omega )x_j\parallel =\parallel x_k+\sum _{j=k+1}^n{ϵ}_k(\omega ){ϵ}_j(\omega )x_j\parallel .$$

Thus, for

$$D_k=\{\parallel x_k+\sum _{j=k+1}^n{ϵ}_k{ϵ}_j{x}_j\parallel \ge a\},$$

we have

$$P(C_k\mathrm{△}{D}_k)=0.$$

Let $({\delta }_1,\mathrm{\dots },{\delta }_n)\in {\{+1,-1\}}^n$. On the one hand, because ${\delta }_j^2=1$ and using that ${ϵ}_1,\mathrm{\dots },{ϵ}_n$ are independent,

On the other hand, for $k+1\le j\le n$ we have

and hence

$$P({ϵ}_1={\delta }_1)\mathrm{\cdots }P({ϵ}_k={\delta }_k)P({ϵ}_k{ϵ}_{k+1}={\delta }_{k+1})\mathrm{\cdots }P({ϵ}_k{ϵ}_n={\delta }_n)=2^{-n}.$$

Therefore, for each $1\le k\le n$ and for each $({\delta }_1,\mathrm{\dots },{\delta }_n)\in {\{+1,-1\}}^n$,

But for almost all $\omega \in \mathrm{\Omega }$,

$$({ϵ}_1(\omega ),\mathrm{\dots },{ϵ}_k(\omega ),{ϵ}_k(\omega ){ϵ}_{k+1}(\omega ),\mathrm{\dots },{ϵ}_k(\omega ){ϵ}_n(\omega ))\in {\{+1,-1\}}^n,$$

so it follows that

$${ϵ}_1,\mathrm{\dots },{ϵ}_k,{ϵ}_k{ϵ}_{k+1},\mathrm{\dots },{ϵ}_k{ϵ}_n$$

are independent random variables. We check that $A_k\in \sigma ({ϵ}_1,\mathrm{\dots },{ϵ}_k)$ and $D_k\in \sigma ({\sigma }_k{\sigma }_{k+1},\mathrm{\dots },{\sigma }_k{\sigma }_n)$, and what we have just established means that these $\sigma$-algebras are independent, so

$$P(A_k\cap D_k)=P(A_k)P(D_k).$$

But

$$A_k\cap (C_k\mathrm{△}{D}_k)=(A_k\cap C_k)\mathrm{△}(A_k\cap D_k),$$

so, because $P(C_k\mathrm{△}{D}_k)=0$,

$$P(A_k\cap C_k)=P(A_k\cap D_k)=P(A_k)P(D_k)=P(A_k)P(C_k).$$

We had already established that $P(C)\le {\sum }_{k=1}^{n}P(A_k\cap C_k)$. Using this with the above, and the fact that $A$ is the disjoint union of $A_1,\mathrm{\dots },A_n$, we obtain

$P(C)$ $\le {\displaystyle \sum _{k=1}^n}P(A_k\cap C_k)$

$={\displaystyle \sum _{k=1}^n}P(A_k)P(C_k)$

$\le \left({\displaystyle \sum _{k=1}^n}P(A_k)\right)\underset{1\le k\le n}{\max }P(C_k)$

$=P\left({\displaystyle \bigcup _{k=1}^n}{A}_k\right)\underset{1\le k\le n}{\max }P(C_k)$

$=P(A)\underset{1\le k\le n}{\max }P(C_k).$

As we stated before, we have from Lévy’s inequality that $P(A)\le 2P(B)$, with which

$$P(C)\le 2P(B)\underset{1\le k\le n}{\max }P(C_k).$$

To prove the claim it thus suffices to show that

$$\underset{1\le k\le n}{\max }P(C_k)\le 2P(B).$$

Let $1\le k\le n$. For $\delta =({\delta }_1,\mathrm{\dots },{\delta }_{k-1})\in {\{+1,-1\}}^{k-1}$, let let $H_{k,\delta ,+}$ be those $(t_1,\mathrm{\dots },t_n)\in {ℝ}^n$ such that (i) for each $1\le j\le k-1$, $t_j={\delta }_j$, (ii) $\parallel {\sum }_{j=k}^n{t}_j{x}_j\parallel \ge a$, and (iii)

$$\parallel \sum _{j=1}^n{t}_j{x}_j\parallel \ge a,$$

and let $H_{k,\delta ,-}$ be those $(t_1,\mathrm{\dots },t_n)\in {ℝ}^n$ satisfying (i) and (ii) and

$$\parallel \sum _{j=1}^{k-1}{t}_j{x}_j-\sum _{j=k}^n{t}_j{x}_j\parallel \ge a.$$

Let

$$X=({ϵ}_1,\mathrm{\dots },{ϵ}_n):\mathrm{\Omega }\to {ℝ}^n$$

and let

$$X_k=({ϵ}_1,\mathrm{\dots },{ϵ}_{k-1},-{ϵ}_k,\mathrm{\dots },-{ϵ}_n):\mathrm{\Omega }\to {ℝ}^n,$$

which have the same distribution because ${ϵ}_1,\mathrm{\dots },{ϵ}_n$ are independent and symmetric. Then

$P(X^{-1}(H_{k,\delta ,+}))$ $=(X_{*}P)(H_{k,\delta ,+})$

$=(X_k{}_{*}P)(H_{k,\delta ,+})$

$=P(X_k^{-1}(H_{k,\delta ,+}))$

$=P(X^{-1}(H_{k,\delta ,-})).$

Set

$$C_{k,\delta ,+}=\{X\in H_{k,\delta ,+}\},C_{k,\delta ,-}=\{X\in H_{k,\delta ,-}\},$$

for which we thus have

$$P(C_{k,\delta ,+})=P(C_{k,\delta ,-}).$$

We can write $C_{k,\delta ,+}$ and $C_{k,\delta ,-}$ as

and

If $\omega \in C_k$ then, because $\parallel S_n(\omega )-S_{k-1}(\omega )\parallel \ge a$,

$2a$ $\le 2\parallel S_n(\omega )-S_{k-1}(\omega )\parallel$

$=\parallel S_n(\omega )+(S_n(\omega )-2S_{k-1}(\omega ))\parallel$

$\le \parallel S_n(\omega )\parallel +\parallel S_n(\omega )-2S_{k-1}(\omega )\parallel ,$

so at least one of the inequalities $\parallel S_n(\omega )\parallel \ge a$ and $\parallel S_n(\omega )-2S_{k-1}(\omega )\parallel \ge a$ is true, and hence

$$C_k\subset \{\parallel S_n\parallel \ge a\}\cup \{\parallel S_n-2S_{k-1}\parallel \ge a\}.$$

It follows that

Therefore, using the fact that for almost all $\omega \in \mathrm{\Omega }$,

$$({ϵ}_1(\omega ),\mathrm{\dots },{ϵ}_{k-1}(\omega ))\in {\{+1,-1\}}^{k-1},$$

and

we get

$P(C_k)$

$={\displaystyle \sum _{\delta }}P(C_{k,\delta ,+}\cup C_{k,\delta ,-})$

$=2{\displaystyle \sum _{\delta }}P(C_{k,\delta ,+})$

$=2P(B),$

and thus

$$\underset{1\le k\le n}{\max }P(C_k)\le 2P(B),$$

which proves the claim. ∎

3 Kahane’s inequality

By $E{(X)}^r$ we mean ${(E(X))}^r$. The following is Kahane’s inequality.

Theorem 3 (Kahane’s inequality).

For , there is some $K_{p\mathrm{,}q}\mathrm{>}\mathrm{0}$ such that if $X$ is a real or complex Banach space and $x_k\mathrm{\in }X$, $k\mathrm{\ge }\mathrm{1}$, then for each $n$,

$$E{\left({\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel }^q\right)}^{1/q}\le K_{p,q}\cdot E{\left({\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel }^p\right)}^{1/p}.$$

Proof.

Suppose that ; when $p\ge q$ the claim is immediate with $K_{p,q}=1$. Let

$$M=E{\left({\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel }^p\right)}^{1/p};$$

if $M=0$ we check that the claim is $0\le K_{p,q}\cdot 0$, which is true for, say, $K_{p,q}=1$. Otherwise, $M>0$, and let $u_k=\frac{x_k}{M}$, $1\le k\le n$, for which

$$E\left({\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel }^p\right)=E\left({\parallel \sum _{k=1}^n{ϵ}_k\frac{x_k}{M}\parallel }^p\right)=1.$$ (1)

Using Chebyshev’s inequality,

$$P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel \ge 8^{1/p})=P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k{\parallel }^p\ge 8)\le \frac{1}{8}E(\parallel \sum _{k=1}^n{ϵ}_k{u}_k{\parallel }^p)=\frac{1}{8}.$$

Assume for induction that for some $l\ge 0$ we have

$$P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel \ge 2^l\cdot 8^{1/p})\le \frac{1}{4}\cdot 2^{-2^l};$$ (2)

the above shows that this is true for $l=0$. Applying Theorem 2 and then (2),

$$P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel \ge 2^{l+1}\cdot 8^{1/p})\le 4{\left(P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel \ge 2^l\cdot 8^{1/p})\right)}^2\le \frac{1}{4}\cdot 2^{-2^{l+1}},$$

which shows that (2) is true for all $l\ge 0$.

Generally, for , if $X:\mathrm{\Omega }\to ℝ$ is a random variable for which $P(X\ge 0)=1$, then

$$E(X^q)={\int }_0^{\mathrm{\infty }}q{s}^{q-1}P(X\ge s)ds;$$

the right-hand side is finite if and only if $X\in L^q(P)$. Using this,

$$E(\parallel \sum _{k=1}^n{ϵ}_k{u}_k{\parallel }^q)={\int }_0^{\mathrm{\infty }}q{s}^{q-1}P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel \ge s)ds.$$ (3)

Let ${\alpha }_0=$ and for $l\ge 1$ let ${\alpha }_l=2^{l-1}\cdot 8^{1/p}$, and define

$$f(s)=q{s}^{q-1}P(\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel \ge s),s\ge 0.$$

Using (3) and then (2),

$E\left({\parallel {\displaystyle \sum _{k=1}^n}{ϵ}_k{u}_k\parallel }^q\right)$ $={\displaystyle {\int }_0^{\mathrm{\infty }}}f(s)𝑑s$

$={\displaystyle {\int }_0^{{\alpha }_1}}f(s)𝑑s+{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{\displaystyle {\int }_{{\alpha }_{l+1}}^{{\alpha }_{l+2}}}f(s)𝑑s$

$\le {\displaystyle {\int }_0^{{\alpha }_1}}q{s}^{q-1}ds+{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{\displaystyle {\int }_{{\alpha }_{l+1}}^{{\alpha }_{l+2}}}q{s}^{q-1}P(\parallel {\displaystyle \sum _{k=1}^n}{ϵ}_k{u}_k\parallel \ge {\alpha }_{l+1})ds$

$\le {\alpha }_1^q+{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{\displaystyle {\int }_{{\alpha }_{l+1}}^{{\alpha }_{l+2}}}q{s}^{q-1}{\displaystyle \frac{1}{4}}\cdot 2^{-2^l}𝑑s$

$=8^{q/p}+{\displaystyle \frac{1}{4}}{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{2}^{-2^l}({\alpha }_{l+2}^q-{\alpha }_{l+1}^q),$

and we define $K_{p,q}$ by taking $K_{p,q}^q$ to be equal to the above. Thus

$$E{\left({\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel }^q\right)}^{1/q}\le K_{p,q},$$

and therefore, by (1),

$$E{\left({\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel }^q\right)}^{1/q}\le K_{p,q}\cdot E{\left({\parallel \sum _{k=1}^n{ϵ}_k{u}_k\parallel }^p\right)}^{1/p}.$$

Finally, as $u_k=\frac{x_k}{M}$,

$$E{\left({\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel }^q\right)}^{1/q}\le K_{p,q}\cdot E{\left({\parallel \sum _{k=1}^n{ϵ}_k{x}_k\parallel }^p\right)}^{1/p},$$

which proves the claim. ∎

In the above proof of Kahane’s inequality, for $p=1$ and $q=2$ we have

$K_{1,2}^2$ $=8^2+{\displaystyle \frac{1}{4}}{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{2}^{-2^l}({\alpha }_{l+2}^2-{\alpha }_{l+1}^2)$

$=64+16{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{2}^{-2^l}(2^{2l+2}-2^{2l})$

$=64+48{\displaystyle \sum _{l=0}^{\mathrm{\infty }}}{2}^{-2^l}{2}^{2l},$

for which

$$K_{1,2}=14.006\mathrm{\dots }.$$

In fact, the inequality is true with $K_{1,2}=\sqrt{2}=1.414\mathrm{\dots }$.