Hoeffding inequality ($\mathbb{P}(S_n\ge t)\le e^{-2t^2/V}$)

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,\dots ,X_n$ be independent essentially bounded real random variables, with deterministic finite bounds $a_i\le X_i\le b_i$ almost surely. Define the centered sum and its squared-width budget byFor $V>0$ and $t>0$,The union bound therefore gives $\mathbb{P}(|S_n|\ge t)\le \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.^[ref]

The quantity $V$ is a sum of squared interval widths, not the variance of $S_n$. Centering changes the endpoints to $a_i-\mathbb{E}{X}_i$ and $b_i-\mathbb{E}{X}_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}\approx 0.165299$. If all widths equal $b-a>0$, the sample mean ${\overline{X}}_n=n^{-1}{\sum }_i{X}_i$ satisfies

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|\ge 1/4)=1$, whereas incorrectly inserting these dependent observations into the formula would give $2e^{-n/8}$, less than one for $n\ge 6$. 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: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.

Let $B_1,\dots ,B_n$ be independent and identically distributed Bernoulli random variables with success probability $p$, and let ${\hat{p}}_n=n^{-1}{\sum }_i{B}_i$ be their observed frequency, a sample mean. Since every interval width is one, $V=n$. Substituting $t=n\epsilon$ into the Hoeffding inequality givesFor tolerance $0<\epsilon <1$ and failure probability $0<\delta <1$, solving $2e^{-2n{\epsilon }^2}\le \delta$ yields the sufficient sample sizeHere $\log$ is the natural logarithm. For $\epsilon =0.05$ and $\delta =0.05$, $n=738$ guarantees an error smaller than $0.05$ with probability at least $0.95$, for every $p\in [0,1]$. The two-sided bound at this sample size is approximately $0.0499440$. A specified single direction instead needs $n\ge \lceil \log (1/\delta )/(2{\epsilon }^2)\rceil$, or $600$ for these choices. Halving the tolerance multiplies the unrounded sufficient sample size by four; reducing the failure probability tenfold adds $\log (10)/(2{\epsilon }^2)$ before rounding.

This is a conservative sufficient sample size, not a necessary minimum. For a specified $p$, the count $K={\sum }_i{B}_i$ has a binomial distribution, whose exact upper tail probability isFor $k>np$, the Hoeffding inequality bounds this by $\exp [-2(k-np{)}^2/n]$. An arbitrary frequency threshold uses $k=\lceil n(p+\epsilon )\rceil$; if $k>n$, the event is impossible. The discreteness of the count and its variance $np(1-p)$ can make the exact tail probability substantially smaller. At $n=100$, $p=1/2$, $k=60$, the exact upper tail probability is about $0.0284440$, while the bound is $e^{-2}\approx 0.135335$. At $p=1/10$, $k=20$, the same deviation $\epsilon =0.1$ gives the same bound but an exact upper tail probability about $0.00197856$.

For a fixed positive sample size $n$ of independent and identically distributed Bernoulli random variables, letThe Hoeffding inequality makes $C_n$ a conservative confidence interval for $p$: ${\mathbb{P}}_p(p\in C_n)\ge 1-\delta$ for every $p\in [0,1]$. Indeed, exclusion from the closed interval implies $|{\hat{p}}_n-p|>r_n$, an event contained in the deviation event bounded by $\delta$. Clipping to $[0,1]$ retains coverage because $p$ already lies there. For $n=738$, $\delta =0.05$, and an observed frequency $369/738=1/2$, $r_n\approx 0.0499924$, giving approximately $[0.450008,0.549992]$.

Coverage concerns repeated independent samples: the unknown $p$ is fixed and the confidence interval is random. This fixed-$n$ guarantee does not justify repeatedly checking the same bound and stopping as soon as it looks favorable. The Hoeffding sample size for Bernoulli frequencies chooses $n$ in advance; guarantees across repeated inspection times require separate control of the additional events, for example through a union bound with an allocated failure probability at each time.

The Hoeffding lemma controls the entire centered moment-generating function using only an interval width. For an essentially bounded real random variable $X$ with finite deterministic bounds $a\le X\le b$ almost surely, every real $\lambda$ satisfiesEquivalently, $\mathbb{E}{e}^{\lambda (X-\mathbb{E}X)}\le e^{{\lambda }^2(b-a{)}^2/8}$. This single-random variable statement needs no independence assumption; independence enters when applying it to the factors for a sum in the Hoeffding inequality. Both signs of $\lambda$ are allowed, and equality holds at $\lambda =0$ or when $a=b$.^[ref]

In the convention $\log \mathbb{E}{e}^{\lambda Y}\le {\lambda }^2{\sigma }^2/2$ for a centered sub-Gaussian random variable $Y$, the Hoeffding lemma supplies ${\sigma }^2=(b-a{)}^2/4$. This upper parameter need not equal the actual variance. For a Bernoulli random variable $B$ of success probability $p$,The actual variance is $p(1-p)$, whereas the supplied parameter is $1/4$ for every $p$. This explains part of the conservatism visible in Hoeffding sample size for Bernoulli frequencies.

A short proof exposes why the constant is $1/8$. Put $Y=X-\mathbb{E}X$ and define exponential tilting byThe tilted probability measure has the same interval of possible values, and differentiating the cumulant-generating function gives ${\psi }^{\prime \prime }(\lambda )={\mathrm{Var}}_{{\mathbb{P}}_{\lambda }}(Y)$. Boundedness justifies these derivatives for every finite $\lambda$. Under any such tilted law, Popoviciu's inequality on variances gives ${\psi }^{\prime \prime }(\lambda )\le (b-a{)}^2/4$: the variance is no larger than the expected value of the squared distance from the interval midpoint, itself at most $(b-a{)}^2/4$. Since $\psi (0)={\psi }^{\prime }(0)=0$, the integral form of Taylor's theorem yieldsThis expression handles either sign of $\lambda$ without changing the argument.

The constant $1/8$ cannot be reduced uniformly over all essentially bounded real random variables. Equal endpoint probabilities at $a$ and $b$ give $Y=\pm (b-a)/2$, a scaled Rademacher random variable, andThus the sharpness is already forced near zero by the variance; the bound need not be equality at nonzero parameters for a particular probability distribution.