Hoeffding's inequality

Hoeffding's inequality bounds the probability that a sum of independent bounded random variables deviates from its expected value. Its exponential tail bound depends on the variables’ range widths, not their distributions.

Hoeffding's lemma: A bound on the moment-generating function of a bounded random variable centered at its mean. Applying this lemma to each summand yields Hoeffding's exponential bound.
Independent random variables: Random variables whose joint probabilities factor into the product of their individual probabilities. Independence lets the proof factor the sum’s moment-generating function.
Hoeffding's inequality for sample means: A tail bound for the difference between a sample average of independent bounded observations and its expectation. Rescaling the sum gives a direct confidence guarantee for an empirical average.
Bernstein's inequality: A concentration inequality that uses both variance and a bound on individual deviations. It can be tighter when the summands’ variance is much smaller than their ranges suggest.
Moment-generating function: A function that encodes a random variable’s moments and generates exponential tail bounds. The proof controls exponential moments of the centered sum.
Bounded random variable: A random variable whose possible values lie within a finite interval. The interval widths are the key inputs to the inequality.
Hoeffding's inequality for sampling without replacement: A concentration bound for sums drawn without replacement from a finite population. This extension handles finite-population sampling, where draws are dependent.
McDiarmid's inequality: A concentration inequality for functions of independent inputs with bounded changes under one-coordinate replacements. It applies to functions beyond sums by bounding sensitivity to each input.
Chernoff bound: A tail-bound method that applies Markov’s inequality to an exponential transform of a random variable. Hoeffding’s inequality is obtained by optimizing a Chernoff bound.
Expected value: The probability-weighted average value of a random variable. The inequality measures deviations from the sum’s expected value.

Linked from 7 pages