Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

BigO in probability notation

From Wikipedia, the free encyclopedia

Theorder in probability notation is used inprobability theory andstatistical theory in direct parallel to thebigO notation that is standard inmathematics. Where the bigO notation deals with the convergence of sequences or sets of ordinary numbers, the order in probability notation deals withconvergence of sets of random variables, where convergence is in the sense ofconvergence in probability.[1]

Definitions

[edit]

Smallo: convergence in probability

[edit]

For a set of random variablesXn and corresponding set of constantsan (both indexed byn, which need not be discrete), the notation

Xn=op(an){\displaystyle X_{n}=o_{p}(a_{n})}

means that the set of valuesXn/an converges to zero in probability asn approaches an appropriate limit.Equivalently,Xn = op(an) can be written asXn/an = op(1),i.e.

limn→∞P[|Xnan|≥ε]=0,{\displaystyle \lim _{n\to \infty }P\left[\left|{\frac {X_{n}}{a_{n}}}\right|\geq \varepsilon \right]=0,}

for every positive ε.[2]

BigO: stochastic boundedness

[edit]

The notation

Xn=Op(an) as n→∞{\displaystyle X_{n}=O_{p}(a_{n}){\text{ as }}n\to \infty }

means that the set of valuesXn/an is stochastically bounded. That is, for anyε > 0, there exists a finiteM > 0 and a finiteN > 0 such that

P(|Xnan|>M)<ε,∀n>N.{\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:

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 isop(1){\displaystyle o_{p}(1)}, then it isOp(1){\displaystyle O_{p}(1)}, i.e. convergence in probability implies stochastic boundedness. But the reverse does not hold.

Chebyshev lemma for stochastic order

[edit]

Chebyshev lemma for stochastic order ([3])—If(Xn){\displaystyle (X_{n})} is a stochastic sequence such that each element has finite varianceσn2{\displaystyle \sigma _{n}^{2}}, then

Xn−μn=Op(σn){\displaystyle X_{n}-\mu _{n}=O_{p}\left(\sigma _{n}\right)}, whereμn=E(Xn){\displaystyle \mu _{n}=E(X_{n})}.
Proof

Let's introduce another definition for convenience.Xn=Op(1){\displaystyle X_{n}=O_{p}(1)} if for everyη>0{\displaystyle \eta >0} there exist a constantK(η){\displaystyle K(\eta )} and integern(η){\displaystyle n(\eta )} such that ifn≥n(η){\displaystyle n\geq n(\eta )} then

P(|Xn|≤K(η))≥1−η{\displaystyle P\left(\left|X_{n}\right|\leq K(\eta )\right)\geq 1-\eta }.

Chebyshev's inequality states:

P(|X−μ|≤hσ)≥1−h−2{\displaystyle P\left(\left|X-\mu \right|\leq h\sigma \right)\geq 1-h^{-2}}, whereh>0{\displaystyle h>0}.

If we set thereh=η−1/2{\displaystyle h=\eta ^{-1/2}} for any0<η<1{\displaystyle 0<\eta <1} then we have

P(|Xn−μn|σn<η−1/2)≥1−η{\displaystyle P\left({\frac {\left|X_{n}-\mu _{n}\right|}{\sigma _{n}}}<\eta ^{-1/2}\right)\geq 1-\eta },

which holds forn≥1{\displaystyle n\geq 1}. SettingK(η)=η−1/2{\displaystyle K(\eta )=\eta ^{-1/2}} we apply our definition and conclude that

Xn−μnσn=Op(1){\displaystyle {\frac {X_{n}-\mu _{n}}{\sigma _{n}}}=O_{p}(1)}.

If, moreover,an−2var⁡(Xn)=var⁡(an−1Xn){\displaystyle a_{n}^{-2}\operatorname {var} (X_{n})=\operatorname {var} (a_{n}^{-1}X_{n})} is a null sequence for a sequence(an){\displaystyle (a_{n})} of real numbers, thenan−1(Xn−E(Xn)){\displaystyle a_{n}^{-1}(X_{n}-E(X_{n}))} converges to zero in probability byChebyshev's inequality, so

Xn−E(Xn)=op(an).{\displaystyle 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
  3. ^Bishop, Yvonne M. M.; Fienberg, Stephen E.; Holland, Paul W. (2007).Discrete Multivariate Analysis: Theory and Practice. New York, NY: Springer. p. 476-477.ISBN 978-0-387-72805-6.LCCN 2007928365.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Big_O_in_probability_notation&oldid=1336716346"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp