Kolmogorov's Maximal Inequality

Controlling All Partial Sums at Once

For a sequence of random variables, controlling one partial sum is not the same as controlling every partial sum up to a given time. Kolmogorov’s maximal inequality gives a bound on the probability that any partial sum crosses a fixed threshold. Its hypotheses are important: the variables must be independent, have mean zero, and have finite variances.

Throughout, $(\Omega,\mathcal{F},\mathbb{P})$ is a probability space, and $X_1,\ldots,X_n$ are real-valued, independent random variables with $\mathbb{E}[X_j]=0$ and $\mathbb{E}[X_j^2]<\infty$ for every $j$. Define the partial sums $S_k=\sum_{j=1}^k X_j$ for $1\le k\le n$, and set $S_0=0$. A threshold $\lambda$ below is always strictly positive. The crossing event uses the non-strict inequality $\max_{1\le k\le n}|S_k|\ge\lambda$.

Theorem (Kolmogorov’s Maximal Inequality): Under these hypotheses, for every $\lambda>0$, $$ \mathbb{P}\!\left(\max_{1\le k\le n}|S_k|\ge\lambda\right) \le \frac{1}{\lambda^2}\sum_{j=1}^n\mathbb{E}[X_j^2]. $$ Since $\mathbb{E}[X_j]=0$, each $\mathbb{E}[X_j^2]$ is the variance of $X_j$. The probability space has total measure one; no completeness assumption is needed.

Proof by the First Crossing

The key is to divide the event according to the first index at which the threshold is reached. This makes the crossing information depend only on variables observed up to that index. The remaining sum is independent of that information and has mean zero.

Proof. For each $k=1,\ldots,n$, define $$ A_k=\{|S_1|<\lambda,\ldots,|S_{k-1}|<\lambda,\ |S_k|\ge\lambda\}. $$ For $k=1$, the list of conditions before $|S_k|\ge\lambda$ is empty. Each $A_k$ is in $\sigma(X_1,\ldots,X_k)$. The events $A_k$ are pairwise disjoint, and their union is $A=\{\max_{1\le j\le n}|S_j|\ge\lambda\}$: on $A$, there is a first crossing index, and it is unique.

Fix $k$, and put $T_k=S_n-S_k=\sum_{j=k+1}^n X_j$, with $T_n=0$. Independence implies that $T_k$ is independent of $\sigma(X_1,\ldots,X_k)$, hence independent of the pair $(\chi_{A_k},S_k)$; also $\mathbb{E}[T_k]=0$. All products in the following expansion are integrable: $S_k,T_k$ have finite second moments, so their product is integrable by Cauchy–Schwarz. Independence and the zero mean give $$ \mathbb{E}[\chi_{A_k}S_kT_k] =\mathbb{E}[\chi_{A_k}S_k]\,\mathbb{E}[T_k]=0. $$ Since $S_n=S_k+T_k$, expansion of the square yields $$ \mathbb{E}[\chi_{A_k}S_n^2] =\mathbb{E}[\chi_{A_k}S_k^2]+\mathbb{E}[\chi_{A_k}T_k^2] +2\mathbb{E}[\chi_{A_k}S_kT_k] \ge \mathbb{E}[\chi_{A_k}S_k^2] \ge \lambda^2\mathbb{P}(A_k). $$ The first inequality uses $T_k^2\ge0$; the second uses $|S_k|\ge\lambda$ on $A_k$. Because the $A_k$ are disjoint and $S_n^2\ge0$, $$ \mathbb{E}[S_n^2]\ge\sum_{k=1}^n\mathbb{E}[\chi_{A_k}S_n^2] \ge\lambda^2\sum_{k=1}^n\mathbb{P}(A_k) =\lambda^2\mathbb{P}(A). $$ Finally, expanding $S_n^2=(\sum_{j=1}^nX_j)^2$, every cross term has expectation zero: for $i<j$, independence gives $\mathbb{E}[X_iX_j]=\mathbb{E}[X_i]\mathbb{E}[X_j]=0$. Therefore $\mathbb{E}[S_n^2]=\sum_{j=1}^n\mathbb{E}[X_j^2]$. Divide by $\lambda^2>0$ to obtain the asserted bound. $\square$

The proof also shows why the partial sums are treated as a family rather than by a union bound over $k$: the first-crossing events are disjoint, and the future increments cannot cancel the squared size at the first crossing in expectation. The resulting bound uses the total variance once, rather than a separate estimate at each time.

Worked Applications

Worked Example: A Symmetric Random Walk of Length Eight

Let $X_1,\ldots,X_8$ be independent, with $\mathbb{P}(X_j=1)=\mathbb{P}(X_j=-1)=1/2$. Compute the maximal-inequality bound for threshold $\lambda=3$, and compare it with the exact crossing probability.

Each variable has mean $(1)(1/2)+(-1)(1/2)=0$, and second moment $1^2(1/2)+(-1)^2(1/2)=1$. Thus the total variance in the bound is $8$, and the bound is $$ \mathbb{P}\!\left(\max_{1\le k\le8}|S_k|\ge3\right) \le\frac{8}{3^2}=\frac89. $$ To check this against the exact probability, count paths that do not cross either boundary $3$ or $-3$. Such paths must stay at positions $-2,-1,0,1,2$ at every time. The following entries give the numbers of paths at these positions after each step; a path leaving this range is not counted: $$ \begin{array}{c|ccccc|c} \text{steps}&-2&-1&0&1&2&\text{total}\\ 0&0&0&1&0&0&1\\ 1&0&1&0&1&0&2\\ 2&1&0&2&0&1&4\\ 3&0&3&0&3&0&6\\ 4&3&0&6&0&3&12\\ 5&0&9&0&9&0&18\\ 6&9&0&18&0&9&36\\ 7&0&27&0&27&0&54\\ 8&27&0&54&0&27&108 \end{array} $$ Each row is obtained by sending the count at each position to its two neighboring positions and discarding moves outside $[-2,2]$. There are $2^8=256$ equally likely paths altogether, so the exact crossing probability is $(256-108)/256=148/256=37/64$. The comparison is valid because $37/64\le8/9$: cross-multiplication gives $37\cdot9=333\le512=8\cdot64$. The bound is not exact, but it controls all eight partial sums without enumerating their paths.

Worked Example: Unequal Variances and a Sharp Crossing Count

Let $X_1,X_2,X_3$ be independent, with $X_1$ taking the values $1,-1$ equally likely, $X_2$ taking $1/2,-1/2$ equally likely, and $X_3$ taking $1/3,-1/3$ equally likely. Use $\lambda=3/2$ and compare the bound with the exact probability.

Each variable has mean zero. Their second moments are, respectively, $1^2=1$, $(1/2)^2=1/4$, and $(1/3)^2=1/9$, so the total is $$ 1+\frac14+\frac19=\frac{36+9+4}{36}=\frac{49}{36}. $$ Kolmogorov’s inequality gives $$ \mathbb{P}\!\left(\max_{1\le k\le3}|S_k|\ge\frac32\right) \le \frac{49/36}{(3/2)^2} =\frac{49}{36}\cdot\frac49 =\frac{49}{81}. $$ For the exact probability, $|S_1|=1<3/2$. At the second step, $S_2$ has absolute value $3/2$ when $X_1$ and $X_2$ have the same sign, which occurs with probability $1/2$. If their signs differ, then $|S_2|=1/2$; adding $X_3$, whose absolute value is $1/3$, gives $|S_3|\le1/2+1/3=5/6<3/2$. Thus the crossing probability is exactly $1/2$, and $1/2\le49/81$ because $81\le98$. This calculation also checks that a later increment can be considered without overlooking a crossing at an earlier time.

Worked Example: A Centered Variable with Unequal Outcomes

Let $X_1$ take the value $2$ with probability $1/3$ and $-1$ with probability $2/3$. Independently, let $X_2$ take the values $1,-1$ with probabilities $1/2,1/2$. Find the maximal bound and the exact probability at $\lambda=2$.

The first mean is $2(1/3)+(-1)(2/3)=0$, and its second moment is $2^2(1/3)+(-1)^2(2/3)=4/3+2/3=2$. The second mean is $1(1/2)+(-1)(1/2)=0$, and its second moment is $1$. Thus the bound is $$ \mathbb{P}\!\left(\max_{1\le k\le2}|S_k|\ge2\right) \le\frac{2+1}{2^2}=\frac34. $$ For the exact event, $S_1=2$ with probability $1/3$, so that outcome crosses immediately. When $X_1=-1$, which has probability $2/3$, a crossing at time two occurs exactly when $X_2=-1$, which has conditional probability $1/2$; then $S_2=-2$. If $X_1=-1$ and $X_2=1$, then $S_2=0$, so there is no crossing. Hence the exact probability is $1/3+(2/3)(1/2)=2/3$, which is at most $3/4$. The computation confirms the bound for a centered distribution that is not symmetric.

What the Assumptions Prevent

Independence cannot be dropped. Let $Z$ equal $1$ or $-1$, each with probability $1/2$, and set $X_1=X_2=X_3=Z$. These variables are centered and each has second moment $1$, but they are not independent. The partial sums are $Z,2Z,3Z$, so at threshold $\lambda=3$ the crossing probability is $1$. The expression on the right of the claimed inequality would be $(1+1+1)/3^2=1/3$, which is smaller than $1$. The independence step in the proof, which makes the cross term have expectation zero on each first-crossing event, is unavailable here.

Centering matters as well. The theorem does not apply to arbitrary independent variables with finite variances. For example, if $X_j=1$ surely for $j=1,2$, then at $\lambda=1$ the crossing probability is $1$, while the sum of the variances is $0$. These variables are not mean zero: their partial sums have a deterministic drift that the variance sum does not measure.

The theorem is a finite-horizon probability estimate; it does not assert that a crossing must or must not occur. If its right side exceeds $1$, the estimate remains true but gives no useful improvement on the elementary probability bound $1$. Its strength is that, when the total variance is small relative to $\lambda^2$, it controls the chance of a large excursion at any of the specified times using only the second moments.

Check Your Understanding

In each question, identify the hypotheses before applying the inequality.

For independent mean-zero variables with variances $2,3,5$, compute the maximal bound at threshold $\lambda=4$.
In the first-crossing proof, explain why the cross term involving $S_kT_k$ has expectation zero on $A_k$.
For the three-variable sequence in the second worked example, which partial sum first reaches absolute value $3/2$ on a crossing path?
Give a reason the bound may be uninformative even when all its hypotheses hold.
For the dependent sequence $X_1=X_2=X_3=Z$ above, compute the right-hand side at threshold $\lambda=2$ and compare it with the actual crossing probability.