The Subsequence Criterion for Convergence in Probability

Why a Subsequence Criterion Is Useful

Convergence in probability describes the size of an error at each index: for any fixed tolerance, the probability of exceeding it eventually becomes small. Almost-sure convergence makes a stronger, path-by-path statement: outside a single probability-zero set, the errors eventually become arbitrarily small. The two notions are not equivalent for a whole sequence, but a useful bridge between them is that convergence in probability can always be found almost surely along a suitably chosen further subsequence.

The key point is the quantifier over subsequences. Convergence in probability holds exactly when no subsequence can avoid having a further subsequence that converges almost surely to the same limit. The forward direction selects indices with increasingly small error probabilities. The reverse direction argues that if convergence in probability fails, one can find a subsequence whose errors stay too likely, preventing any further subsequence from converging almost surely.

Definitions and the Criterion

Definition: Let $X_n$ and $X$ be real-valued random variables on the same probability space. The sequence $X_n$ converges in probability to $X$, written $X_n\xrightarrow{p}X$, if for every $\varepsilon>0$, $$ P(|X_n-X|>\varepsilon)\longrightarrow 0. $$ A sequence $Y_k$ converges almost surely to $X$, written $Y_k\xrightarrow{a.s.}X$, if $P(\{\omega:Y_k(\omega)\to X(\omega)\})=1$.

A subsequence is indexed by strictly increasing indices $n_1<n_2<\cdots$. A further subsequence of it has the form $X_{n_{j_1}},X_{n_{j_2}},\ldots$, where $j_1<j_2<\cdots$. The limit $X$ in the criterion is the same random variable throughout; it is not allowed to change with the subsequence.

Theorem (Subsequence criterion for convergence in probability): Suppose $X_n$ and $X$ are real-valued random variables on a common probability space. Then $X_n\xrightarrow{p}X$ if and only if every subsequence of $(X_n)$ has a further subsequence that converges almost surely to $X$.

Both directions matter. It is not enough that one particular subsequence has an almost-surely convergent further subsequence. The criterion requires this property for every subsequence.

Proof of the Forward Direction

Assume $X_n\xrightarrow{p}X$, and begin with any subsequence $(X_{n_j})$. Convergence in probability is inherited by subsequences: for each fixed $\varepsilon>0$, the probabilities $P(|X_{n_j}-X|>\varepsilon)$ are terms from a sequence tending to zero, so they also tend to zero as $j\to\infty$.

We choose a further subsequence recursively. At step $k$, use convergence in probability with tolerance $1/k$. Since the corresponding error probabilities tend to zero, we can choose $j_k>j_{k-1}$ sufficiently large that $$ P(|X_{n_{j_k}}-X|>1/k)\leq 2^{-k}. $$ For the first step, choose any $j_1$ sufficiently large to meet the same bound. This constructs increasing indices and makes the error bounds summable.

Let $A_k=\{|X_{n_{j_k}}-X|>1/k\}$. For any integer $m\geq1$, countable subadditivity gives $$ P\left(\bigcup_{k\geq m}A_k\right) \leq \sum_{k\geq m}P(A_k) \leq \sum_{k\geq m}2^{-k} =2^{1-m}. $$ The event that $A_k$ occurs infinitely often is $\bigcap_{m\geq1}\bigcup_{k\geq m}A_k$, so its probability is at most $2^{1-m}$ for every $m$. Letting $m\to\infty$ shows that this event has probability zero. Thus, with probability one, there is an index after which none of the events $A_k$ occurs. On that probability-one event, eventually $$ |X_{n_{j_k}}-X|\leq 1/k, $$ and $1/k\to0$. Hence $X_{n_{j_k}}\xrightarrow{a.s.}X$, as required. $\square$

Proof of the Converse

We first record why almost-sure convergence implies convergence in probability. Suppose $Y_k\xrightarrow{a.s.}X$, and fix $\varepsilon>0$. Define $$ E_m=\bigcup_{k\geq m}\{|Y_k-X|>\varepsilon\}. $$ The events $E_m$ decrease as $m$ increases. Their intersection is the event that the error exceeds $\varepsilon$ infinitely often, which has probability zero because $Y_k\to X$ almost surely. By continuity of probability for decreasing events, $P(E_m)\to0$. For every $k\geq m$, $\{|Y_k-X|>\varepsilon\}\subseteq E_m$, and therefore $$ P(|Y_k-X|>\varepsilon)\leq P(E_m). $$ Given any positive bound, choose $m$ so that $P(E_m)$ is below that bound; the inequality then holds for all $k\geq m$. This proves $Y_k\xrightarrow{p}X$.

Now suppose every subsequence of $(X_n)$ has a further subsequence converging almost surely to $X$, but $X_n$ does not converge in probability to $X$. By the definition, there must be some $\varepsilon_0>0$ for which $$ P(|X_n-X|>\varepsilon_0)\not\longrightarrow0. $$ These probabilities are nonnegative, so their limsup is positive. Consequently, there is a $\delta>0$ and a subsequence $(X_{n_j})$ such that $$ P(|X_{n_j}-X|>\varepsilon_0)\geq\delta \quad\text{for every }j. $$ By the assumed subsequence property, this subsequence has a further subsequence converging almost surely to $X$. The result just proved implies that this further subsequence converges in probability to $X$. But each of its terms still has probability at least $\delta$ of an error greater than $\varepsilon_0$, contradicting convergence in probability. The contradiction proves $X_n\xrightarrow{p}X$. $\square$

Worked Applications

Worked Example: A Deterministic Sequence

Let $X_n=1/n$ and $X=0$ on any probability space. For each $\varepsilon>0$, choose an integer $N>1/\varepsilon$. For $n\geq N$, $1/n<\varepsilon$, so $$ P(|X_n-X|>\varepsilon)=P(1/n>\varepsilon)=0. $$ Thus $X_n\xrightarrow{p}0$.

To see the subsequence property directly, take any subsequence $(X_{n_j})$. Its indices increase, so $n_j\to\infty$, and hence $1/n_j\to0$. Every value here is deterministic, so the convergence holds on every outcome and is therefore almost sure. The whole subsequence works; no further selection is needed.

Worked Example: Rare-Event Indicators

Suppose $A_n$ are events on a common probability space with $P(A_n)=1/n$, and let $X_n=\mathbf{1}_{A_n}$ and $X=0$. For $0<\varepsilon<1$, the indicator takes only the values zero and one, so $$ \{|X_n|>\varepsilon\}=A_n, \qquad P(|X_n|>\varepsilon)=1/n\longrightarrow0. $$ For $\varepsilon\geq1$, the event $\{|X_n|>\varepsilon\}$ is empty, because neither possible value of $|X_n|$ is strictly greater than $\varepsilon$. Its probability is therefore zero. These cases establish $X_n\xrightarrow{p}0$.

Now start with an arbitrary subsequence $(X_{n_j})$. Since $n_j\to\infty$, choose increasing positions $j_k$ with $n_{j_k}\geq2^k$. Then $P(A_{n_{j_k}})\leq2^{-k}$. For each $m$, $$ P\left(\bigcup_{k\geq m}A_{n_{j_k}}\right) \leq\sum_{k\geq m}2^{-k} =2^{1-m}\longrightarrow0. $$ Thus the probability that $A_{n_{j_k}}$ occurs infinitely often is zero. Almost surely, the indicators $\mathbf{1}_{A_{n_{j_k}}}$ are eventually zero, so this further subsequence converges almost surely to zero.

Worked Example: Detecting Failure with an Oscillating Sequence

Let $X_n=(-1)^n$ and take $X=0$. For $\varepsilon=1/2$, every term has $|X_n-X|=1$, so $$ P(|X_n-X|>1/2)=1 $$ for every $n$. Therefore $X_n$ does not converge in probability to zero.

The subsequence criterion detects the failure as well. Consider the odd-indexed subsequence $X_{2j-1}=-1$. Every further subsequence of it is still constantly $-1$, so none converges almost surely to zero. Thus this one subsequence violates the required “every subsequence” condition.

What the Criterion Does and Does Not Say

The forward proof explains how the two modes of convergence fit together. At each selected index, the allowed error tolerance shrinks to zero, while the probability of exceeding that tolerance is made small enough that the total of the selected error probabilities is finite. A tail-union bound then ensures that only finitely many selected errors occur, outside a null event.

The converse has a different structure. If convergence in probability fails, there is one fixed tolerance for which errors remain bounded away from zero along some subsequence. No further subsequence can converge in probability at that tolerance. Since almost-sure convergence implies convergence in probability, no such further subsequence can converge almost surely either.

Mistake: proving the property for just one subsequence. The theorem says every subsequence must contain a suitable further subsequence. One successful choice does not rule out a different subsequence that fails the condition.
Mistake: using a fixed tolerance in the forward selection. A fixed tolerance only controls errors at one scale. The construction uses tolerances $1/k$ so that the selected errors themselves tend to zero.
Mistake: assuming the entire sequence converges almost surely. The forward direction guarantees a further subsequence for each chosen subsequence, not almost-sure convergence of the original sequence.
Mistake: overlooking strict inequalities. In the indicator example, the event is $A_n$ for $0<\varepsilon<1$, not at $\varepsilon=1$. At and above one, the strict-threshold event is empty.

Key takeaway: Convergence in probability is exactly the condition that every subsequence contains a further subsequence converging almost surely to the same limit. The forward proof selects summably small error probabilities; the reverse proof finds a subsequence whose errors stay too likely.

Check Your Understanding

For each question, identify the quantifiers and the error event before attempting a proof.

In the forward direction, why must the selected tolerance depend on $k$, and why is $1/k$ a useful choice?
Suppose $P(A_k)\leq 3^{-k}$. Use a tail-union bound to show that $A_k$ occurs only finitely often with probability one.
Why does almost-sure convergence of a further subsequence contradict a fixed lower bound $\delta>0$ on its error probabilities at some fixed tolerance?
For $X_n=\mathbf{1}_{A_n}$, what is $P(|X_n|>1)$? Explain why the strict inequality matters.
How does the odd-indexed subsequence of $X_n=(-1)^n$ show failure of the subsequence criterion for convergence to zero?