Probability Inequalities

This article gives systematic description of the inequalities and bounds used in probability and statistics.

Kolmogorov’s maximal inequality

Kolmogorov's inequality is one of the main inequalities in the probability theory, it provides the upper bound for the maximum of the sum of independent identical random variables.
Theorem (Kolmogorov’s maximal inequality)
A\mathbf{A} Let ξ1,ξ2,…,ξn\xi_1, \xi_2, \ldots, \xi_n be independent random variables with Eξi=0, Eξi2<∞\mathrm{E} \xi_i=0, \, \mathrm{E} \xi_i^2<\infty, i≤ni \leq n. If Sn=ξ1+…ξnS_n = \xi_1 + \dots \xi_n thenP(max⁡1≤k≤n∣Sk∣≥ε)≤ESn2ε2.\begin{equation}\mathrm{P} \left( \max _{1 \leq k \leq n}\left|S_k \right| \geq \varepsilon \right) \leq \frac{E S_n^2}{\varepsilon^2} .\end{equation}B\mathbf{B} If also P(∣ξi∣≤c)=1,i≤n\mathrm{P}\left(\left|\xi_i\right| \leq c\right)=1, i \leq n, thenP{max⁡1≤k≤n∣Sk∣≥ε}≥1−(c+ε)2ESn2.\begin{equation}\mathrm{P}\left\{\max _{1 \leq k \leq n}\left|S_k\right| \geq \varepsilon\right\} \geq 1-\frac{(c+\varepsilon)^2}{E S_n^2} .\end{equation}
\quad Proof. A\mathbf{A} We put
A={max⁡1≤k≤n∣Sk∣≥ε},Ak={∣Si∣<ε,i=1,…,k−1,∣Sk∣≥ε},1≤k≤n,\begin{align*}A & =\left\{\max_{1 \leq k \leq n} \left|S_k\right| \geq \varepsilon\right\}, \\A_k & =\left\{\left|S_i\right|<\varepsilon, i=1, \ldots, k-1,\left|S_k\right| \geq \varepsilon\right\}, \quad 1 \leq k \leq n ,\end{align*}i.e., we break things down according to the time that ∣Sk∣\left|S_k\right| first exceeds ε\varepsilon. Then Ak∩Aj=∅, j≠kA_k \cap A_j = \emptyset, \, j \neq k and A=⋃k=1nAkA= \bigcup_{k=1}^{n} A_k,ESn2≥ESn2IA=∑k=1nESn2IAk\begin{equation*}E S_n^2 \geq E S_n^2 I_A=\sum_{k = 1}^{n} E S_n^2 I_{A_k}\end{equation*}ButESn2IAk=E(Sk+(ξk+1+⋯+ξn))2IAk=ESk2IAk+2ESk(ξk+1+⋯+ξn)IAk+E(ξk+1+⋯+ξn)2IAk≥ESk2IAk,\begin{align*}\mathrm{E} S_n^2 I_{A_k} & =\mathrm{E}\left(S_k+\left(\xi_{k+1}+\cdots+\xi_n\right)\right)^2 I_{A_k} \\& =E S_k^2 I_{A_k}+2 \mathrm{E} S_k\left(\xi_{k+1}+\cdots+\xi_n\right) I_{A_k}+\mathrm{E}\left(\xi_{k+1}+\cdots+\xi_n\right)^2 I_{A_k} \\& \geq \mathrm{E} S_k^2 I_{A_k},\end{align*}sinceESk(ξk+1+⋯+ξn)IAk=ESkIAk⋅E(ξk+1+⋯+ξn)=0\begin{equation*}E S_k\left(\xi_{k+1}+\cdots+\xi_n\right) I_{A_k}=E S_k I_{A_k} \cdot \mathrm{E}\left(\xi_{k+1}+\cdots+\xi_n\right)=0\end{equation*}because of independence and the conditions Eξi=0,i≤n\mathrm{E} \xi_i=0, i \leq n. HenceESn2≥∑k=1nESk2IAk≥ε2∑k=1nP(Ak)=ε2P(max⁡1≤k≤n∣Sk∣≥ε),\begin{equation*}E S_n^2 \geq \sum_{k = 1}^{n} \mathrm{ES}_k^2 I_{A_k} \geq \varepsilon^2 \sum_{k = 1}^{n} \mathrm{P}\left(A_k\right)=\varepsilon^2 \mathrm{P} \left( \max _{1 \leq k \leq n}\left|S_k \right| \geq \varepsilon \right),\end{equation*}which proves the inequality (1).

B\mathbf{B} To prove (2), we observe thatESn2IA=ESn2−ESn2IAˉ≥ESn2−ε2P(Aˉ)=ESn2−ε2+ε2P(A).\begin{equation}\mathrm{E} S_n^2 I_A=\mathrm{E} S_n^2-\mathrm{E} S_n^2 I_{\bar{A}} \geq \mathrm{E} S_n^2-\varepsilon^2 \mathrm{P}(\bar{A})=\mathrm{E} S_n^2-\varepsilon^2+\varepsilon^2 \mathrm{P}(A) .\end{equation}On the other hand, on the set AkA_k∣Sk−1∣≤ε,∣Sk∣≤∣Sk−1∣+∣ξk∣≤ε+c\begin{equation*}\left|S_{k-1}\right| \leq \varepsilon, \quad\left|S_k\right| \leq\left|S_{k-1}\right|+\left|\xi_k\right| \leq \varepsilon+c\end{equation*}and thereforeESn2IA=∑k=1nESk2IAk+∑kE(IAk(Sn−Sk)2)≤(ε+c)2∑k=1nP(Ak)+∑k=1nP(Ak)∑j=k+1nEξj2≤P(A)[(ε+c)2+∑j=1nEξj2]=P(A)[(ε+c)2+ESn2].\begin{align}\mathrm{E} S_n^2 I_A & =\sum_{k = 1}^{n} \mathrm{E} S_k^2 I_{A_k}+\sum_k \mathrm{E}\left(I_{A_k}\left(S_n-S_k\right)^2\right) \\& \leq(\varepsilon+c)^2 \sum_{k = 1}^{n} \mathrm{P}\left(A_k\right)+\sum_{k=1}^n \mathrm{P}\left(A_k\right) \sum_{j=k+1}^n \mathrm{E} \xi_j^2 \\& \leq \mathrm{P}(A)\left[(\varepsilon+c)^2+\sum_{j=1}^n \mathrm{E} \xi_j^2\right]=\mathrm{P}(A)\left[(\varepsilon+c)^2+\mathrm{E} S_n^2\right] .\end{align}Then we can subtract ε2P(A)\varepsilon^2 \mathrm{P}(A) from both sides of (4) and getESn2IA−ε2P(A)≤P(A)[(ε+c)2+ESn2−ε2]\begin{equation}\mathrm{E} S_n^2 I_A - \varepsilon^2 \mathrm{P}(A) \leq \mathrm{P}(A)\left[(\varepsilon+c)^2+\mathrm{E} S_n^2 - \varepsilon^2 \right]\end{equation}Finally, using (3) and (5) we obtainP(A)≥ESn2−ε2(ε+c)2+ESn2−ε2=1−(ε+c)2(ε+c)2+ESn2−ε2≥1−(ε+c)2ESn2.\begin{equation*}\mathrm{P}(A) \geq \frac{\mathrm{E} S_n^2-\varepsilon^2}{(\varepsilon+c)^2+\mathrm{E} S_n^2-\varepsilon^2}=1-\frac{(\varepsilon+c)^2}{(\varepsilon+c)^2+\mathrm{E} S_n^2-\varepsilon^2} \geq 1-\frac{(\varepsilon+c)^2}{\mathrm{E} S_n^2} .\end{equation*}This completes the proof of (3). □\Box

References

  • Shiryaev A. N., ---Probability---. Springer-Verlag, Berlin Heidelberg, 1996 (English translation).