Khinchin’s inequality and Etemadi’s inequality

1 Khinchin’s inequality

We will use the following to prove Khinchin’s inequality.

Lemma 1.

Let $X_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{X}_n$ be independent random variables each with the Rademacher distribution. For $a_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{a}_n\mathrm{\in }\mathrm{R}$ and $\lambda \mathrm{>}\mathrm{0}$,

$$P\left(\right|S_n|>\lambda {\left(\sum _{k=1}^n{a}_k^2\right)}^{1/2})\le 2e^{-{\lambda }^2/2},$$

where

$$S_n=\sum _{k=1}^n{a}_k{X}_k.$$

Proof.

For $t\in ℝ$,

$$E(e^{t{a}_k{X}_k})={\int }_{ℝ}{e}^{t{a}_{k}x}d\left(\frac{1}{2}{\delta }_{-1}+\frac{1}{2}{\delta }_1\right)(x)=\frac{1}{2}(e^{-t{a}_k}+e^{t{a}_k})=\cosh (t{a}_k).$$

Because the $X_k$ are independent,

$$E(e^{t{S}_n})=\prod _{k=1}^{n}E(e^{t{a}_k{X}_k})=\prod _{k=1}^n\cosh (t{a}_k),$$

and because $\cosh x\le e^{x^2/2}$ for all $x\in ℝ$, we have

$$E(e^{t{S}_n})\le \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^{t{S}_n})\le \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

which yields $P(S_n>\lambda \sigma )\le e^{-\lambda \sigma t}E(e^{t{S}_n})$, and hence

$$P(S_n>\lambda \sigma )\le e^{-\lambda \sigma t}\exp \left(\frac{t^2{\sigma }^2}{2}\right)=\exp (-\lambda \sigma t+\frac{t^2{\sigma }^2}{2}).$$

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 )\le \exp (-{\lambda }^2+\frac{{\lambda }^2}{2})=e^{-{\lambda }^2/2}.$$

For $t>0$,

which yields , and hence

whence

Therefore

proving the claim. ∎

Corollary 2.

Let $X_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{X}_n$ be independent random variables each with the Rademacher distribution. For ${\alpha }_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{\alpha }_n\mathrm{\in }\mathrm{C}$ and $\lambda \mathrm{>}\mathrm{0}$,

$$P\left(\right|S_n|>\lambda {(\sum _{k=1}^n|{\alpha }_k{|}^2)}^{1/2})\le 4e^{-{\lambda }^2/2},$$

where

$$S_n=\sum _{k=1}^n{\alpha }_k{X}_k.$$

Proof.

Write ${\alpha }_k=a_k+i{b}_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},\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(\right|S_n|>\lambda {\left(\sum _{k=1}^n{a}_k^2\right)}^{1/2})\le 2e^{-{\lambda }^2/2}$$

and

$$P\left(\right|S_n|>\lambda {\left(\sum _{k=1}^n{b}_k^2\right)}^{1/2})\le 2e^{-{\lambda }^2/2},$$

thus

$P\left(\right|S_n|>\lambda {({\displaystyle \sum _{k=1}^n}|{\alpha }_k{|}^2)}^{1/2})$ $\le P\left(\right|S_n|>\lambda {\left({\displaystyle \sum _{k=1}^n}{a}_k^2\right)}^{1/2})$

$+P\left(\right|S_n|>\lambda {\left({\displaystyle \sum _{k=1}^n}{b}_k^2\right)}^{1/2})$

$\le 4e^{-{\lambda }^2/2},$

proving the claim. ∎

We now prove Khinchin’s inequality.

Theorem 3 (Khinchin’s inequality).

For , let

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

and let $\frac{\mathrm{1}}{p}\mathrm{+}\frac{\mathrm{1}}{q}\mathrm{=}\mathrm{1}$. If $X_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{X}_n$ are independent random variables each with the Rademacher distribution and $a_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{a}_n\mathrm{\in }\mathrm{C}$, then

$$C{(q)}^{-1}{\left(\sum _{k=1}^n{|a_k|}^2\right)}^{1/2}\le E{\left({\left|\sum _{k=1}^n{a}_k{X}_k\right|}^p\right)}^{1/p}\le 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^{\mathrm{\infty }}p{t}^{p-1}\cdot 4e^{-t^2/2}𝑑t\right)}^{1/p}={\left(2^{1+\frac{p}{2}}\cdot p\cdot \mathrm{\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}\le E{\left({\left|\sum _{k=1}^n{\alpha }_k{X}_k\right|}^p\right)}^{1/p}\le 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\ge 0)=1$,

$$E(X^p)={\int }_0^{\mathrm{\infty }}p{t}^{p-1}P(X\ge t)dt,$$

we obtain, applying Lemma 2,

$$E(|S_n{|}^p)={\int }_0^{\mathrm{\infty }}p{t}^{p-1}P(|S_n|\ge t)dt\le {\int }_0^{\mathrm{\infty }}p{t}^{p-1}\cdot 4e^{-t^2/2}dt,$$

and thus

$$E{({|S_n|}^p)}^{1/p}\le 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)\le 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}\le C(q),$$

and as ${\sum }_{k=1}^n{|{\alpha }_k|}^2=1$ we obtain

$$1\le C(q)E{\left({\left|\sum _{k=1}^n{\alpha }_k{X}_k\right|}^p\right)}^{1/p}.$$

Thus we have

$$C{(q)}^{-1}\le E{({|S_n|}^p)}^{1/p}\le C(p),$$

which proves the claim. ∎

2 Etemadi’s inequality

The following is Etemadi’s inequality.

Theorem 4 (Etemadi’s inequality).

If $X_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{X}_n$ are independent random variables, then for any $x\mathrm{>}\mathrm{0}$,

$$P(\underset{1\le k\le n}{\max }|S_k|\ge 3x)\le 2P(|S_n|\ge x)+\underset{1\le k\le n}{\max }P(|S_k|\ge x)\le 3\underset{1\le k\le n}{\max }P(|S_k|\ge x),$$

where $S_k\mathrm{=}{\mathrm{\sum }}_{j\mathrm{=}\mathrm{1}}^k{X}_j$.

Proof.

For $k=1,\mathrm{\dots },n$, let

with $A_1=\{|S_1|\ge 3x\}$. $A_1,\mathrm{\dots },A_n$ are disjoint, and

$$A=\bigcup _{k=1}^n{A}_k=\{\underset{1\le k\le n}{\max }|S_k|\ge 3x\}.$$

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

and also, the events $A_k$ and $\{|S_n-S_k|>2x\}$ are independent, and thus

$P(A)$

$\le P(|S_n|\ge x)+{\displaystyle \sum _{k=1}^n}P(A_k\cap \{|S_n-S_k|>2x\})$

$=P(|S_n|\ge x)+{\displaystyle \sum _{k=1}^n}P(A_k)P(|S_n-S_k|>2x)$

$\le P(|S_n|\ge x)+\underset{1\le k\le n}{\max }P(|S_n-S_k|>2x)\cdot P(A).$

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

$P(A)$ $\le P(|S_n|\ge x)+\underset{1\le k\le n}{\max }P(|S_n-S_k|>2x)$

$\le P(|S_n|\ge x)+\underset{1\le k\le n}{\max }(P(|S_n|>x)+P(|S_k|>x)).$

∎

The following inequality is similar enough to Etemadi’s inequality to be placed in this note.

Lemma 5.

Let ${\xi }_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{\xi }_n$ be independent random variables with sample space $\mathrm{(}\mathrm{\Omega }\mathrm{,}\mathrm{F}\mathrm{,}P\mathrm{)}$. Let ${\zeta }_{\mathrm{0}}\mathrm{=}\mathrm{0}$ and for $\mathrm{1}\mathrm{\le }k\mathrm{\le }n$ let ${\xi }_k\mathrm{=}{\mathrm{\sum }}_{i\mathrm{=}\mathrm{1}}^k{\xi }_i$. If $P\mathrm{(}\mathrm{|}{\zeta }_n\mathrm{-}{\zeta }_k\mathrm{|}\mathrm{\le }t\mathrm{)}\mathrm{\ge }\alpha$ for $\mathrm{0}\mathrm{\le }k\mathrm{\le }n$ then

$$P(\underset{1\le k\le n}{\max }|{\zeta }_k|>2t)\le {\alpha }^{-1}P(|{\zeta }_n|>t).$$

Proof.

For $0\le k\le n$ let

$$A_k=\{|{\zeta }_1|\le 2t,\mathrm{\dots },|{\zeta }_{k-1}|\le 2t,|{\zeta }_k|>2t\},B_k=\{|{\zeta }_n-{\zeta }_k|\le t\},$$

where $A_0=\mathrm{\Omega }$. Because $|{\zeta }_n|\ge |{\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\ne k$ the events $A_j$ and $A_k$ are disjoint, so the sets $A_1\cap B_1,\mathrm{\dots },A_k\cap B_k$ are pairwise disjoint, hence

$$P(|{\zeta }_n|>t)\ge 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,\mathrm{\dots },{\xi }_n$ are independent one checks that the events $A_k$ and $B_k$ are independent, and using this,

$$P(|{\zeta }_n|>t)\ge \sum _{k=1}^{n}P(A_k)P(B_k)\ge \alpha \sum _{k=1}^{n}P(A_k)=\alpha P\left(\bigcup _{k=1}^n{A}_k\right),$$

that is,

$$P(|{\zeta }_n|>t)\ge \alpha P(\underset{1\le k\le n}{\max }|{\zeta }_k|>2t),$$

proving the claim. ∎