Concentration inequality

A concentration inequality bounds the probability that a random quantity deviates substantially from a typical value, often using its mean, variance, or structural properties.

Markov's inequality: For a nonnegative random variable, Markov's inequality bounds the probability of exceeding a positive threshold using its expectation. It gives a basic tail bound from only nonnegativity and the mean.
Random variable: A random variable assigns a numerical value to each outcome of a random experiment. The quantity whose unusually large deviations an inequality bounds.
Law of large numbers: The law of large numbers states that sample averages converge toward their expected value as sample size grows. Concentration bounds give quantitative rates for this convergence.
Sub-Gaussian random variable: A sub-Gaussian random variable has tails bounded at least as rapidly as those of a Gaussian with comparable scale. Sub-Gaussian assumptions yield Gaussian-shaped concentration even without Gaussian distributions.
Chebyshev's inequality: Chebyshev's inequality bounds deviations from the mean using the variance. It strengthens the mean-only bound when variance is known.
Expected value: The expected value is the probability-weighted average of a random variable's possible values. Many inequalities measure departures from this central value.
Randomized algorithm: A randomized algorithm uses random choices during computation to produce an output. Tail bounds certify that random choices produce reliable outputs with high probability.
Sub-exponential random variable: A sub-exponential random variable has tails that decay exponentially beyond a characteristic scale. Its heavier tails often require weaker bounds than sub-Gaussian assumptions.
Chernoff bound: A Chernoff bound uses exponential moments to bound the tails of sums of random variables. Exponential moments often yield sharp bounds for sums of independent variables.
Variance: Variance is the expected squared deviation of a random variable from its mean. It quantifies spread and determines the scale in several classic bounds.

Linked from 7 pages