Probability Inequalities

Last updated: 2026-04-12

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 then
P(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, then
P{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*}
But
ESn2IAk=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*}
since
ESk(ξ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. Hence
ESn2≥∑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 that
ESn2IA=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 therefore
ESn2IA=∑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 get
ESn2IA−ε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 obtain
P(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