Big O in probability notation

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 \lim _{n\to \infty }P\left[\left|{\frac {X_{n}}{a_{n}}}\right|\geq \varepsilon \right]=0,}$

for every positive ε.^[2]

The notation

${\displaystyle X_{n}=O_{p}(a_{n}){\text{ as }}n\to \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)<\varepsilon ,\;\forall \;n>N.}$

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

• Big ${\displaystyle O_{p}(1)}$: ${\displaystyle \forall \varepsilon \quad \exists N_{\varepsilon },\delta _{\varepsilon }\quad {\text{ such that }}P(|X_{n}|\geq \delta _{\varepsilon })\leq \varepsilon \quad \forall n>N_{\varepsilon }}$
• Small ${\displaystyle o_{p}(1)}$: ${\displaystyle \forall \varepsilon ,\delta \quad \exists N_{\varepsilon ,\delta }\quad {\text{ such that }}P(|X_{n}|\geq \delta )\leq \varepsilon \quad \forall n>N_{\varepsilon ,\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 \varepsilon }$ (hence the ${\displaystyle \delta _{\varepsilon }}$). 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.

If ${\displaystyle (X_{n})}$ is a stochastic sequence such that each element has finite variance, then

${\displaystyle X_{n}-E(X_{n})=O_{p}\left({\sqrt {\operatorname {var} (X_{n})}}\right)}$

(see Theorem 14.4-1 in Bishop et al.)

If, moreover, ${\displaystyle a_{n}^{-2}\operatorname {var} (X_{n})=\operatorname {var} (a_{n}^{-1}X_{n})}$ is a null sequence for a sequence ${\displaystyle (a_{n})}$ of real numbers, then ${\displaystyle a_{n}^{-1}(X_{n}-E(X_{n}))}$ converges to zero in probability by Chebyshev's inequality, so

${\displaystyle X_{n}-E(X_{n})=o_{p}(a_{n}).}$