Independent and Identically Distributed Random Variables

Suppose you observe several random variables and use their sample mean to estimate a common 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…

When a Sample Misses Its Target

Suppose you observe several random variables and use their sample mean to estimate a common true mean. The sample mean can differ from that true mean in a particular sample. Hoeffding's Inequality addresses this uncertainty by bounding the probability that the difference is at least a chosen positive tolerance ε.

What does it mean for the sample mean to differ from the true mean by at least the tolerance ε?

The Deviation Event

Let θ1 through θm denote the observed random variables. Their sample mean is computed from those observations. Let μ denote their common expected value, which is the true mean used as the reference point. Hoeffding's Inequality focuses on the event that the absolute difference between the sample mean and μ is at least ε.

Rule

Key point

The sample mean is calculated from the observations you received. The true mean μ is the fixed reference value represented by their common expectation. Hoeffding's Inequality does not say that these two quantities are equal for every sample; it bounds how likely a deviation of at least ε is.

How does the sample mean relate to the fixed true mean, and what changes when a different sample is drawn?

Assumptions for Application

Definition

The variables must be independent and identically distributed, with common expectation μ. Each variable θi must also lie between the same lower bound a and upper bound b with probability 1. Finally, the tolerance ε must be positive.

Requirement	What the setup must contain
Independent	The variables satisfy the independence part of the i.i.d. requirement.
Identically distributed	The variables share the same distributional status and common expectation μ.
Bounded	P[a ≤ θi ≤ b] = 1 for every i.
Positive tolerance	ε is any positive number.
Common reference	μ is the common expected value used as the true mean.

The conditions that must be identified before using Hoeffding's Inequality.

What does each random variable share with the others, and how are the two parts of the i.i.d. requirement different?

Building the Setup

A Hoeffding setup begins with the sequence θ1 through θm. Record the interval [a, b] that contains every θi with probability 1. Identify μ as the common expected value, form the sample mean from the sequence, and choose a positive tolerance ε. The target is then the probability of the absolute-deviation event.

How do the random variables, their bounds, the sample mean, the true mean, and ε fit together?

Worked example

A Complete Symbolic Setup

Suppose θ1 through θm are i.i.d., share common expectation μ, and satisfy P[a ≤ θi ≤ b] = 1 for every i. A positive tolerance ε is selected.

1
Identify the observations
Use θ1 through θm as the sequence of random variables and use their average as the sample mean.
2
Identify the reference
Use μ as the common expected value and therefore the true mean used for comparison.
3
Verify the bounds
The condition P[a ≤ θi ≤ b] = 1 states that every variable lies in the same interval from a to b with probability 1.
4
State the deviation event
The target is the probability that the absolute difference between the sample mean and μ is at least ε.

Result

The problem has the required symbolic ingredients for applying Hoeffding's Inequality. A numerical probability bound cannot be evaluated from this setup alone without the complete statement of the inequality and the needed numerical inputs.

From Inputs to a Bound

Hoeffding's Inequality converts information about the sample and its variables into an upper bound on the probability of the deviation event. The relevant setup includes the sample size m, the common bounds a and b, and the positive tolerance ε, together with the i.i.d. assumptions and common expectation μ. The bound concerns reliability: it limits how probable it is for the sample mean to be at least ε away from μ.

How does Hoeffding's Inequality use the sample size, variable range, and ε to bound the deviation probability?

Edge case

If ε is not positive, the setup fails the stated requirement. If the variables are not known to lie between a and b with probability 1, the boundedness assumption has not been established. If μ is not identified as the common expected value, the reference point for the deviation is missing.

Mistakes in Setup

Common mistake
Treating the sample mean as the true mean.
What it looks like
The sample mean is assumed to equal μ for every possible sample.
Why it fails
Hoeffding's Inequality exists because the sample mean may differ from μ.
Do this instead
Describe μ as the common expected value and the sample mean as the quantity computed from the observations.
Common mistake
Forgetting the absolute value in the deviation event.
What it looks like
Only deviations above μ are considered.
Why it fails
The stated event concerns the absolute difference, so deviations on either side of μ are included.
Do this instead
Use the event |sample mean − μ| ≥ ε.
Common mistake
Using a nonpositive tolerance.
What it looks like
ε is set to zero or a negative value.
Why it fails
The tolerance threshold must be positive.
Do this instead
```
State ε > 0.
```
Common mistake
Mentioning bounds without the probability-1 condition.
What it looks like
The variables are said to be between a and b, but the setup does not state P[a ≤ θi ≤ b] = 1 for every i.
Why it fails
The required boundedness condition is specifically that each variable lies in the interval with probability 1.
Do this instead
State the probability-1 bound for every θi.
Common mistake
Claiming a numerical result from an incomplete setup.
What it looks like
A probability value is calculated without a complete inequality statement and numerical inputs.
Why it fails
The setup identifies the variables, bounds, sample size, and ε, but the source notes that numerical evaluation requires the complete inequality.
Do this instead
Present the setup first and evaluate only when the complete inequality and required values are available.

Practice Check

MEDIUM

A sequence θ1 through θm is independent and identically distributed. Every θi satisfies P[a ≤ θi ≤ b] = 1, and all variables share expectation μ. An analyst chooses a positive ε. Write the deviation event that Hoeffding's Inequality is intended to bound, then list the assumptions that justify the setup.

Hints

The event compares the sample mean with μ.
Use an absolute difference and include the phrase at least ε.
List i.i.d. behavior, common expectation μ, probability-1 bounds, and ε > 0.

Your attempt (not saved)

What do you think happens?

What should be the target event when the analyst wants to measure whether the sample mean is at least ε away from μ?

sample mean = μ
sample mean − μ ≥ ε
|sample mean − μ| ≥ ε
ε ≤ 0

Reveal answer

Answer:

|sample mean − μ| ≥ ε

The event uses the absolute difference, so it includes deviations in either direction, and ε is required to be positive.

Key Takeaways

1
Hoeffding's Inequality bounds the probability that a sample mean differs from the true mean μ by at least a chosen positive tolerance ε.
2
The variables must be independent and identically distributed, share expectation μ, and be bounded between a and b with probability 1.
3
The sample mean is computed from the observed variables, while μ is their common expected value and reference point.
4
The deviation event is expressed using the absolute difference between the sample mean and μ.
5
A complete setup identifies θ1 through θm, the bounds, μ, the sample mean, and ε before attempting a probability calculation.

At a glance

Hoeffding's Inequality controls the probability of a large difference between a sample mean and the true mean.
Its setup requires i.i.d. variables with common expectation μ, common probability-1 bounds from a to b, and a positive ε.
The sample mean can vary from sample to sample; μ is the fixed reference represented by the common expectation.
The target event is that the absolute difference between the sample mean and μ is at least ε.
A symbolic setup is not the same as a numerical evaluation; numerical evaluation requires the complete inequality and necessary values.

Related concepts

Concentration Inequalities

More concepts starting with I