Big O in probability notation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The order in probability notation is used in probability theory and statistical theory in direct parallel to the big-O notation that is standard in mathematics. Where the big-O notation deals with the convergence of sequences or sets of ordinary numbers, the order in probability notation deals with convergence of sets of random variables, where convergence is in the sense of convergence in probability.[1]

Definitions[edit]

Small O: convergence in probability[edit]

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

X_n=o_p(a_n) \,

means that the set of values Xn/an converges to zero in probability as n approaches an appropriate limit. Equivalently, Xn = op(an) can be written as Xn/an = op(1), where Xn = op(1) is defined as,

\lim_{n \to \infty} P(|X_n| \geq \varepsilon) = 0,

for every positive ε.[2]

Big O: stochastic boundedness[edit]

The notation,

X_n=O_p(a_n), \,

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

P(|X_n/a_n| > M) < \varepsilon,\ \forall n.


Comparison of the two definitions[edit]

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

  • Big Op(1): \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 op(1): \forall \varepsilon, \delta \quad \exists N_{\varepsilon} \quad  \text{ such that } P(|X_n| \geq \delta) \leq \varepsilon \quad \forall n> N_{\varepsilon}

The difference lies in the δ: for stochastic boundedness, it suffices that there exists one (arbitrary large) δ to satisfy the inequality, and δ is allowed to be dependent on ε (hence the δε). On the other side, for convergence, the statement has to hold not only for one, but for any (arbitrary small) δ. 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 op(1), then it is Op(1), i.e. convergence in probability implies stochastic boundedness. But the reverse does not hold.

Example[edit]

If (X_n) is a stochastic sequence such that each element has finite variance, then

X_n - E(X_n) = O_p(\sqrt{\operatorname{var}(X_n)}) \,

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

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

X_n - E(X_n) = o_p(a_n).

References[edit]

  1. ^ Dodge, Y. (2003) The Oxford Dictionary of Statistical Terms, OUP. ISBN 0-19-920613-9
  2. ^ Yvonne M. Bishop, Stephen E. Fienberg, Paul W. Holland. (1975,2007) Discrete multivariate analysis, Springer. ISBN 0-387-72805-8, ISBN 978-0-387-72805-6