# Khinchin’s inequality and Etemadi’s inequality

Jordan Bell
September 4, 2015

## 1 Khinchin’s inequality

We will use the following to prove Khinchin’s inequality.11 1 Camil Muscalu and Wilhelm Schlag, Classical and Multilinear Harmonic Analysis, volume I, p. 113, Lemma 5.4.

###### Lemma 1.

Let $X_{1},\ldots,X_{n}$ be independent random variables each with the Rademacher distribution. For $a_{1},\ldots,a_{n}\in\mathbb{R}$ and $\lambda>0$,

 $P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}a_{k}^{2}\right)^{1/2}% \right)\leq 2e^{-\lambda^{2}/2},$

where

 $S_{n}=\sum_{k=1}^{n}a_{k}X_{k}.$
###### Proof.

For $t\in\mathbb{R}$,

 $E(e^{ta_{k}X_{k}})=\int_{\mathbb{R}}e^{ta_{k}x}d\left(\frac{1}{2}\delta_{-1}+% \frac{1}{2}\delta_{1}\right)(x)=\frac{1}{2}(e^{-ta_{k}}+e^{ta_{k}})=\cosh(ta_{% k}).$

Because the $X_{k}$ are independent,

 $E(e^{tS_{n}})=\prod_{k=1}^{n}E(e^{ta_{k}X_{k}})=\prod_{k=1}^{n}\cosh(ta_{k}),$

and because $\cosh x\leq e^{x^{2}/2}$ for all $x\in\mathbb{R}$, we have

 $E(e^{tS_{n}})\leq\prod_{k=1}^{n}e^{\frac{t^{2}a_{k}^{2}}{2}}=\exp\left(\frac{t% ^{2}}{2}\sum_{k=1}^{n}a_{k}^{2}\right).$

Let $\sigma^{2}=\sum_{k=1}^{n}a_{k}^{2}$, with which

 $E(e^{tS_{n}})\leq\exp\left(\frac{t^{2}\sigma^{2}}{2}\right).$

Because $t\mapsto e^{\lambda\sigma t}$ is nonnegative and nondecreasing, for $t>0$ we have

 $1_{S_{n}>\lambda\sigma}e^{\lambda\sigma t}

which yields $P(S_{n}>\lambda\sigma)\leq e^{-\lambda\sigma t}E(e^{tS_{n}})$, and hence

 $P(S_{n}>\lambda\sigma)\leq e^{-\lambda\sigma t}\exp\left(\frac{t^{2}\sigma^{2}% }{2}\right)=\exp\left(-\lambda\sigma t+\frac{t^{2}\sigma^{2}}{2}\right).$

The minimum of the right-hand side occurs when $\lambda\sigma=t\sigma^{2}$, i.e. $t=\frac{\lambda}{\sigma}$, at which

 $P(S_{n}>\lambda\sigma)\leq\exp\left(-\lambda^{2}+\frac{\lambda^{2}}{2}\right)=% e^{-\lambda^{2}/2}.$

For $t>0$,

 $1_{S_{n}<-\lambda\sigma}e^{\lambda\sigma t}

which yields $P(S_{n}<-\lambda\sigma)\leq e^{-\lambda\sigma t}E(e^{-tS_{n}})$, and hence

 $P(S_{n}<-\lambda\sigma)\leq e^{-\lambda\sigma t}\exp\left(\frac{(-t)^{2}\sigma% ^{2}}{2}\right)=\exp\left(-\lambda\sigma t+\frac{t^{2}\sigma^{2}}{2}\right),$

whence

 $P(S_{n}<-\lambda\sigma)\leq e^{-\lambda^{2}/2}.$

Therefore

 $P(|S_{n}|>\lambda\sigma)=P(S_{n}>\lambda\sigma)+P(S_{n}<-\lambda\sigma)\leq 2e% ^{-\lambda^{2}/2},$

proving the claim. ∎

###### Corollary 2.

Let $X_{1},\ldots,X_{n}$ be independent random variables each with the Rademacher distribution. For $\alpha_{1},\ldots,\alpha_{n}\in\mathbb{C}$ and $\lambda>0$,

 $P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}|\alpha_{k}|^{2}\right)^{% 1/2}\right)\leq 4e^{-\lambda^{2}/2},$

where

 $S_{n}=\sum_{k=1}^{n}\alpha_{k}X_{k}.$
###### Proof.

Write $\alpha_{k}=a_{k}+ib_{k}$. If

 $\left|S_{n}(\omega)\right|>\lambda\left(\sum_{k=1}^{n}|\alpha_{k}|^{2}\right)^% {1/2},$

then

 $|S_{n}(\omega)|^{2}>\lambda^{2}\sum_{k=1}^{n}(a_{k}^{2}+b_{k}^{2}).$

But

 $|S_{n}(\omega)|^{2}=\left(\sum_{k=1}^{n}a_{k}X_{k}(\omega)\right)^{2}+\left(% \sum_{k=1}^{n}b_{k}X_{k}(\omega)\right)^{2},$

so at least one of the following is true:

 $\left|\sum_{k=1}^{n}a_{k}X_{k}(\omega)\right|>\lambda\left(\sum_{k=1}^{n}a_{k}% ^{2}\right)^{1/2},\qquad\left|\sum_{k=1}^{n}b_{k}X_{k}(\omega)\right|>\lambda% \left(\sum_{k=1}^{n}b_{k}^{2}\right)^{1/2}.$

By Lemma 4,

 $P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}a_{k}^{2}\right)^{1/2}% \right)\leq 2e^{-\lambda^{2}/2}$

and

 $P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}b_{k}^{2}\right)^{1/2}% \right)\leq 2e^{-\lambda^{2}/2},$

thus

 $\displaystyle P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}|\alpha_{k}% |^{2}\right)^{1/2}\right)$ $\displaystyle\leq P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}a_{k}^{% 2}\right)^{1/2}\right)$ $\displaystyle+P\left(\left|S_{n}\right|>\lambda\left(\sum_{k=1}^{n}b_{k}^{2}% \right)^{1/2}\right)$ $\displaystyle\leq 4e^{-\lambda^{2}/2},$

proving the claim. ∎

We now prove Khinchin’s inequality.22 2 Camil Muscalu and Wilhelm Schlag, Classical and Multilinear Harmonic Analysis, volume I, p. 114, Lemma 5.5; Thomas H. Wolff, Lectures on Harmonic Analysis, p. 28, Proposition 4.5.

###### Theorem 3 (Khinchin’s inequality).

For $1\leq p<\infty$, let

 $C(p)=\left(2^{1+\frac{p}{2}}\cdot p\cdot\Gamma\left(\frac{p}{2}\right)\right)^% {1/p},$

and let $\frac{1}{p}+\frac{1}{q}=1$. If $X_{1},\ldots,X_{n}$ are independent random variables each with the Rademacher distribution and $a_{1},\ldots,a_{n}\in\mathbb{C}$, then

 $C(q)^{-1}\left(\sum_{k=1}^{n}|a_{k}|^{2}\right)^{1/2}\leq E\left(\left|\sum_{k% =1}^{n}a_{k}X_{k}\right|^{p}\right)^{1/p}\leq C(p)\left(\sum_{k=1}^{n}|a_{k}|^% {2}\right)^{1/2}.$
###### Proof.

First we remark that it can be computed that

 $\left(\int_{0}^{\infty}pt^{p-1}\cdot 4e^{-t^{2}/2}dt\right)^{1/p}=\left(2^{1+% \frac{p}{2}}\cdot p\cdot\Gamma\left(\frac{p}{2}\right)\right)^{1/p}=C(p).$

Let $\sigma^{2}=\sum_{k=1}^{n}|a_{k}|^{2}$ and let $\alpha_{k}=\frac{a_{k}}{\sigma}$; if $\sigma=0$ then the claim is immediate. To prove the claim it is equivalent to prove that

 $C(q)^{-1}\leq E\left(\left|\sum_{k=1}^{n}\alpha_{k}X_{k}\right|^{p}\right)^{1/% p}\leq C(p).$

Write $S_{n}=\sum_{k=1}^{n}\alpha_{k}X_{k}$. Using the fact that for a random variable $X$ with $P(X\geq 0)=1$,

 $E(X^{p})=\int_{0}^{\infty}pt^{p-1}P(X\geq t)dt,$

we obtain, applying Lemma 2,

 $E(|S_{n}|^{p})=\int_{0}^{\infty}pt^{p-1}P(|S_{n}|\geq t)dt\leq\int_{0}^{\infty% }pt^{p-1}\cdot 4e^{-t^{2}/2}dt,$

and thus

 $E(|S_{n}|^{p})^{1/p}\leq C(p).$ (1)

Using Hölder’s inequality, because the $X_{k}$ are independent and $E(X_{k})=0$ and $E(|X_{k}|^{2})=1$,

 $\sum_{k=1}^{n}|\alpha_{k}|^{2}=E\left(\left|\sum_{k=1}^{n}\alpha_{k}X_{k}% \right|^{2}\right)\leq E\left(\left|\sum_{k=1}^{n}\alpha_{k}X_{k}\right|^{p}% \right)^{1/p}E\left(\left|\sum_{k=1}^{n}\alpha_{k}X_{k}\right|^{q}\right)^{1/q}.$

Applying (1),

 $E\left(\left|\sum_{k=1}^{n}\alpha_{k}X_{k}\right|^{q}\right)^{1/q}\leq C(q),$

and as $\sum_{k=1}^{n}|\alpha_{k}|^{2}=1$ we obtain

 $1\leq C(q)E\left(\left|\sum_{k=1}^{n}\alpha_{k}X_{k}\right|^{p}\right)^{1/p}.$

Thus we have

 $C(q)^{-1}\leq E(|S_{n}|^{p})^{1/p}\leq C(p),$

which proves the claim. ∎

The following is Etemadi’s inequality.33 3 Allan Gut, Probability: A Graduate Course, p. 143, Theorem 7.6.

If $X_{1},\ldots,X_{n}$ are independent random variables, then for any $x>0$,

 $P\left(\max_{1\leq k\leq n}|S_{k}|\geq 3x\right)\leq 2P(|S_{n}|\geq x)+\max_{1% \leq k\leq n}P(|S_{k}|\geq x)\leq 3\max_{1\leq k\leq n}P(|S_{k}|\geq x),$

where $S_{k}=\sum_{j=1}^{k}X_{j}$.

###### Proof.

For $k=1,\ldots,n$, let

 $A_{k}=\left\{\max_{1\leq j\leq k-1}|S_{j}|<3x\right\}\cap\{|S_{k}|\geq 3x\},$

with $A_{1}=\{|S_{1}|\geq 3x\}$. $A_{1},\ldots,A_{n}$ are disjoint, and

 $A=\bigcup_{k=1}^{n}A_{k}=\left\{\max_{1\leq k\leq n}|S_{k}|\geq 3x\right\}.$

For each $1\leq k\leq n$,

 $A_{k}\cap\{|S_{n}|2x\},$

and also, the events $A_{k}$ and $\{|S_{n}-S_{k}|>2x\}$ are independent, and thus

 $\displaystyle P(A)$ $\displaystyle=P(A\cap\{|S_{n}|\geq x\})+P(A\cap\{|S_{n}| $\displaystyle\leq P(|S_{n}|\geq x)+P(A\cap\{|S_{n}| $\displaystyle\leq P(|S_{n}|\geq x)+\sum_{k=1}^{n}P(A_{k}\cap\{|S_{n}-S_{k}|>2x\})$ $\displaystyle=P(|S_{n}|\geq x)+\sum_{k=1}^{n}P(A_{k})P(|S_{n}-S_{k}|>2x)$ $\displaystyle\leq P(|S_{n}|\geq x)+\max_{1\leq k\leq n}P(|S_{n}-S_{k}|>2x)% \cdot P(A).$

Then, because $|a-b|>2x$ implies that $|a|>x$ or $|b|>x$,

 $\displaystyle P(A)$ $\displaystyle\leq P(|S_{n}|\geq x)+\max_{1\leq k\leq n}P(|S_{n}-S_{k}|>2x)$ $\displaystyle\leq P(|S_{n}|\geq x)+\max_{1\leq k\leq n}\left(P(|S_{n}|>x)+P(|S% _{k}|>x)\right).$

The following inequality is similar enough to Etemadi’s inequality to be placed in this note.44 4 K. R. Parthasarathy, Probability Measures on Metric Spaces, p. 219, Chapter VII, Lemma 4.1.

###### Lemma 5.

Let $\xi_{1},\ldots,\xi_{n}$ be independent random variables with sample space $(\Omega,\mathscr{F},P)$. Let $\zeta_{0}=0$ and for $1\leq k\leq n$ let $\xi_{k}=\sum_{i=1}^{k}\xi_{i}$. If $P(|\zeta_{n}-\zeta_{k}|\leq t)\geq\alpha$ for $0\leq k\leq n$ then

 $P\left(\max_{1\leq k\leq n}|\zeta_{k}|>2t\right)\leq\alpha^{-1}P(|\zeta_{n}|>t).$
###### Proof.

For $0\leq k\leq n$ let

 $A_{k}=\{|\zeta_{1}|\leq 2t,\ldots,|\zeta_{k-1}|\leq 2t,|\zeta_{k}|>2t\},\qquad B% _{k}=\{|\zeta_{n}-\zeta_{k}|\leq t\},$

where $A_{0}=\Omega$. Because $|\zeta_{n}|\geq|\zeta_{k}|-|\zeta_{n}-\zeta_{k}|$,

 $A_{k}\cap B_{k}\subset\{|\zeta_{n}|>t\},$

and so

 $\bigcup_{k=1}^{n}(A_{k}\cap B_{k})\subset\{|\zeta_{n}|>t\}.$

It is apparent that for $j\neq k$ the events $A_{j}$ and $A_{k}$ are disjoint, so the sets $A_{1}\cap B_{1},\ldots,A_{k}\cap B_{k}$ are pairwise disjoint, hence

 $P(|\zeta_{n}|>t)\geq P\left(\bigcup_{k=1}^{n}(A_{k}\cap B_{k})\right)=\sum_{k=% 1}^{n}P(A_{k}\cap B_{k}).$

For each $k$, using that $\xi_{1},\ldots,\xi_{n}$ are independent one checks that the events $A_{k}$ and $B_{k}$ are independent, and using this,

 $P(|\zeta_{n}|>t)\geq\sum_{k=1}^{n}P(A_{k})P(B_{k})\geq\alpha\sum_{k=1}^{n}P(A_% {k})=\alpha P\left(\bigcup_{k=1}^{n}A_{k}\right),$

that is,

 $P(|\zeta_{n}|>t)\geq\alpha P\left(\max_{1\leq k\leq n}|\zeta_{k}|>2t\right),$

proving the claim. ∎