Find a concept
Start typing to search the mathematical index.
Upper bound on deviation probability using variance.
Chebyshev's inequality: Let be a random variable with expectation and finite variance . Then for every ,
Equivalently, for every ,
Here denotes the probability measure on the underlying probability space. Chebyshev's inequality is a direct consequence of Markov's inequality applied to , and it is a standard tool for proving the weak law of large numbers.
A random variable is a measurable function defined on a probability space , meaning that for every Borel set one has .
A random variable induces a distribution (law) on the real numbers via , and quantities such as expectation and variance are defined from this law.
An expectation of a random variable is the number
provided is integrable, i.e. (so is an random variable; see L1 function).
A variance of a random variable is the quantity
defined when (so in particular the expectation is finite).
A probability measure is a function defined on a sigma-algebra of subsets of a set such that , for every pairwise disjoint sequence , and .
A probability measure is a special case of a measure and is the key ingredient in a probability space; it assigns probabilities to events (measurable sets).
A probability space is a triple where is a set, is a sigma-algebra on , and is a probability measure on .
Elements of are the events whose probabilities are evaluated by , and a random variable is a measurable function defined on .
Markov inequality: If is a nonnegative random variable and , then
This is a basic tool for bounding event probabilities using expectation. It directly implies the Chebyshev inequality (by applying it to ) and is also a starting point for exponential tail bounds such as the Chernoff bound.
Weak law of large numbers: Let be an iid sequence of random variables with expectation and finite variance . Define the sample mean
Then for every ,
This is a convergence-in-probability statement on the underlying probability space. A standard proof uses Chebyshev's inequality applied to , and the result is weaker than the strong law of large numbers, which upgrades the mode of convergence.