= Hoeffding inequality
{c}
{title2=$\mathbb P(S_n\geq t)\leq e^{-2t^2/V}$}
{wiki=Hoeffding's_inequality}
= Hoeffding's inequality
{c}
{synonym}
The <Hoeffding inequality> turns finite <interval> bounds and <independence> into exponentially small <tail probabilities> for a <sum>. It requires neither a <normal distribution> nor identical <probability distributions>. Let $X_1,\ldots,X_n$ be <independent> <essentially bounded> real <random variables>, with deterministic finite bounds $a_i\leq X_i\leq b_i$ <almost surely>. Define the centered <sum> and its squared-width budget by
$$
S_n=\sum_{i=1}^n(X_i-\mathbb EX_i),\qquad V=\sum_{i=1}^n(b_i-a_i)^2.
$$
For $V>0$ and $t>0$,
$$
\boxed{\mathbb P(S_n\geq t)\leq e^{-2t^2/V},\qquad \mathbb P(S_n\leq-t)\leq e^{-2t^2/V}.}
$$
The <union bound> therefore gives $\mathbb P(|S_n|\geq t)\leq\min\{1,2e^{-2t^2/V}\}$. If $V=0$, every $X_i$ is constant <almost surely>, so $S_n=0$ and both positive-threshold <tail probabilities> vanish. The equal-width version is stated in the authored Stanford notes.<CS229 Supplemental Lecture notes/Hoeffding’s inequality>[§3, p. 6, theorem 4: independent bounded variables and both tails]{ref}
The quantity $V$ is a sum of squared <interval> widths, \b[not the <variance> of $S_n$]. Centering changes the endpoints to $a_i-\mathbb EX_i$ and $b_i-\mathbb EX_i$, leaving each width unchanged. For example, <independent> <random variables> in $[-2,1]$ and $[4,5]$ have $V=3^2+1^2=10$, whatever their <expected values> or <probability distributions>. A deviation at least three above their total <expected value> has <probability> at most $e^{-18/10}\approx0.165299$. If all widths equal $b-a>0$, the <sample mean> $\overline X_n=n^{-1}\sum_iX_i$ satisfies
$$
\mathbb P\left(|\overline X_n-\mathbb E\overline X_n|\geq\varepsilon\right)\leq\min\{1,2\exp(-2n\varepsilon^2/(b-a)^2)\},\qquad\varepsilon>0.
$$
<Independence> is essential to this general guarantee. Take one <Bernoulli random variable> $B$ with success <probability> $1/2$ and set every $X_i=B$. Each lies in $[0,1]$, but for every $n$ the <sample mean> is either zero or one. Thus $\mathbb P(|\overline X_n-1/2|\geq1/4)=1$, whereas incorrectly inserting these dependent observations into the formula would give $2e^{-n/8}$, less than one for $n\geq6$. Some special dependent models have their own valid <concentration inequalities>; arbitrary <statistical dependence> cannot be ignored.
For the short proof, apply <Markov's inequality> to $e^{\lambda S_n}$ with $\lambda>0$, factor the <expectation> using <independence>, and apply the <Hoeffding lemma> to each factor:
$$
\mathbb P(S_n\geq t)\leq e^{-\lambda t}\prod_i\mathbb E e^{\lambda(X_i-\mathbb EX_i)}\leq\exp(-\lambda t+\lambda^2V/8).
$$
Minimizing this <quadratic polynomial> at $\lambda=4t/V$ gives the upper <tail probability>; applying it to $-S_n$ gives the lower one. This is the <Chernoff bound> method. The original 1963 article is <Probability Inequalities for Sums of Bounded Random Variables by Wassily Hoeffding>; its publisher record identifies the article, but its full text was unavailable during this source check. The argument above is a direct derivation rather than a claim to have inspected that article's proof.
Back to article page
