Kolmogorov's Maximal Inequality for Partial Sums

Why Control a Maximum of Partial Sums?

A bound for one partial sum answers whether $S_k$ is likely to be large at a specified time $k$. In many arguments, the concern is broader: could any partial sum become large during the sequence? Checking each time separately and adding the resulting probability bounds can be wasteful. Kolmogorov’s maximal inequality gives a direct bound for the chance of a threshold crossing anywhere in a finite sequence.

The result is especially useful when the increments are independent, have mean zero, and have finite variances. It does not require identical distributions. The proof uses the first time the partial sums reach the threshold; after that time, independence makes the expected contribution of the remaining increments vanish.

Setup and Statement

Definition: Let $X_1,\ldots,X_n$ be independent random variables with $E[X_j]=0$ and $\operatorname{Var}(X_j)<\infty$ for every $j$. Define the partial sums $$ S_0=0,\qquad S_k=\sum_{j=1}^{k}X_j,\quad 1\leq k\leq n. $$ The maximum absolute partial sum is $\max_{1\leq k\leq n}|S_k|$.

Theorem (Kolmogorov’s maximal inequality): Under the conditions above, for every $\lambda>0$, $$ P\!\left(\max_{1\leq k\leq n}|S_k|\geq \lambda\right) \leq \frac{\sum_{j=1}^{n}\operatorname{Var}(X_j)}{\lambda^2}. $$

The numerator is the variance of the final sum $S_n$. The bound is informative when the accumulated variance is small relative to $\lambda^2$; if the right-hand side exceeds 1, it remains a valid bound but gives no improvement over the basic probability bound of 1. The inequality controls an event involving every partial sum, not just the final sum.

Proof by the First Crossing

For each $k$, let $A_k$ be the event that $S_k$ is the first partial sum whose absolute value is at least $\lambda$: $$ A_k=\{|S_1|<\lambda,\ldots,|S_{k-1}|<\lambda,\ |S_k|\geq\lambda\}. $$ For $k=1$, the conditions before the comma are absent. Each $A_k$ is determined by $X_1,\ldots,X_k$. The events are disjoint, and their union is exactly the event that the maximum reaches or exceeds $\lambda$.

Write the remaining sum after time $k$ as $R_k=\sum_{j=k+1}^{n}X_j$, with $R_n=0$. Then $S_n=S_k+R_k$. Independence implies that $R_k$ is independent of $X_1,\ldots,X_k$, and hence of $A_k$ and $S_k$. Also $E[R_k]=0$. Expanding the square gives $$ E[S_n^2\mathbf{1}_{A_k}] =E[S_k^2\mathbf{1}_{A_k}] +2E[S_k\mathbf{1}_{A_k}R_k] +E[R_k^2\mathbf{1}_{A_k}]. $$ Here $\mathbf{1}_{A_k}$ is the indicator of $A_k$. The middle term is zero: independence and the zero mean of $R_k$ give $$ E[S_k\mathbf{1}_{A_k}R_k] =E[S_k\mathbf{1}_{A_k}]E[R_k]=0. $$ The last term is nonnegative. On $A_k$, $S_k^2\geq\lambda^2$, so $$ E[S_n^2\mathbf{1}_{A_k}]\geq E[S_k^2\mathbf{1}_{A_k}] \geq \lambda^2P(A_k). $$ Summing over the disjoint events, and using nonnegativity of $S_n^2$, yields $$ \lambda^2\sum_{k=1}^{n}P(A_k) \leq \sum_{k=1}^{n}E[S_n^2\mathbf{1}_{A_k}] =E\!\left[S_n^2\mathbf{1}_{\cup_{k=1}^{n}A_k}\right] \leq E[S_n^2]. $$ Finally, the variables are independent and centered, so for $i\ne j$, $E[X_iX_j]=E[X_i]E[X_j]=0$. Consequently, $$ E[S_n^2]=\sum_{j=1}^{n}E[X_j^2] =\sum_{j=1}^{n}\operatorname{Var}(X_j). $$ Substituting this identity and $\sum_k P(A_k)=P(\cup_k A_k)$ proves the inequality. $\square$

Worked Applications

Worked Example: A Symmetric Random Walk

Let $X_1,\ldots,X_8$ be independent, with $P(X_j=1)=P(X_j=-1)=1/2$ for every $j$. Find an upper bound for the probability that at least one of the first eight partial sums has absolute value at least 5.

Each increment is centered, since $E[X_j]=(1)(1/2)+(-1)(1/2)=0$. Also $E[X_j^2]=1$, so $\operatorname{Var}(X_j)=1$, and the total variance is $8$. With $\lambda=5$, Kolmogorov’s inequality gives $$ P\!\left(\max_{1\leq k\leq 8}|S_k|\geq 5\right) \leq \frac{8}{5^2} =\frac{8}{25} =0.32. $$ Thus the probability of a crossing at any time from 1 through 8 is at most $0.32$. This is a bound, not a claim that the crossing probability equals $0.32$.

Worked Example: Unequal Variances

Suppose $X_1,X_2,X_3$ are independent with $X_1\sim N(0,1)$, $X_2\sim N(0,4)$, and $X_3\sim N(0,9)$. Bound the probability that any of $S_1,S_2,S_3$ has absolute value at least 6.

The stated normal distributions have mean zero and variances $1,4,9$, respectively. The total variance is $1+4+9=14$. Therefore $$ P\!\left(\max_{1\leq k\leq 3}|S_k|\geq 6\right) \leq \frac{14}{6^2} =\frac{14}{36} =\frac{7}{18} \approx 0.389. $$ The result applies even though the variances are different: the bound uses their sum, not a common variance. No independence among the partial sums $S_1,S_2,S_3$ is required; the theorem’s independence assumption is on the increments $X_1,X_2,X_3$.

Worked Example: Bounding Deviations Over a Tail Block

Let $X_j$, $101\leq j\leq150$, be independent, with $P(X_j=1/j)=P(X_j=-1/j)=1/2$. Bound the probability that a partial sum starting at index 101 reaches absolute value at least $0.5$: $$ P\!\left(\max_{101\leq k\leq150}\left|\sum_{j=101}^{k}X_j\right|\geq 0.5\right). $$

Each $X_j$ has mean zero and variance $1/j^2$. Apply the inequality to the 50 increments $X_{101},\ldots,X_{150}$, whose partial sums are exactly the sums in the event. Then $$ P\!\left(\max_{101\leq k\leq150}\left|\sum_{j=101}^{k}X_j\right|\geq 0.5\right) \leq \frac{\sum_{j=101}^{150}1/j^2}{(0.5)^2}. $$ Since $x\mapsto x^{-2}$ is decreasing on $(0,\infty)$, $$ \sum_{j=101}^{150}\frac{1}{j^2} \leq \int_{100}^{150}\frac{1}{x^2}\,dx =\frac{1}{100}-\frac{1}{150} =\frac{1}{300}. $$ It follows that the probability is at most $(1/300)/(1/4)=1/75$, approximately $0.0133$. The comparison bounds the entire block’s crossing probability, not merely the probability at its final index.

A Useful Consequence for Centered Sample Sums

For independent, identically distributed variables $Y_1,\ldots,Y_n$ with $E[Y_j]=\mu$ and $\operatorname{Var}(Y_j)=\sigma^2<\infty$, set $X_j=Y_j-\mu$. The centered variables are independent, have mean zero, and each has variance $\sigma^2$. For any fixed $\varepsilon>0$, the event $\max_{k\leq n}|\sum_{j=1}^k(Y_j-\mu)|/n\geq\varepsilon$ is exactly the event $\max_{k\leq n}|S_k|\geq n\varepsilon$. Thus $$ P\!\left(\max_{1\leq k\leq n} \left|\frac{1}{n}\sum_{j=1}^{k}(Y_j-\mu)\right|\geq\varepsilon\right) \leq \frac{n\sigma^2}{n^2\varepsilon^2} =\frac{\sigma^2}{n\varepsilon^2}. $$ The denominator here is the fixed $n$, even for partial sums ending before $n$. This is a simultaneous bound at one fixed scale; it is not a bound on the maximum of the differently normalized averages $k^{-1}\sum_{j=1}^k(Y_j-\mu)$.

Why the Assumptions Matter

The proof depends on two distinct features. First, finite variances ensure that $E[S_n^2]$ exists and equals the sum of the increment variances. Second, independence of future increments from the first-crossing event, together with their zero mean, makes the cross term vanish. Without that step, a future increment could systematically reinforce or cancel the sum at the crossing time, and the proof would not give the stated bound.

Centering is also essential to the displayed form. If the increments have nonzero means, applying the theorem directly to their partial sums is not justified. When means exist, one can instead center each increment and apply the inequality to $X_j-E[X_j]$; that controls deviations around the accumulated means, not around zero.

Common Mistake

Incorrect reasoning: Apply a one-time variance bound to each $S_k$, then report the resulting bound as if it automatically controls $\max_{k\leq n}|S_k|$. A statement about $P(|S_n|\geq\lambda)$ concerns only the final sum and says nothing by itself about an earlier crossing.

Correction: The maximal event is a union across times. Kolmogorov’s proof handles that union by dividing it into disjoint first-crossing events $A_k$. Independence and centering then let the final squared sum pay for each crossing event, giving a single bound with the total variance in the numerator.

Key takeaway: For independent, mean-zero increments with finite variances, the probability that any partial sum reaches magnitude $\lambda$ is at most total variance divided by $\lambda^2$. The first-crossing decomposition is what turns a bound for a final squared sum into control over the whole path of partial sums.

Check Your Understanding

Use the assumptions and proof strategy above to answer these questions.

For independent centered increments with variances $2,3,5$, what bound does the inequality give for $P(\max_{k\leq3}|S_k|\geq 5)$?
In the proof, why are the first-crossing events $A_1,\ldots,A_n$ disjoint?
Which term in the expansion of $E[S_n^2\mathbf{1}_{A_k}]$ vanishes, and what assumptions make it vanish?
If the increments are independent but have nonzero means, can the inequality be applied directly to their uncentered partial sums? Explain.
Why does a bound for $P(|S_n|\geq\lambda)$ alone not establish a bound for $P(\max_{k\leq n}|S_k|\geq\lambda)$?