The order in probability notation is used in
probability theory
Probability theory or probability calculus is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expre ...
and
statistical theory
The theory of statistics provides a basis for the whole range of techniques, in both study design and data analysis, that are used within applications of statistics.
The theory covers approaches to statistical-decision problems and to statistica ...
in direct parallel to the
big ''O'' notation that is standard in
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
. 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
In probability theory, there exist several different notions of convergence of sequences of random variables, including ''convergence in probability'', ''convergence in distribution'', and ''almost sure convergence''. The different notions of conve ...
.
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
:
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.
:
for every positive ε.
[ Yvonne M. Bishop, Stephen E.Fienberg, Paul W. Holland. (1975, 2007) ''Discrete multivariate analysis'', Springer. , ]
Big ''O'': stochastic boundedness
The notation
:
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
:
Comparison of the two definitions
The difference between the definitions is subtle. If one uses the definition of the limit, one gets:
* Big
:
* Small
:
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 hand, 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
, then it is
, i.e. convergence in probability implies stochastic boundedness. But the reverse does not hold.
Example
If
is a stochastic sequence such that each element has finite variance, then
:
(see Theorem 14.4-1 in Bishop et al.)
If, moreover,
is a null sequence for a sequence
of real numbers, then
converges to zero in probability by
Chebyshev's inequality, so
:
References
{{DEFAULTSORT:Big O In Probability Notation
Mathematical notation
Probability theory
Statistical theory
Convergence (mathematics)