Small o: convergence in probability edit

For a set of random variables X_n and a 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]

Big O: stochastic boundedness edit

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.}$ 

Comparison of the two definitions edit

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}).}$