Hoeffding Inequality
Compare a distribution-free concentration guarantee with an exact finite binomial tail.
Free theory articleCompare a distribution-free concentration guarantee with an exact finite binomial tail.
Concept & interpretation
The Hoeffding inequality provides an upper bound on the probability that the sum of bounded independent random variables deviates from its expected value by more than a certain amount. For a sequence of independent Bernoulli(p) random variables, it gives a distribution-free concentration guarantee on the empirical mean.
Experiment
You can interact with the Hoeffding Inequality module to see how the exact binomial tail compares with the Hoeffding bound under different parameters.
- Select a Sample count (e.g., 50).
- Choose a Success probability (e.g., 0.5).
- Adjust the Deviation epsilon (e.g., 0.1).
- Observe how the Exact upper tail compares to the Hoeffding bound. The canvas visualizes the threshold relative to the Binomial PMF.