Namespaces
Variants
Actions

Difference between revisions of "Probability of large deviations"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (MR/ZBL numbers added)
m (tex encoded by computer)
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
<!--
 +
p0749401.png
 +
$#A+1 = 22 n = 0
 +
$#C+1 = 22 : ~/encyclopedia/old_files/data/P074/P.0704940 Probability of large deviations
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 +
{{DEF}}
 +
 +
{{MSC|60F10}}
 +
 +
[[Category:Limit theorems]]
 +
 
A probability of the type
 
A probability of the type
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749401.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} ( S _ {n} - b _ {n} > a _ {n} ),\ \
 +
{\mathsf P} ( S _ {n} - b _ {n} < - a _ {n} ) \ \
 +
\textrm{ or } \  {\mathsf P} (| S _ {n} - b _ {n} | > a _ {n} ),
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749402.png" /></td> </tr></table>
+
$$
 +
S _ {n}  = \sum _ { j= } 1 ^ { n }  X _ {j} ,
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749403.png" /> is a sequence of independent random variables, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749404.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749405.png" /> are two numerical sequences such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749406.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749407.png" /> in probability.
+
$  \{ X _ {j} \} $
 +
is a sequence of independent random variables, and $  \{ a _ {n} \} $
 +
and $  \{ b _ {n} \} $
 +
are two numerical sequences such that $  a _ {n} > 0 $,  
 +
and $  ( S _ {n} - b _ {n} ) / a _ {n} \rightarrow 0 $
 +
in probability.
  
If the random variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749408.png" /> have the same distribution with mathematical expectation zero and finite variance <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p0749409.png" />, one may write <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494010.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494012.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494013.png" />. Cramér's theorem and strengthened versions of it are particularly important in this connection (cf. [[Cramér theorem|Cramér theorem]]).
+
If the random variables $  X _ {1} , X _ {2} \dots $
 +
have the same distribution with mathematical expectation zero and finite variance $  \sigma  ^ {2} $,  
 +
one may write $  b _ {n} = 0 $
 +
and $  a _ {n} = x _ {n} \sigma \sqrt n $,  
 +
where $  x _ {n} \rightarrow + \infty $
 +
as $  n \rightarrow \infty $.  
 +
Cramér's theorem and strengthened versions of it are particularly important in this connection (cf. [[Cramér theorem|Cramér theorem]]).
  
To obtain guaranteed bounds for the probability of large deviations one uses inequalities of the type of the [[Chebyshev inequality in probability theory|Chebyshev inequality in probability theory]]; these provide the so-called exponential bounds for the probability of large deviations. For instance, if the random variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494014.png" /> are independent, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494017.png" /> with probability one, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494019.png" />, then the estimate
+
To obtain guaranteed bounds for the probability of large deviations one uses inequalities of the type of the [[Chebyshev inequality in probability theory|Chebyshev inequality in probability theory]]; these provide the so-called exponential bounds for the probability of large deviations. For instance, if the random variables $  X _ {j} $
 +
are independent, $  {\mathsf E} {X _ {j} } = 0 $,  
 +
$  {\mathsf E} {X _ {j}  ^ {2} } = \sigma _ {j}  ^ {2} $,  
 +
$  | X _ {j} | \leq  L $
 +
with probability one, $  B _ {n}  ^ {2} = \sigma _ {1}  ^ {2} + \dots + \sigma _ {n}  ^ {2} $
 +
and $  a = xL/B _ {n} $,  
 +
then the estimate
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494020.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ | S _ {n} | > x B _ {n} \}  \leq  \
 +
2  \mathop{\rm exp} \left \{ -
 +
\frac{x  ^ {2} }{2}
 +
\left ( 1+
 +
\frac{a}{3}
 +
\right )  ^ {-} 1 \right \} ,
 +
$$
  
the right-hand side of which decreases exponentially with increasing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494021.png" />, is valid for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p074/p074940/p07494022.png" />.
+
the right-hand side of which decreases exponentially with increasing $  x $,  
 +
is valid for all $  x \geq  0 $.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top"> M. Loève, "Probability theory" , Springer (1977) {{MR|0651017}} {{MR|0651018}} {{ZBL|0359.60001}} </TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian) {{MR|0388499}} {{ZBL|0322.60043}} {{ZBL|0322.60042}} </TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> I.A. Ibragimov, Yu.V. Linnik, "Independent and stationary sequences of random variables" , Wolters-Noordhoff (1971) (Translated from Russian) {{MR|0322926}} {{ZBL|0219.60027}} </TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> Yu.V. Prokhorov, "Multidimensional distributions: inequalities and limit theorems" ''J. Soviet Math.'' , '''2''' : 5 (1976) pp. 475–488 ''Itogi Nauk. i Tekhn.'' , '''10''' (1972) pp. 5–24</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> V.V. Yurinskii, "Exponential bounds for large deviations" ''Theory Probab. Appl.'' , '''19''' : 1 (1974) pp. 154–159 ''Teor. Veroyatnost. i Primenen.'' , '''19''' : 1 (1974) pp. 152–153</TD></TR></table>
+
{|
 
+
|valign="top"|{{Ref|L}}|| M. Loève, "Probability theory" , Springer (1977) {{MR|0651017}} {{MR|0651018}} {{ZBL|0359.60001}}
 
+
|-
 +
|valign="top"|{{Ref|Pe}}|| V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian) {{MR|0388499}} {{ZBL|0322.60043}} {{ZBL|0322.60042}}
 +
|-
 +
|valign="top"|{{Ref|IL}}|| I.A. Ibragimov, Yu.V. Linnik, "Independent and stationary sequences of random variables" , Wolters-Noordhoff (1971) (Translated from Russian) {{MR|0322926}} {{ZBL|0219.60027}}
 +
|-
 +
|valign="top"|{{Ref|Pr}}|| Yu.V. Prokhorov, "Multidimensional distributions: inequalities and limit theorems" ''J. Soviet Math.'' , '''2''' : 5 (1976) pp. 475–488 ''Itogi Nauk. i Tekhn.'' , '''10''' (1972) pp. 5–24
 +
|-
 +
|valign="top"|{{Ref|Y}}|| V.V. Yurinskii, "Exponential bounds for large deviations" ''Theory Probab. Appl.'' , '''19''' : 1 (1974) pp. 154–159 ''Teor. Veroyatnost. i Primenen.'' , '''19''' : 1 (1974) pp. 152–153
 +
|}
  
 
====Comments====
 
====Comments====
There are substantial new developments which link the rate of exponential decay to entropy. These developments find widespread use in statistical physics and in statistics. Cf. [[Limit theorems|Limit theorems]] and [[#References|[a1]]], [[#References|[a2]]].
+
There are substantial new developments which link the rate of exponential decay to entropy. These developments find widespread use in statistical physics and in statistics. Cf. [[Limit theorems|Limit theorems]] and {{Cite|E}}, {{Cite|S}}.
  
A second recent development concerns the development of limit theorems and large deviation theory for stochastic processes instead of sums of independent random variables, cf. [[#References|[a3]]].
+
A second recent development concerns the development of limit theorems and large deviation theory for stochastic processes instead of sums of independent random variables, cf. {{Cite|W}}.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> R.S. Ellis, "Entropy, large deviations, and statistical mechanics" , Springer (1985) {{MR|0793553}} {{ZBL|0566.60097}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> D.W. Stroock, "An introduction to the theory of large deviations" , Springer (1984) {{MR|0755154}} {{MR|0758258}} {{ZBL|0552.60022}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> A.D. [A.D. Ventsel'] Wentzell, "Limit theorems on large deviations for Markov stochastic processes" , Kluwer (1990) (Translated from Russian) {{MR|1135113}} {{ZBL|0743.60029}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> H. Cramér, "Sur un nouveau théorème-limite de la théorie des probabilités" , ''Act. Sci. et Ind.'' , '''736''' , Hermann (1938) pp. 5–24 {{MR|}} {{ZBL|64.0529.01}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> P. Groeneboom, J. Oosterhoff, F.H. Ruymgaart, "Large deviation theorems for empirical probability measures" ''Ann. Probl.'' , '''7''' (1979) pp. 553–586 {{MR|0537208}} {{ZBL|0425.60021}} </TD></TR></table>
+
{|
 +
|valign="top"|{{Ref|E}}|| R.S. Ellis, "Entropy, large deviations, and statistical mechanics" , Springer (1985) {{MR|0793553}} {{ZBL|0566.60097}}
 +
|-
 +
|valign="top"|{{Ref|S}}|| D.W. Stroock, "An introduction to the theory of large deviations" , Springer (1984) {{MR|0755154}} {{MR|0758258}} {{ZBL|0552.60022}}
 +
|-
 +
|valign="top"|{{Ref|W}}|| A.D. Wentzell, "Limit theorems on large deviations for Markov stochastic processes" , Kluwer (1990) (Translated from Russian) {{MR|1135113}} {{ZBL|0743.60029}}
 +
|-
 +
|valign="top"|{{Ref|C}}|| H. Cramér, "Sur un nouveau théorème-limite de la théorie des probabilités" , ''Act. Sci. et Ind.'' , '''736''' , Hermann (1938) pp. 5–24 {{MR|}} {{ZBL|64.0529.01}}
 +
|-
 +
|valign="top"|{{Ref|GOR}}|| P. Groeneboom, J. Oosterhoff, F.H. Ruymgaart, "Large deviation theorems for empirical probability measures" ''Ann. Probl.'' , '''7''' (1979) pp. 553–586 {{MR|0537208}} {{ZBL|0425.60021}}
 +
|}

Revision as of 08:07, 6 June 2020


This page is deficient and requires revision. Please see Talk:Probability of large deviations for further comments.

2020 Mathematics Subject Classification: Primary: 60F10 [MSN][ZBL]

A probability of the type

$$ {\mathsf P} ( S _ {n} - b _ {n} > a _ {n} ),\ \ {\mathsf P} ( S _ {n} - b _ {n} < - a _ {n} ) \ \ \textrm{ or } \ {\mathsf P} (| S _ {n} - b _ {n} | > a _ {n} ), $$

where

$$ S _ {n} = \sum _ { j= } 1 ^ { n } X _ {j} , $$

$ \{ X _ {j} \} $ is a sequence of independent random variables, and $ \{ a _ {n} \} $ and $ \{ b _ {n} \} $ are two numerical sequences such that $ a _ {n} > 0 $, and $ ( S _ {n} - b _ {n} ) / a _ {n} \rightarrow 0 $ in probability.

If the random variables $ X _ {1} , X _ {2} \dots $ have the same distribution with mathematical expectation zero and finite variance $ \sigma ^ {2} $, one may write $ b _ {n} = 0 $ and $ a _ {n} = x _ {n} \sigma \sqrt n $, where $ x _ {n} \rightarrow + \infty $ as $ n \rightarrow \infty $. Cramér's theorem and strengthened versions of it are particularly important in this connection (cf. Cramér theorem).

To obtain guaranteed bounds for the probability of large deviations one uses inequalities of the type of the Chebyshev inequality in probability theory; these provide the so-called exponential bounds for the probability of large deviations. For instance, if the random variables $ X _ {j} $ are independent, $ {\mathsf E} {X _ {j} } = 0 $, $ {\mathsf E} {X _ {j} ^ {2} } = \sigma _ {j} ^ {2} $, $ | X _ {j} | \leq L $ with probability one, $ B _ {n} ^ {2} = \sigma _ {1} ^ {2} + \dots + \sigma _ {n} ^ {2} $ and $ a = xL/B _ {n} $, then the estimate

$$ {\mathsf P} \{ | S _ {n} | > x B _ {n} \} \leq \ 2 \mathop{\rm exp} \left \{ - \frac{x ^ {2} }{2} \left ( 1+ \frac{a}{3} \right ) ^ {-} 1 \right \} , $$

the right-hand side of which decreases exponentially with increasing $ x $, is valid for all $ x \geq 0 $.

References

[L] M. Loève, "Probability theory" , Springer (1977) MR0651017 MR0651018 Zbl 0359.60001
[Pe] V.V. Petrov, "Sums of independent random variables" , Springer (1975) (Translated from Russian) MR0388499 Zbl 0322.60043 Zbl 0322.60042
[IL] I.A. Ibragimov, Yu.V. Linnik, "Independent and stationary sequences of random variables" , Wolters-Noordhoff (1971) (Translated from Russian) MR0322926 Zbl 0219.60027
[Pr] Yu.V. Prokhorov, "Multidimensional distributions: inequalities and limit theorems" J. Soviet Math. , 2 : 5 (1976) pp. 475–488 Itogi Nauk. i Tekhn. , 10 (1972) pp. 5–24
[Y] V.V. Yurinskii, "Exponential bounds for large deviations" Theory Probab. Appl. , 19 : 1 (1974) pp. 154–159 Teor. Veroyatnost. i Primenen. , 19 : 1 (1974) pp. 152–153

Comments

There are substantial new developments which link the rate of exponential decay to entropy. These developments find widespread use in statistical physics and in statistics. Cf. Limit theorems and [E], [S].

A second recent development concerns the development of limit theorems and large deviation theory for stochastic processes instead of sums of independent random variables, cf. [W].

References

[E] R.S. Ellis, "Entropy, large deviations, and statistical mechanics" , Springer (1985) MR0793553 Zbl 0566.60097
[S] D.W. Stroock, "An introduction to the theory of large deviations" , Springer (1984) MR0755154 MR0758258 Zbl 0552.60022
[W] A.D. Wentzell, "Limit theorems on large deviations for Markov stochastic processes" , Kluwer (1990) (Translated from Russian) MR1135113 Zbl 0743.60029
[C] H. Cramér, "Sur un nouveau théorème-limite de la théorie des probabilités" , Act. Sci. et Ind. , 736 , Hermann (1938) pp. 5–24 Zbl 64.0529.01
[GOR] P. Groeneboom, J. Oosterhoff, F.H. Ruymgaart, "Large deviation theorems for empirical probability measures" Ann. Probl. , 7 (1979) pp. 553–586 MR0537208 Zbl 0425.60021
How to Cite This Entry:
Probability of large deviations. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Probability_of_large_deviations&oldid=23648
This article was adapted from an original article by V.V. PetrovV.V. Yurinskii (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article