Kolmogorov's inequality

Remarks

Let $\tau$ be the first $k$ with $\abs{S_k} \ge \lambda$. The event $\set{\tau = k}$ depends only on $X_1, \dots, X_k$. By independence the cross term $E[S_k (S_n - S_k) \mathbf{1}_{\tau = k}]$ vanishes, so $E[S_n^2 \mathbf{1}_{\tau = k}] \ge E[S_k^2 \mathbf{1}_{\tau = k}] \ge \lambda^2 P(\tau = k)$. Summing over $k$ gives $\lambda^2 P(\tau \le n) \le E[S_n^2]$.

The bound has the same right side as Chebyshev's inequality for the single variable $S_n$, but it controls the whole path $S_1, \dots, S_n$. It is a special case of Doob's martingale inequality, since $(S_k)$ is a martingale.

Example: let the $X_k$ be independent signs, equal to $1$ or $-1$ with probability $1/2$ each. Then the probability that $\abs{S_k} \ge \lambda$ for some $k \le n$ is at most $n / \lambda^2$. With $\lambda = 10 \sqrt{n}$ this is at most $1/100$.

Going deeper

For a student

The inequality is the key step in the proof that a series $\sum X_k$ of independent centred variables with $\sum \operatorname{Var}(X_k) < \infty$ converges almost surely. That result leads to Kolmogorov's three-series theorem and to the strong law of large numbers for independent variables with suitable finite variances.