Probability Theory Basics
Hoeffding's Inequality controls the probability of a large difference between a sample mean and the true mean.
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 ε.
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.
The Required Assumptions
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.
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. |
Setting Up a Problem
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 ε.
Name the variables: Use θ1 through θm for the observed random variables.
Identify the reference mean: Let μ be their common expectation, which serves as the true mean.
State the distribution assumptions: State that the variables are independent and identically distributed.
State the bounds: State that every θi lies between a and b with probability 1.
Choose the tolerance: Choose a positive value ε to define the deviation threshold.
Name the target event: The target is the event that the absolute difference between the sample mean and μ is at least ε.
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 μ.
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.
Common Setup Mistakes
Treating the sample mean as the true mean
The sample mean is computed from the observed sequence, while μ is the true mean and reference point.
Fix:
Name the observed average as the sample mean and reserve μ for the common expectation.Leaving out independence or identical distribution
Boundedness alone does not include the required i.i.d. condition.
Fix:
State that the variables are independent and identically distributed.Failing to state the common expectation
The deviation is measured relative to the common true mean.
Fix:
Identify μ as the common expectation.Using bounds without the probability-one condition
The required boundedness condition is specifically that P[a ≤ θi ≤ b] = 1 for every i.
Fix:
State the shared interval and that the condition holds with probability 1 for every variable.Choosing a nonpositive tolerance
The tolerance ε must be positive.
Fix:
Choose ε greater than zero.Claiming a numerical result from a setup alone
The setup identifies the problem but does not by itself provide a numerical evaluation.
Fix:
Separate the setup from the later calculation and use the complete statement of Hoeffding's Inequality for numerical evaluation.
Practice: Build the Setup
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 ε.
What do you think happens?
Which setup is incomplete for applying Hoeffding's Inequality?
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
- Hoeffding's Inequality bounds the probability that a sample mean differs from the true mean μ by at least a positive tolerance ε.
- The variables must be independent and identically distributed and must share the expectation μ.
- Every variable must lie between common bounds a and b with probability 1.
- The sample mean comes from the observations, while μ is the common expected value used as the reference.
- A correct setup identifies the variables, sample size, common mean, bounds, positive tolerance, and deviation event; numerical evaluation requires the complete inequality.
Key Takeaways
- 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.