Worked Problems in Calibrating Concentration Bounds

From a Tail Inequality to a Numerical Guarantee

A concentration inequality becomes useful in a design or analysis when it answers a concrete question: how large can a deviation probability be, or how many observations are needed to make that probability small? The calculation is not just substitution. One must match the inequality's assumptions to the model, use the correct scale parameter, and verify that the final bound actually meets the target.

This tutorial works through those calibrations for sample means and functions of independent inputs. The inequalities provide upper bounds, not exact probabilities. A bound above a chosen threshold does not prove that the true probability exceeds that threshold; it only fails to certify that the probability is below it.

Bounds and Calibration Formulas

Hoeffding inequality: If $X_1,\ldots,X_n$ are independent and $X_i\in[a_i,b_i]$ almost surely, then for $S_n=\sum_{i=1}^n(X_i-E[X_i])$ and every $t>0$, $$ P(|S_n|\ge t)\le 2\exp\left(-\frac{2t^2}{\sum_{i=1}^n(b_i-a_i)^2}\right). $$ For independent observations in a common interval of length $R$, the corresponding sample-mean bound is $P(|\bar X-E[\bar X]|\ge\varepsilon)\le 2\exp(-2n\varepsilon^2/R^2)$.

Bernstein inequality: Suppose $Z_1,\ldots,Z_n$ are independent, $E[Z_i]=0$, $|Z_i|\le M$ almost surely, and $\sum_i\operatorname{Var}(Z_i)\le V$. Then $$ P\left(\left|\sum_{i=1}^n Z_i\right|\ge t\right) \le 2\exp\left(-\frac{t^2}{2(V+Mt/3)}\right),\qquad t>0. $$ In the iid sample-mean setting, if $Z_i=X_i-E[X_i]$, $|Z_i|\le M$, and $\operatorname{Var}(X_i)=v$, this gives $P(|\bar X-E[X_1]|\ge\varepsilon)\le 2\exp\left(-n\varepsilon^2/[2(v+M\varepsilon/3)]\right)$.

Sub-Gaussian tail bound: A centered random variable $Z$ is sub-Gaussian with variance proxy $s^2$ if $E[e^{\lambda Z}]\le e^{\lambda^2s^2/2}$ for every real $\lambda$. For independent centered $Z_i$ with proxies $s_i^2$, $P(|\sum_i Z_i|\ge t)\le2\exp(-t^2/[2\sum_i s_i^2])$.

Bounded-difference inequality: Let $X_1,\ldots,X_n$ be independent, and let $g(X_1,\ldots,X_n)$ be measurable. Suppose changing coordinate $i$, while holding the others fixed, changes $g$ by at most $c_i$. Then for $t>0$, $$ P(|g-E[g]|\ge t)\le 2\exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). $$

For a generic bound of the form $2e^{-An}$, where $A>0$ is fixed by the deviation threshold and model, the requirement that the bound be at most $\delta$, with $0<\delta<1$, can be solved directly.

Calibration rule: The inequality $2e^{-An}\le\delta$ holds exactly when $$ n\ge\frac{\log(2/\delta)}{A}. $$ Thus the smallest integer sample size certified by this bound is $\left\lceil\log(2/\delta)/A\right\rceil$. This follows by taking logarithms: $An\ge\log(2/\delta)$. Since $A>0$, the exponential bound decreases as $n$ increases, so the ceiling is the first integer that meets the requirement.

Worked Comparisons for Sample Means

Worked Example: Hoeffding and Bernstein for Bernoulli Data

Let $X_1,\ldots,X_{100}$ be independent Bernoulli random variables with success probability $0.2$. Compare the two-sided bounds for a deviation of at least $0.1$ in the sample mean.

Each $X_i$ lies in $[0,1]$, so the range length is $1$. Hoeffding gives $$ P(|\bar X-0.2|\ge0.1)\le2\exp\left(-\frac{2(100)(0.1)^2}{1^2}\right) =2e^{-2}\approx0.2707. $$

For Bernstein, $Z_i=X_i-0.2$ has variance $v=0.2(0.8)=0.16$. Its possible values are $-0.2$ and $0.8$, so $|Z_i|\le M=0.8$. Substitution gives $$ P(|\bar X-0.2|\ge0.1) \le2\exp\left(-\frac{100(0.1)^2}{2(0.16+0.8(0.1)/3)}\right) =2\exp\left(-\frac{1}{0.373333\ldots}\right) \approx0.1373. $$

Both are valid upper bounds, but Bernstein's is smaller here because it uses the variance $0.16$, as well as the bound on centered observations. The result does not say the true deviation probability is $0.1373$; it says that it is no greater than this value. In this model Hoeffding uses only the range, so it does not benefit from the comparatively small variance.

Worked Example: Minimum Sample Size from Hoeffding

Suppose independent observations lie in an interval of length $1$. Find the smallest $n$ for which Hoeffding certifies $P(|\bar X-E[\bar X]|\ge1/8)\le0.01$.

The bound is $$ 2\exp\left(-\frac{2n(1/8)^2}{1^2}\right) =2\exp(-n/32). $$ To make it at most $0.01$, solve $2e^{-n/32}\le0.01$. Taking logarithms gives $$ n\ge32\log(200)\approx169.546. $$ The smallest integer that satisfies this inequality is $n=170$. Checking the two integers at the threshold, $$ 2e^{-169/32}=2e^{-5.28125}\approx0.01017>0.01, \qquad 2e^{-170/32}=2e^{-5.3125}\approx0.00986<0.01. $$ Thus 170 is the minimum sample size certified by this bound. This conclusion concerns the Hoeffding guarantee, not necessarily the minimum sample size for the actual model's tail probability.

Worked Example: Sample Size from a Sub-Gaussian Proxy

Let $X_1,\ldots,X_n$ be independent Rademacher variables: each equals $1$ or $-1$ with probability $1/2$. Find the sample size required for the sub-Gaussian bound to certify $P(|\bar X|\ge0.25)\le0.05$.

The variables are centered and have variance proxy $1$: their moment generating function is $E[e^{\lambda X_i}]=\cosh(\lambda)\le e^{\lambda^2/2}$. Independence therefore gives a proxy $n$ for the sum, and hence $$ P(|\bar X|\ge0.25)\le2\exp\left(-\frac{n(0.25)^2}{2}\right) =2e^{-n/32}. $$ The calibration rule yields $$ n\ge32\log(40)\approx118.044. $$ Therefore the smallest certified integer is $n=119$. For verification, at $n=118$ the exponent is $118/32=3.6875$, giving a bound of about $0.05007$, which is above $0.05$; at $n=119$ it is $119/32=3.71875$, giving about $0.0485$, below $0.05$. The proxy-based inequality is valid for every threshold, although it need not be the sharpest possible bound for this particular discrete distribution.

Calibrating a Bounded-Difference Bound

For a statistic that depends on many independent inputs, a direct range for the statistic may be unhelpful. The bounded-difference inequality instead uses the effect of changing each input separately. The sum $\sum_i c_i^2$, not the number of possible values of the statistic, determines the exponent.

Worked Example: Concentration of an Occupancy Count

Place $30$ independent balls into $10$ boxes, with each ball assigned uniformly to a box. Let $G$ be the number of occupied boxes. Compute a bounded-difference guarantee for a deviation of at least $8$ from $E[G]$.

Changing the destination of one ball can change the occupied-box count by at most $1$: a box may become empty and another may become occupied, but the net change is no larger than $1$ in absolute value. Thus $c_i=1$ for all 30 coordinates and $\sum_i c_i^2=30$. The expectation is the sum of the probabilities that each box is occupied: $$ E[G]=10\left(1-\left(\frac{9}{10}\right)^{30}\right)\approx9.5761. $$ Applying bounded differences at $t=8$ gives $$ P(|G-E[G]|\ge8) \le2\exp\left(-\frac{2(8)^2}{30}\right) =2\exp(-128/30)\approx0.02806. $$ Consequently the probability is at most $0.02806$, and in particular is below $0.05$. The calculation uses the input sensitivities; it does not require $G$ itself to have a short interval of possible values.

Comparing Bounds and Checking the Claim

Calibration is also a way to compare the information each inequality uses. For iid observations in an interval of length $R$, Hoeffding has exponent $2n\varepsilon^2/R^2$. Bernstein has exponent $n\varepsilon^2/[2(v+M\varepsilon/3)]$. Which exponent is larger depends on the variance, the centered bound, the range, and the deviation size; there is no universal ranking independent of these inputs. The selection principles developed in choosing between Hoeffding, Bernstein, and Bennett help identify which assumptions are available, while the numerical comparison determines the resulting guarantee.

For a requested confidence level $\delta$, a useful check is to substitute the proposed integer sample size back into the original bound. When the exponent is linear in $n$, comparing the integer immediately below and the integer at the ceiling verifies minimality. For bounded differences, the calibration may instead be in a threshold $t$: if the desired upper bound is $\delta$, then $$ 2\exp\left(-\frac{2t^2}{\sum_i c_i^2}\right)\le\delta \quad\Longleftrightarrow\quad t\ge\sqrt{\frac{\sum_i c_i^2}{2}\log\left(\frac{2}{\delta}\right)}. $$ This is obtained by taking logarithms and then taking the nonnegative square root. It gives a deviation threshold guaranteed by the inequality, not a quantile of the exact distribution.

Common Mistake: Treating a Bound as an Exact Probability

A frequent error is to say that a probability “is” the value of a concentration bound. For example, the Bernoulli calculation above does not establish $P(|\bar X-0.2|\ge0.1)=0.1373$; it establishes only that this probability is no greater than $0.1373$. A second error is to stop at an integer that nearly meets the target. In the Hoeffding calculation, $n=169$ produces a bound of about $0.01017$, so it does not certify a target of $0.01$. Rounding the bound down or treating “approximately one percent” as equivalent to “at most one percent” changes the claim. Keep the unrounded threshold inequality for the decision, and use rounded decimals only to report the check.

Key takeaway: Identify the bound's assumptions and parameters, solve the inequality for the desired quantity, and verify the candidate numerically. Report the result as a guarantee from that bound, not as an exact tail probability.

Check Your Understanding

For each question, distinguish what the inequality guarantees from what is known about the exact distribution.

For $n$ independent variables in an interval of length $2$, write the Hoeffding bound for a sample-mean deviation of at least $\varepsilon$.
In the Bernoulli example, why does the Bernstein calculation use $M=0.8$, rather than $M=0.2$?
If a bound is $2e^{-0.04n}$, derive the smallest integer $n$ that makes it at most $0.01$.
A function of 12 independent inputs changes by at most $2$ when any one input is changed. What value of $\sum_i c_i^2$ enters its bounded-difference bound?
If a calculated upper bound is $0.06$ when the target is $0.05$, what can and cannot be concluded about the actual probability?