Kolmogorov's 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.