Independent and Identically Distributed Random Variables
Hoeffding's Inequality controls the probability of a large difference between a sample mean and the true mean.
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 ε.
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 ε.
Absolute deviation event: |sample mean − μ| ≥ ε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.
Assumptions for Application
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. |
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.
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.
Identify the observations: Use θ1 through θm as the sequence of random variables and use their average as the sample mean.
Identify the reference: Use μ as the common expected value and therefore the true mean used for comparison.
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.
State the deviation event: The target is the probability that the absolute difference between the sample mean and μ is at least ε.
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 μ.
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
Treating the sample mean as the true mean.
Hoeffding's Inequality exists because the sample mean may differ from μ.
Fix:
Describe μ as the common expected value and the sample mean as the quantity computed from the observations.Forgetting the absolute value in the deviation event.
The stated event concerns the absolute difference, so deviations on either side of μ are included.
Fix:
Use the event |sample mean − μ| ≥ ε.Using a nonpositive tolerance.
The tolerance threshold must be positive.
Fix:
State ε > 0.Mentioning bounds without the probability-1 condition.
The required boundedness condition is specifically that each variable lies in the interval with probability 1.
Fix:
State the probability-1 bound for every θi.Claiming a numerical result from an incomplete setup.
The setup identifies the variables, bounds, sample size, and ε, but the source notes that numerical evaluation requires the complete inequality.
Fix:
Present the setup first and evaluate only when the complete inequality and required values are available.
Practice Check
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.
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 μ?
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
- Hoeffding's Inequality bounds the probability that a sample mean differs from the true mean μ by at least a chosen positive tolerance ε.
- The variables must be independent and identically distributed, share expectation μ, and be bounded between a and b with probability 1.
- The sample mean is computed from the observed variables, while μ is their common expected value and reference point.
- The deviation event is expressed using the absolute difference between the sample mean and μ.
- A complete setup identifies θ1 through θm, the bounds, μ, the sample mean, and ε before attempting a probability calculation.
Key Takeaways
- 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.