Stochastic Orders and Asymptotic Equivalence

Why Stochastic Orders Matter

A limit theorem often gives only part of the information needed for an approximation. For example, \(X_n\xrightarrow{d}X\) describes the limiting distribution of a sequence, but a derivation may also contain a remainder whose size must be compared with the scale of \(X_n\). Stochastic order notation gives a concise way to make that comparison: it distinguishes a term that stays bounded after rescaling from one that vanishes after rescaling.

The distinction is important when simplifying a statistic. If two sequences differ by an amount that is negligible on the scale relevant to the limit, then one can often replace one by the other. But “small” must be measured against a specified deterministic rate, and convergence in distribution alone does not mean convergence in probability.

Big-O and Little-o in Probability

Let \(a_n>0\) eventually be a deterministic sequence, and let \(X_n\) be real-valued random variables. The definitions below apply to \(X_n/a_n\); thus the rate \(a_n\) is part of the statement.

Definition: \(X_n=O_p(a_n)\) means that \(X_n/a_n\) is bounded in probability: for every \(\varepsilon>0\), there is a finite \(M\) such that \(\limsup_{n\to\infty}P(|X_n/a_n|>M)<\varepsilon\). The notation \(X_n=o_p(a_n)\) means \(X_n/a_n\xrightarrow{p}0\), or equivalently, for every \(\varepsilon>0\), \(P(|X_n/a_n|>\varepsilon)\to0\).

Informally, \(O_p(a_n)\) says that \(X_n\) is no larger than order \(a_n\), up to a random multiplier that remains bounded in probability. The stronger statement \(o_p(a_n)\) says that \(X_n\) is negligible relative to \(a_n\). In particular, \(o_p(a_n)\) implies \(O_p(a_n)\). If \(a_n\to0\), then \(O_p(a_n)\) also implies \(X_n\xrightarrow{p}0\); if \(a_n\) does not tend to zero, that conclusion need not hold.

The deterministic rate can make an order statement informative. Writing \(X_n=O_p(1)\) says that the sequence is bounded in probability, while \(X_n=O_p(n^{-1/2})\) says that the sequence is bounded in probability after multiplication by \(\sqrt n\). The latter does not, by itself, say that \(\sqrt n X_n\) converges to zero.

Distributional Order Notation and Tightness

The phrase bounded in distribution is often used for a sequence whose distributions form a tight family. Here, a sequence \(Z_n\) is tight if for every \(\varepsilon>0\), some finite \(M\) satisfies \(\limsup_n P(|Z_n|>M)<\varepsilon\). For real-valued sequences, tightness is exactly boundedness in probability. Some authors use \(O_d\) and \(o_d\) to emphasize distributional language; their meaning is given precisely here.

Definition: \(X_n=O_d(a_n)\) means that \(X_n/a_n\) is tight (equivalently, bounded in probability). \(X_n=o_d(a_n)\) means \(X_n/a_n\xrightarrow{d}0\). For real-valued random variables, \(o_d(a_n)\) and \(o_p(a_n)\) are equivalent. The \(O_d\) and \(O_p\) notations likewise express the same tightness condition.

To see why the little-o statements agree, convergence in distribution to the constant zero forces the probability of being outside any fixed neighborhood of zero to vanish. Conversely, convergence in probability to zero implies convergence in distribution to zero. This equivalence is special to a constant limit: convergence in distribution to a nonconstant random variable generally does not imply convergence in probability.

Worked Example: A Sample Mean’s Stochastic Rate

Let \(X_1,\ldots,X_n\) be independent Bernoulli random variables with common success probability \(p\), where \(0<p<1\), and let \(\bar X_n=n^{-1}\sum_{i=1}^n X_i\). Show that \(\bar X_n-p=O_p(n^{-1/2})\).

Since \(E[X_i]=p\) and \(\operatorname{Var}(X_i)=p(1-p)\), independence gives \(E[\bar X_n]=p\) and \(\operatorname{Var}(\bar X_n)=p(1-p)/n\). For every \(M>0\), Chebyshev’s inequality yields

P\!\left(\left|\frac{\bar X_n-p}{n^{-1/2}}\right|>M\right) =P\!\left(|\bar X_n-p|>\frac{M}{\sqrt n}\right) \leq \frac{p(1-p)/n}{M^2/n} =\frac{p(1-p)}{M^2}.

The bound does not depend on \(n\), and it tends to zero as \(M\to\infty\). Thus \(\sqrt n(\bar X_n-p)\) is bounded in probability, which proves \(\bar X_n-p=O_p(n^{-1/2})\). This argument does not prove \(\bar X_n-p=o_p(n^{-1/2})\); indeed, the central limit theorem gives a nondegenerate limiting distribution at that scale.

Rules for Combining Stochastic Orders

The basic algebra of stochastic orders follows from probability bounds. The following result is useful when a statistic is written as a leading term plus an error, or when products of random quantities appear.

Theorem: Suppose \(a_n,b_n>0\) eventually. If \(X_n=O_p(a_n)\) and \(Y_n=O_p(b_n)\), then \(X_n+Y_n=O_p(a_n+b_n)\) and \(X_nY_n=O_p(a_nb_n)\). If, in addition, \(X_n=o_p(a_n)\), then \(X_nY_n=o_p(a_nb_n)\) whenever \(Y_n=O_p(b_n)\).

Proof. Set \(U_n=X_n/a_n\) and \(V_n=Y_n/b_n\). By assumption, both sequences are bounded in probability. For the sum,

\frac{|X_n+Y_n|}{a_n+b_n} \leq \frac{a_n}{a_n+b_n}|U_n| +\frac{b_n}{a_n+b_n}|V_n| \leq |U_n|+|V_n|.

For any \(M>0\), if \(|U_n|+|V_n|>M\), then either \(|U_n|>M/2\) or \(|V_n|>M/2\). The union bound therefore gives

P(|U_n|+|V_n|>M) \leq P(|U_n|>M/2)+P(|V_n|>M/2).

Boundedness in probability of \(U_n\) and \(V_n\) makes the right-hand side arbitrarily small for sufficiently large \(M\), in the limit superior over \(n\). This proves the sum assertion.

For the product, \((X_nY_n)/(a_nb_n)=U_nV_n\). If \(|U_nV_n|>M^2\), at least one of \(|U_n|>M\) or \(|V_n|>M\) must hold. Hence

P(|U_nV_n|>M^2) \leq P(|U_n|>M)+P(|V_n|>M),

which proves that \(U_nV_n\) is bounded in probability. Finally, if \(U_n\xrightarrow{p}0\) and \(V_n\) is bounded in probability, then for any \(\varepsilon>0\) and \(M>0\),

P(|U_nV_n|>\varepsilon) \leq P(|V_n|>M)+P(|U_n|>\varepsilon/M).

First choose \(M\) so the limit superior of the first term is arbitrarily small; with that \(M\) fixed, the second term tends to zero. Thus \(U_nV_n\xrightarrow{p}0\), proving the little-o assertion. \(\square\)

Worked Example: Comparing Two Error Rates

Let \(Z_n\sim N(0,1)\) for each \(n\), and define \(A_n=Z_n/\sqrt n\) and \(B_n=(1+|Z_n|)/n\). Compare the two error sizes on the scale \(n^{-1/2}\).

For \(A_n\), \(A_n/n^{-1/2}=Z_n\), whose distribution is the same standard normal distribution for every \(n\). It is therefore tight, so \(A_n=O_p(n^{-1/2})\).

For \(B_n\),

\frac{B_n}{n^{-1/2}} =\frac{1+|Z_n|}{\sqrt n}.

The random variables \(1+|Z_n|\) have a common distribution and are tight. Multiplying a tight sequence by the deterministic sequence \(1/\sqrt n\to0\) gives convergence in probability to zero: for any \(\varepsilon>0\), choose \(M\) with \(P(1+|Z_n|>M)\) small, then for sufficiently large \(n\), \(M/\sqrt n<\varepsilon\). Thus \(B_n=o_p(n^{-1/2})\). Although both errors are \(O_p(n^{-1/2})\), only \(B_n\) is negligible at that scale.

Asymptotic Equivalence and Replacing a Sequence

There is no single universal symbol for “asymptotically equivalent”; the scale and meaning should be stated. The version most useful for distributional approximations is absolute-scale equivalence: sequences \(X_n\) and \(Y_n\) are equivalent at scale \(a_n\) when \(X_n-Y_n=o_p(a_n)\). At scale one, this says their difference converges in probability to zero. Relative equivalence, such as \(X_n/Y_n\xrightarrow{p}1\), is a different claim and requires a meaningful, nonzero denominator.

Theorem: Suppose \(a_n>0\), \(X_n-Y_n=o_p(a_n)\), and \(X_n/a_n\xrightarrow{d}X\), where \(X\) is a real-valued random variable. Then \(Y_n/a_n\xrightarrow{d}X\). Also, if \(X_n=O_p(a_n)\), then \(Y_n=O_p(a_n)\).

Proof. Write \(D_n=(Y_n-X_n)/a_n\). The equivalence assumption gives \(D_n\xrightarrow{p}0\). For the tightness assertion, \(Y_n/a_n=X_n/a_n+D_n\); the first term is tight because it converges in distribution, and the second is bounded in probability because it converges in probability to zero. The sum rule proved above then gives \(Y_n=O_p(a_n)\).

For the distributional assertion, let \(t\) be a continuity point of the distribution function \(F_X\). For any \(\delta>0\), the event \(\{Y_n/a_n\leq t\}\) is contained in the union of \(\{X_n/a_n\leq t+\delta\}\) and \(\{|D_n|>\delta\}\). Also, \(\{X_n/a_n\leq t-\delta\}\) is contained in the union of \(\{Y_n/a_n\leq t\}\) and \(\{|D_n|>\delta\}\). Consequently,

P(X_n/a_n\leq t-\delta)-P(|D_n|>\delta) \leq P(Y_n/a_n\leq t) \leq P(X_n/a_n\leq t+\delta)+P(|D_n|>\delta).

For fixed \(\delta\), take the limit inferior and limit superior as \(n\to\infty\). The error probabilities tend to zero, while the distribution functions for \(X_n/a_n\) converge at continuity points of \(F_X\). Choose positive \(\delta\) decreasing to zero for which \(t-\delta\) and \(t+\delta\) are continuity points; such choices exist because a distribution function has at most countably many discontinuities. Right and left continuity at the continuity point \(t\) then squeeze both bounds to \(F_X(t)\). Thus \(P(Y_n/a_n\leq t)\to F_X(t)\), proving \(Y_n/a_n\xrightarrow{d}X\). \(\square\)

Worked Example: A Negligible Perturbation Preserves a Normal Limit

Let \(X_1,X_2,\ldots\) be independent Bernoulli random variables with success probability \(1/2\). Define \(S_n=n^{-1/2}\sum_{i=1}^n(X_i-1/2)\) and \(T_n=S_n+n^{-1/4}\). Use the central limit theorem to find the limiting distribution of \(T_n\).

The summands have mean zero and variance \(1/4\), so the central limit theorem gives \(S_n\xrightarrow{d}N(0,1/4)\). The perturbation is deterministic and satisfies \(T_n-S_n=n^{-1/4}\to0\), hence \(T_n-S_n=o_p(1)\). Apply the replacement theorem with \(a_n=1\): it follows that \(T_n\xrightarrow{d}N(0,1/4)\). The perturbation vanishes at scale one, even though it is larger than \(n^{-1/2}\); the conclusion here concerns the unscaled sequences. A claim about the limit after multiplying by \(\sqrt n\) would require checking the remainder at that finer scale.

Common Mistake: Ignoring the Scale

A frequent error is to say that \(X_n-Y_n\to0\), and therefore the sequences are interchangeable in any limit calculation. The missing question is: after what rescaling? If the target limit concerns \(X_n/a_n\), the needed condition is \((X_n-Y_n)/a_n\xrightarrow{p}0\), not merely \(X_n-Y_n\xrightarrow{p}0\).

For instance, in the previous example \(T_n-S_n=n^{-1/4}\to0\), but \(\sqrt n(T_n-S_n)=n^{1/4}\to\infty\). Thus the two sequences are interchangeable at scale one, but not at scale \(n^{-1/2}\). Always compare the remainder to the scale of the statistic whose limit is being studied.

Key takeaway: \(O_p(a_n)\) means bounded after division by \(a_n\); \(o_p(a_n)\) means vanishing after division by \(a_n\). To replace one sequence by another in a distributional limit at scale \(a_n\), verify that their difference is \(o_p(a_n)\).

Check Your Understanding

Use the scale explicitly in each answer.

What does \(X_n=O_p(n^{-1/2})\) say about the sequence \(\sqrt n X_n\)?
If \(X_n=o_p(a_n)\) and \(Y_n=O_p(b_n)\), what order does the product \(X_nY_n\) have?
Why are \(o_p(a_n)\) and \(o_d(a_n)\) equivalent for real-valued random variables?
If \(X_n-Y_n=o_p(1)\), is that sufficient to replace \(X_n\) by \(Y_n\) in a limit for \(X_n/a_n\) when \(a_n\to0\)? What condition is needed?
Distinguish absolute-scale equivalence \(X_n-Y_n=o_p(a_n)\) from relative equivalence \(X_n/Y_n\xrightarrow{p}1\).