SECTION 05 / 10

Hoeffding’s inequality

On this page 7 headings

Learning goal: Understand how sample size controls the error of a bounded average.

The displayed Hoeffding bound is one-sided.
For a two-sided deviation, apply it to both tails and add the bounds; this introduces a factor of 2.
The variables must be independent and bounded.

The ideaToss a fair coin 10 times and you might easily get 7 heads (70 %).
Toss it 1,000 times and getting 70 % heads is practically impossible.
Averages of many independent things stick to their expected value, and the chance of straying drops exponentially fast as you add more samples.
That is Hoeffding.

Key statementLet $X_{1}, \dots, X_{n}$ be independent random variables with each $X_{i} \in [a, b]$ .
Let $X ˉ = \frac{1}{n} \sum_{i = 1}^{n} X_{i}$ (the sample average).
Then

P (X ˉ - E [X ˉ] \geq t) \leq e^{- \frac{2 n t ^{2}}{( b - a ) ^{2}}} .

Coin-toss example: $P (X ˉ - p \geq t) \leq e^{- 2 n t^{2}}$ .

Reading the formula piece by piece

$X_{i} \in [a, b]$ : every observation is bounded.
For a coin with heads = 1 and tails = 0, a = 0 and b = 1.
$X ˉ$ is your sample average, for example the fraction of heads.
$E [X ˉ]$ is what the average "should" be.
For a coin with heads probability p, $E [X ˉ] = p$ .
t is your tolerance: how far above the truth you consider "too far".
The bound $e^{- 2 n t^{2} / (b - a)^{2}}$ shrinks exponentially in n.
Every extra batch of samples multiplies the bound by the same small factor.
Independence is required.
"Identically distributed" is not: the $X_{i}$ can have different distributions.

P (X ˉ - 0.5 \geq 0.1) \leq e^{- 2 \cdot 100 \cdot 0. 1^{2}} = e^{- 2} \approx 0.135.

$e^{- 2 \cdot 1000 \cdot 0.01} = e^{- 20} \approx 2.1 \times 1 0^{- 9}$ .
That is about 2 in a billion; the exact value is about $1.4 \times 1 0^{- 10}$ .
Ten times more tosses made the bound roughly 65 million times smaller.

You want to estimate a coin's bias to within t = 0.05, with at most a 1 % chance of overshooting.
Solve $e^{- 2 n (0.05)^{2}} \leq 0.01$ :

n \geq \frac{ln ( 100 )}{2 \cdot 0.0025} = \frac{4.605}{0.005} \approx 921 tosses .

Note that this answer does not depend on p.
This style of calculation ("how many samples?") reappears in Lesson 8 as "how many dimensions k?".

Fair coin, n = 50, t = 0.1. What does Hoeffding give?

$e^{- 2 \cdot 50 \cdot 0.01} = e^{- 1} \approx 0.37$ .

Ratings are in [1, 5]. How does the bound change compared with a 0/1 coin?

$(b - a)^{2} = 16$ , so the exponent becomes $- 2 n t^{2} /16$ .
You need 16× more samples for the same guarantee, because the data is more spread out.

YOUR STUDY PROGRESS

Finished this section? Save your progress.