Probability Theory Basics

Hoeffding's Inequality controls the probability of a large difference between a sample mean and 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 Observations to a Deviation Event

Suppose you observe a sequence of random variables and use those observations to compute a sample mean. You want to know how far that sample mean might be from the common true mean. Hoeffding's Inequality addresses this question by controlling the probability that the absolute difference between the sample mean and the true mean is at least a chosen positive tolerance ε.

How are the sample mean, true mean, and tolerance ε connected when the sample mean deviates from the true mean?

Sample Mean and True Mean

The sample mean is calculated from the observed sequence θ1 through θm. It is therefore tied to the particular observations in the sample. The true mean, written as μ, is the common expected value of the random variables. It is the reference point used to judge the sample mean.

What is the difference between the average computed from observations and the underlying true mean?

The Required Assumptions

Definition

To set up Hoeffding's Inequality, the variables θ1 through θm must be independent and identically distributed. They must share the expectation μ. In addition, every variable must be bounded between the same values a and b with probability 1. The tolerance ε used in the deviation event must be positive.

Independence: the variables are independent.
Identical distribution: the variables have the same distribution.
Common expectation: the variables share the expectation μ.
Common bounds: each θi lies between a and b with probability 1.
Positive tolerance: ε is greater than zero.

What conditions must the random variables satisfy before Hoeffding's Inequality can be used?

The Tolerance ε

The value ε specifies what size of difference counts as a deviation of interest. The event studied by Hoeffding's Inequality is that the absolute difference between the sample mean and μ is at least ε. Because ε must be positive, it represents a positive tolerance around the true mean.

Choice of ε	Meaning of the event
Positive ε	The event concerns a sample mean at least ε away from μ in absolute value.
Smaller positive ε	The event uses a narrower tolerance and focuses on a smaller deviation.
Larger positive ε	The event uses a wider tolerance and focuses on a larger deviation.

Changing ε changes the deviation threshold being investigated. A complete inequality is required to calculate a particular numerical probability bound.

What changes in the deviation event when ε becomes smaller or larger?

Setting Up a Problem

Worked example

A Symbolic Hoeffding Setup

You observe random variables θ1 through θm and want to study whether their sample mean differs from their common true mean by at least a positive tolerance ε.

1
Name the variables
Use θ1 through θm for the observed random variables.
2
Identify the reference mean
Let μ be their common expectation, which serves as the true mean.
3
State the distribution assumptions
State that the variables are independent and identically distributed.
4
State the bounds
State that every θi lies between a and b with probability 1.
5
Choose the tolerance
Choose a positive value ε to define the deviation threshold.
6
Name the target event
The target is the event that the absolute difference between the sample mean and μ is at least ε.

Result

The problem is correctly prepared for Hoeffding's Inequality when it includes the i.i.d. assumption, common expectation μ, bounds from a to b holding with probability 1, a positive ε, and the deviation event involving the sample mean and μ.

What steps transform a sampling problem into the quantities needed to apply Hoeffding's Inequality?

Reading the Probability Bound

The central question is probabilistic: how likely is it that the sample mean differs from μ by at least ε? Hoeffding's Inequality supplies a bound for that probability when the required assumptions hold. The sample size, the shared bounds, and the positive tolerance are inputs to a complete statement of the inequality.

How does Hoeffding's Inequality identify the probability of a deviation using the sample mean, μ, and ε?

Common Setup Mistakes

Common mistake
Treating the sample mean as the true mean
What it looks like
The average computed from the observations is called μ without separately identifying the common expectation.
Why it fails
The sample mean is computed from the observed sequence, while μ is the true mean and reference point.
Do this instead
Name the observed average as the sample mean and reserve μ for the common expectation.
Common mistake
Leaving out independence or identical distribution
What it looks like
The setup states only that the variables are bounded.
Why it fails
Boundedness alone does not include the required i.i.d. condition.
Do this instead
State that the variables are independent and identically distributed.
Common mistake
Failing to state the common expectation
What it looks like
The variables are described as i.i.d. but no common expectation μ is identified.
Why it fails
The deviation is measured relative to the common true mean.
Do this instead
Identify μ as the common expectation.
Common mistake
Using bounds without the probability-one condition
What it looks like
The setup mentions a and b but does not state that every variable lies between them with probability 1.
Why it fails
The required boundedness condition is specifically that P[a ≤ θi ≤ b] = 1 for every i.
Do this instead
State the shared interval and that the condition holds with probability 1 for every variable.
Common mistake
Choosing a nonpositive tolerance
What it looks like
The deviation threshold is set to ε equal to zero or to a negative value.
Why it fails
The tolerance ε must be positive.
Do this instead
Choose ε greater than zero.
Common mistake
Claiming a numerical result from a setup alone
What it looks like
The variables, bounds, sample size, and ε are listed, and a numerical probability is asserted without the complete inequality.
Why it fails
The setup identifies the problem but does not by itself provide a numerical evaluation.
Do this instead
Separate the setup from the later calculation and use the complete statement of Hoeffding's Inequality for numerical evaluation.

Practice: Build the Setup

MEDIUM

Write a complete Hoeffding setup for random variables θ1 through θm. Identify the sample mean, the common true mean μ, the assumptions about independence and identical distribution, the bounds a and b holding with probability 1, and a positive tolerance ε. Then state in words the deviation event that Hoeffding's Inequality will bound.

Hints

Begin with the sequence θ1 through θm.
Distinguish the observed sample mean from μ.
State both the i.i.d. condition and the common expectation.
Include the shared bounds from a to b with probability 1.
Make ε positive and describe an absolute difference of at least ε.

Your attempt (not saved)

What do you think happens?

Which setup is incomplete for applying Hoeffding's Inequality?

The variables are bounded, but independence and identical distribution are not stated.
The variables are i.i.d. with common expectation μ, bounded from a to b with probability 1, and ε is positive.
The sample mean is compared with μ using an absolute deviation threshold ε greater than zero.

Reveal answer

Answer:

The variables are bounded, but independence and identical distribution are not stated.

Boundedness is required, but the setup must also identify the i.i.d. variables and their common expectation μ, along with a positive tolerance and the deviation event.

Key Takeaways

1
Hoeffding's Inequality bounds the probability that a sample mean differs from the true mean μ by at least a positive tolerance ε.
2
The variables must be independent and identically distributed and must share the expectation μ.
3
Every variable must lie between common bounds a and b with probability 1.
4
The sample mean comes from the observations, while μ is the common expected value used as the reference.
5
A correct setup identifies the variables, sample size, common mean, bounds, positive tolerance, and deviation event; numerical evaluation requires the complete inequality.

At a glance

Hoeffding's Inequality controls the probability of a large absolute difference between a sample mean and a true mean.
Its assumptions include independence, identical distribution, a common expectation μ, and shared bounds a and b holding with probability 1.
The positive tolerance ε defines how large the deviation must be to belong to the event being studied.
A sample mean is computed from observations and should not be confused with the true mean μ.
Setting up the problem is distinct from numerically evaluating the probability bound.

More concepts starting with P