View source for Probability of large deviations

<!--
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

$$ 
{\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|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  $  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====
{|
|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====
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. {{Cite|W}}.

====References====
{|
|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}}
|}