Kolmogorov's inequality

(Redirected from Kolmogorov inequality)

In probability theory, Kolmogorov's inequality is a so-called "maximal inequality" that gives a bound on the probability that the partial sums of a finite collection of independent random variables exceed some specified bound.

Statement of the inequality

edit

Let X1, ..., Xn : Ω → R be independent random variables defined on a common probability space (Ω, F, Pr), with expected value E[Xk] = 0 and variance Var[Xk] < +∞ for k = 1, ..., n. Then, for each λ > 0,

 

where Sk = X1 + ... + Xk.

The convenience of this result is that we can bound the worst case deviation of a random walk at any point of time using its value at the end of time interval.

Proof

edit

The following argument employs discrete martingales. As argued in the discussion of Doob's martingale inequality, the sequence   is a martingale. Define   as follows. Let  , and

 

for all  . Then   is also a martingale.

For any martingale   with  , we have that

 

Applying this result to the martingale  , we have

 

where the first inequality follows by Chebyshev's inequality.


This inequality was generalized by Hájek and Rényi in 1955.

See also

edit

References

edit
  • Billingsley, Patrick (1995). Probability and Measure. New York: John Wiley & Sons, Inc. ISBN 0-471-00710-2. (Theorem 22.4)
  • Feller, William (1968) [1950]. An Introduction to Probability Theory and its Applications, Vol 1 (Third ed.). New York: John Wiley & Sons, Inc. xviii+509. ISBN 0-471-25708-7.
  • Kahane, Jean-Pierre (1985) [1968]. Some random series of functions (Second ed.). Cambridge: Cambridge University Press. p. 29-30.


This article incorporates material from Kolmogorov's inequality on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.