Big O in probability notation

Definitions

Small o: convergence in probability

For a set of random variables X_n and corresponding set of constants a_n (both indexed by n, which need not be discrete), the notation

${\displaystyle X_n=o_p(a_n)}$

means that the set of values X_n/a_n converges to zero in probability as n approaches an appropriate limit. Equivalently, X_n = o_p(a_n) can be written as X_n/a_n = o_p(1), i.e.

${\displaystyle \underset{n\to \mathrm{\infty }}{lim}P\left[\left|\frac{X_n}{a_n}\right|\ge \epsilon \right]=0,}$

for every positive ε.

Big O: stochastic boundedness

The notation

${\displaystyle X_n=O_p(a_n)\text{ as }n\to \mathrm{\infty }}$

means that the set of values X_n/a_n is stochastically bounded. That is, for any ε > 0, there exists a finite M > 0 and a finite N > 0 such that

${\displaystyle P\left(|\frac{X_n}{a_n}|>M\right)<\epsilon ,\mathrm{\forall }n>N.}$

Comparison of the two definitions

The difference between the definitions is subtle. If one uses the definition of the limit, one gets:

• Big ${\displaystyle O_p(1)}$: ${\displaystyle \mathrm{\forall }\epsilon \mathrm{\exists }{N}_{\epsilon },{\delta }_{\epsilon }\text{ such that }P(|X_n|\ge {\delta }_{\epsilon })\le \epsilon \mathrm{\forall }n>N_{\epsilon }}$
• Small ${\displaystyle o_p(1)}$: ${\displaystyle \mathrm{\forall }\epsilon ,\delta \mathrm{\exists }{N}_{\epsilon ,\delta }\text{ such that }P(|X_n|\ge \delta )\le \epsilon \mathrm{\forall }n>N_{\epsilon ,\delta }}$

The difference lies in the ${\displaystyle \delta }$: for stochastic boundedness, it suffices that there exists one (arbitrary large) ${\displaystyle \delta }$ to satisfy the inequality, and ${\displaystyle \delta }$ is allowed to be dependent on ${\displaystyle \epsilon }$ (hence the ${\displaystyle {\delta }_{\epsilon }}$). On the other hand, for convergence, the statement has to hold not only for one, but for any (arbitrary small) ${\displaystyle \delta }$. In a sense, this means that the sequence must be bounded, with a bound that gets smaller as the sample size increases.

This suggests that if a sequence is ${\displaystyle o_p(1)}$, then it is ${\displaystyle O_p(1)}$, i.e. convergence in probability implies stochastic boundedness. But the reverse does not hold.