Hoeffding's Inequality: How Fast a Sample Mean Settles

Chapter 13 · Mathematics for AI and Machine Learning · Advanced · 1:40

An interactive live film: exact distributions of a coin's sample mean for N = 10 to 320 stand one behind another; their tails beyond p + epsilon shrink below the Hoeffding bound exp(-2 N epsilon^2). Find the smallest N with a 5% guarantee.

Narration

Toss a coin that lands heads with probability p, N times, and average the results. Each slice of this picture is the exact distribution of that sample mean, for a different number of tosses.

Going back, N doubles from slice to slice, and the distribution narrows around p. The sample mean settles on the true mean.

The rest of the narration is in the book's Companion.