Measure Concentration Inequalities

Hoeffding is the concentration result for the sample mean's deviation from the true mean.

Programming

Interactive lab

Try it: Concentration: Hoeffding, Chebyshev and Markov

The sample mean of m i.i.d. bounded samples concentrates around the true mean μ: repeated seeded experiments estimate P(|sample mean − μ| ≥ ε) and compare it with Hoeffding's bound 2·exp(−2mε²), Chebyshev's bound Var/ε² and Markov's bound for the one-sided event.

How it works

Draw θ1, …, θm i.i.d. Bernoulli(p) (bounded in [a, b] = [0, 1], common mean μ = p) and track the running sample mean.
The deviation event is |sample mean − μ| ≥ ε for a chosen positive tolerance ε.
Hoeffding: P(|mean − μ| ≥ ε) ≤ 2·exp(−2mε²/(b − a)²); Chebyshev with Var[mean] = p(1 − p)/m: ≤ p(1 − p)/(mε²); Markov for the non-negative mean: P(mean ≥ μ + ε) ≤ μ/(μ + ε).
Repeat the whole experiment many times (seeded) and count how often each event happens.
Compare the observed frequencies with the bounds: they are upper bounds, not the exact probability.

Default run (32 steps): θ1, …, θm are i.i.d. Bernoulli(0.5) samples, each in [a, b] = [0, 1], with true mean μ = 0.5. m = 100, ε = 0.1, seed 7. … 200 experiments: |mean − μ| ≥ 0.1 happened 3 times (frequency 0.015) — Hoeffding allows at most 0.2707, Chebyshev 0.25. One-sided mean ≥ μ + ε: 1 times (0.005) vs Markov 0.8333.

Simplified: Samples are Bernoulli(p) (0 or 1), so [a, b] = [0, 1]; the randomness comes from a seeded pseudo-random generator (mulberry32). Observed frequencies are estimates from a finite number of experiments.

Educational simulation

Loading the simulation…

From an Average to a Probability

A sample mean gives you an average of observed random variables. Hoeffding's Inequality addresses the next question: how likely is that average to be far from the distribution's true mean? It does not claim that the sample mean must equal the true mean. Instead, it provides an upper bound on the probability of a deviation at least as large as a chosen positive amount.

What probability is bounded when the sample mean is at least a chosen amount away from the true mean?

The Hoeffding Setup

To set up a Hoeffding analysis, begin with a sequence of random variables and summarize them using their sample mean. The variables must be identically distributed and independent. In addition, every variable must lie in the same interval from a to b with probability 1. Once these conditions are verified, identify the distribution's true mean and choose the positive deviation amount whose probability you want to bound.

How do bounded i.i.d. random variables become a sample mean, and where do the interval, true mean, and deviation amount enter?

The Controlled Event

Definition

Hoeffding's Inequality bounds the probability that the sample mean differs from the true mean by at least a chosen positive amount.

Each part of this statement has a specific role. The sample mean is the observed average being analyzed. The true mean is the reference value belonging to the distribution. The deviation amount determines what counts as a substantial difference. The result concerns the probability of the deviation event, and the theorem supplies an upper bound for that probability.

How are the sample mean, true mean, deviation amount, and interval bounds related?

Assumptions Before Applying It

1
Identify the random variables whose sample mean will be studied.
2
Check that the variables are independent.
3
Check that the variables are identically distributed.
4
Verify that every variable lies in the same interval from a to b with probability 1.
5
Identify the true mean and choose the positive deviation amount to analyze.
6
State that the desired result is an upper bound on the probability of the specified deviation.

Which properties must the random variables satisfy before Hoeffding's Inequality is applied?

A Symbolic Setup

Worked example

Preparing a Sequence for Hoeffding Analysis

Suppose a sequence of observations is represented by random variables that are independent, identically distributed, and all lie in the common interval from a to b with probability 1. You want to study the probability that their sample mean differs from the distribution's true mean by at least a chosen positive amount.

1
Identify the average
Use the sample mean of the sequence as the quantity whose deviation will be studied.
2
Identify the reference
Use the distribution's true mean as the value against which the sample mean is compared.
3
Specify the event
Define the event as the sample mean differing from the true mean by at least the chosen positive amount.
4
Verify the assumptions
The variables are independent, identically distributed, and bounded in the same interval from a to b with probability 1.
5
State the conclusion type
Hoeffding's Inequality supplies an upper bound on the probability of that deviation event.

Result

The analysis is correctly set up even before a numerical bound is computed. The essential result is a probability upper bound for the specified sample-mean deviation.

This example deliberately stops at the setup stage. A numerical bound would require the particular form of the inequality and chosen parameter values. The important reasoning is to identify the event and verify the assumptions before attempting to calculate or interpret a bound.

Hoeffding and Markov

Inequality	Quantity it concerns	Role in this topic
Hoeffding's Inequality	Probability that a sample mean differs from the true mean by at least a chosen positive amount	Provides an upper bound for a sample-mean deviation event
Markov's Inequality	A non-negative random variable exceeding a value	Used in the proof of Hoeffding's Inequality

The two inequalities concern different events and have different purposes in this context.

Do not replace Hoeffding's target event with Markov's target event. Hoeffding is the concentration result for the sample mean's deviation from the true mean. Markov concerns a non-negative random variable exceeding a value. Markov's Inequality is relevant here because it is used in the proof of Hoeffding's Inequality, not because the two statements bound the same quantity.

What is the difference between the quantity bounded by Hoeffding's Inequality and the quantity considered by Markov's Inequality?

Common Setup Mistakes

Common mistake
Treating Hoeffding's Inequality as a claim that the sample mean equals the true mean.
What it looks like
A learner concludes that the observed average must be the distribution's true mean.
Why it fails
The result is a probability upper bound for a deviation event, not a guarantee that no deviation occurs.
Do this instead
Describe how the inequality bounds the probability that the sample mean differs from the true mean by at least the chosen amount.
Common mistake
Forgetting to check the common interval.
What it looks like
A learner identifies independent and identically distributed variables but does not verify that every variable lies from a to b with probability 1.
Why it fails
The stated Hoeffding setup requires boundedness in a common interval.
Do this instead
Verify the interval condition for every variable before applying the result.
Common mistake
Confusing Hoeffding's target with Markov's target.
What it looks like
A learner describes Hoeffding as directly bounding the probability that a non-negative random variable exceeds a value.
Why it fails
That is the type of quantity Markov's Inequality concerns.
Do this instead
Reserve Hoeffding for the sample-mean deviation event and recognize Markov as an inequality used in Hoeffding's proof.
Common mistake
Skipping the independence or identical-distribution checks.
What it looks like
A learner applies the result to a sequence after only computing its average.
Why it fails
The stated setup uses i.i.d. random variables.
Do this instead
Check independence and identical distribution along with boundedness.

Practice the Setup

EASY

A sequence of random variables is described as independent and identically distributed. Every variable lies in the common interval from a to b with probability 1. Write a verbal Hoeffding setup: identify the quantity being averaged, the reference mean, the deviation event, and the kind of conclusion Hoeffding's Inequality provides.

Hints

Start with the sample mean.
Compare it with the distribution's true mean.
State that the deviation is at least a chosen positive amount.
The conclusion is an upper bound on a probability.

Your attempt (not saved)

MEDIUM

Explain why the following statement is incomplete: The variables are independent and identically distributed, so Hoeffding's Inequality applies. What additional property must be checked, and what probability event will be bounded?