Tails and concentration

Toss a fair coin 1,000 times and count the heads. Ask for the chance that at least three quarters of the tosses come up heads, which means 750 heads or more. Each toss is worth one unit and carries variance one quarter, so 1,000 independent tosses carry variance 250, and Chebyshev turns that into an upper bound of 0.004: 250 divided by the squared gap of 250 is 0.004 [S:19:20]. A sharper argument, which uses only the fact that each toss is bounded, gives a bound of $5.2\times 10^{-55}$.

Those two numbers answer the section question with a rule instead of a picture. A tail is the probability that a random variable lands far from its centre. A concentration inequality bounds that probability using a few facts about the variable rather than its whole distribution [S:19:16]. The bell curve of the last section described a shape. A concentration inequality asks how much probability can sit far out, and it answers without drawing anything. !Both panels bound the chance that at least three quarters of the tosses come up heads, and the vertical scales are not the same. Chebyshev's 4/n loses a factor of ten for every tenfold increase in n, a shallow slope. Hoeffding's e to the minus n over 8 falls off a cliff: at 1,000 tosses it is 5.2 × 10⁻⁵⁵ against Chebyshev's 0.004, a gap of 52 orders of magnitude. The dashed guide marks that pair. Status: synthetic.

The first rule is Chebyshev's inequality, and it needs only a mean and a variance. It says that the chance of landing at least a gap t from the mean is at most the variance divided by the square of that gap [S:19:16]. For 1,000 tosses the variance of the count is 250, the gap from the mean of 500 to the target of 750 is 250, and the bound is 250 divided by 62,500.

That sentence says the bound shrinks like one over the number of tosses, so the limit it sets improves slowly and linearly as the experiment grows.

Chebyshev is honest and weak at the same time, and the source says so plainly: it is very general but often too weak [S:19:20]. It knows the variance and nothing else, so it cannot distinguish a coin from a distribution with the same variance and a much longer tail. Weakness of this kind is not a defect of the proof. It is the price of assuming almost nothing.

The second rule uses a different fact. Hoeffding's inequality assumes that each observation is bounded, meaning it has a floor and a ceiling, and that the observations are independent [S:19:23]. Bounded values make the arithmetic of the tail exponential rather than linear, and the exponential is much stronger than the linear bound that Chebyshev supplies [S:19:22].

That display is the coin case of Hoeffding's bound [S:19:24]. Read e as a fixed number slightly below three; the point is that the exponent carries the whole sample size. So at a thousand tosses the chance is astronomically small rather than merely small.

Worked example. The two bounds are easy to compare once you tabulate them.

Check the middle row by hand. Four divided by 1,000 is 0.004, and e raised to minus 125 is $5.2\times 10^{-55}$, a number whose first nonzero digit sits 55 places after the decimal point. Both numbers bound the same event, and the second bound is smaller by a factor of about $10^{52}$.

The pattern in the table is the lesson. Every row has an honest bound, and the rows differ in how fast the bound falls. Chebyshev divides its bound by ten at every tenfold increase in n. Hoeffding multiplies its bound by $e^{-9n/8}$ for the same step, so the factor depends on where you start: from 100 to 1,000 it is $e^{-112.5}\approx 1.4\times 10^{-49}$, and from 1,000 to 10,000 it is $e^{-1125}\approx 2.6\times 10^{-489}$. There is no single factor; the exponent itself grows tenfold.

Both rules cost something: Chebyshev's bound can exceed one, in which case it says nothing at all. It is also loose for every distribution that does not put its mass near the two ends of its range, which is how a distribution becomes as spread out as its variance allows [S:19:20]. Hoeffding needs independent, bounded observations, and its exponential promise evaporates when one observation can dominate the sum [S:55:114]. A heavy-tailed distribution, one whose extreme values stay far more likely than an exponential allows, puts non-trivial probability on events that an exponential bound calls impossible [S:55:114]. That is exactly the case where the tidy bounds stop being a description of your data.

The formal statement. Markov's inequality says that a non-negative variable exceeds a positive gap with probability at most its mean divided by that gap [S:19:16]. Chebyshev applies Markov to the squared deviation and bounds the chance of landing at least a gap from the mean by σ² divided by the square of the gap [S:19:16]. Hoeffding assumes independent variables, each confined between a lower and an upper endpoint. It bounds the chance that the sum of the centred variables exceeds a gap by an exponential of minus two times the square of the gap, divided by the sum of the squared interval widths [S:19:25].

The derivation. Chebyshev is Markov applied to the square. The event that the distance from the mean exceeds a gap is the event that the squared distance exceeds the square of the gap, and the mean of the squared distance is the variance [S:19:16]. Hoeffding is a Chernoff argument. Multiply the sum by a positive number, exponentiate both sides, and apply Markov to the exponential. The bound becomes an exponential of minus the gap times that number, multiplied by the moment generating function of the sum [S:19:23]. Independence factorises that function into n factors, and Hoeffding's lemma bounds each factor [S:33:27]. The step omitted is the lemma itself, which is one line of calculus on a bounded variable.

The worked comparison. For n fair coin tosses the count lies in an interval of width one, so the sum of the squared widths is n. A gap of a quarter of n gives an exponent of minus n divided by eight, which is the bound in the core. Chebyshev gives four divided by n. Both are honest, and the exponential falls faster at every n.

The edge case. Chebyshev returns a number that can exceed one. If the gap is smaller than the standard deviation, the bound says only what you already knew, and a bound above one is vacuous. Hoeffding fails in a different way: it needs a finite interval. One unbounded observation breaks the hypothesis, and a heavy-tailed distribution puts non-trivial probability on events that an exponential bound calls impossible [S:55:114].

What the core hid. Both bounds are upper bounds, and neither is an estimate. At a thousand tosses the true probability is far below the Chebyshev bound, and the distance between the two columns of the table is not a gain in accuracy but a gain in the strength of the guarantee. The comparison is between promises, not between measurements.

Where the analogy breaks. The core contrasts a shape with a bound, but a normal tail is itself exponential. What stops the central limit theorem from supplying the bound is its own approximation error, not the shape of the bell [S:19:22]. The contrast is about what can be proved, not about what is true.

Original sources. Chebyshev's inequality is Corollary 1.2.5 in Vershynin, derived from Markov's inequality [S:19:16], and the notes record that both are due to Chebyshev [S:19:19]. Hoeffding's inequality appears as Theorem 2.2.2 for symmetric Bernoulli variables and as Theorem 2.2.6 for general bounded variables [S:19:25]. The lemma behind it carries Hoeffding's name and the year 1963 in Rigollet's notes [S:33:27].

An open question. The inequalities hold for every sample size, and their constants are chosen for generality rather than sharpness. No single bound is sharp across all bounded distributions at a fixed n. Evidence that would settle a case: compute the exact tail for a family of small-support distributions and compare it with each bound at the same n, reporting the ratio rather than the two numbers separately. A bound that is ten times too large changes no decision, while one that is ten times too small changes every decision. Until that comparison is made, a bound tells you an event is unlikely and does not tell you how unlikely.

A frontier result. The upper confidence bound algorithm in bandits turns this arithmetic into a decision rule. It places a confidence bound above each estimated reward, built directly from Hoeffding's inequality, and plays the arm with the highest bound [S:59:254]. The width of that bonus is a Hoeffding bound, so the inequality you just met sets the exploration rate: a tighter bound means fewer pulls spent on arms that are probably worse.

What to read next. Read chapter 2 of Vershynin for the three inequalities and the sub-Gaussian class [S:19:20], then section 1.2 of Rigollet for Hoeffding's lemma [S:33:27]. Read the bandit chapter of Hardt and Recht for the confidence-bound algorithm [S:59:254]. For the case where the interval assumption fails, read the median-of-means section of Vershynin's second edition, which recovers a Gaussian tail from a finite variance alone [S:20:41].