algebra911.com

Bernstein Inequality

Ever wonder how pollsters predict elections with just a small sample of voters? The Bernstein Inequality is a powerful mathematical tool that helps us understand how the average of random events is likely to be very close to the true, long-term average, giving us a solid guarantee about our predictions.

What Is the Bernstein Inequality?

The Bernstein Inequality is a result in probability theory that provides a limit, or an upper bound, on the probability that the sum of a series of random variables will deviate significantly from its expected value. Imagine you're flipping a fair coin 1000 times. You'd expect about 500 heads. But what's the chance you get something extreme, like 800 heads? The Bernstein Inequality gives you a mathematical guarantee, saying, "The probability of that happening is no more than this very small number."

It's part of a family of tools called "concentration inequalities." These inequalities are fundamental to statistics, machine learning, and science because they tell us how well a sample can represent a whole population. They provide a mathematical backbone for the Law of Large Numbers, which states that as you collect more data (e.g., flip a coin more times), your sample average will get closer to the true expected average. Bernstein's version is particularly powerful because it uses information about both the variance (the typical spread of the data) and the maximum possible value of each event to give a very tight and accurate bound.

Why Is This Inequality So Useful?

The Bernstein Inequality is more than just a theoretical curiosity; it has profound practical applications. Its main strength is turning uncertainty into a calculated risk. In many real-world situations, we can't measure everything, so we rely on samples. But how much can we trust those samples? Bernstein's inequality helps answer that.

Scientific Research: When scientists test a new drug on a sample of patients, they need to know how likely it is that the observed effect is just random chance versus a real outcome. Bernstein's inequality can help bound the probability of misleading results.
Quality Control: A factory produces thousands of light bulbs a day. To check their quality, they test a small batch. The inequality can tell them the probability that the defect rate in their sample is wildly different from the overall defect rate of the entire production line.
Finance: Financial analysts model stock returns as random variables. They can use these inequalities to estimate the probability of an investment portfolio performing much worse than expected.
Computer Science: In machine learning, algorithms learn from a limited set of data. Concentration inequalities guarantee that a model that performs well on the training data will also perform well on new, unseen data, with high probability.

Essentially, anywhere you use a sample to make an inference about a larger population, the Bernstein Inequality provides a rigorous way to quantify your confidence in that inference.

Breaking Down the Bernstein Inequality Formula

The formula for the Bernstein Inequality can look intimidating at first, but each piece has a specific and understandable meaning. Let's look at a common version used for independent random variables that are "bounded" (meaning they can't take on infinitely large values).

First, let's set up the scenario. Suppose we have a collection of $n$ independent random variables, $X_{1}, X_{2}, . . ., X_{n}$ . For simplicity, we'll assume they have an expected value of zero, $E [X_{i}] = 0$ . (If they don't, we can always just subtract the mean to get a new set of variables that do!). We also need two more pieces of information:

The variables are bounded: There is a number $M$ such that $| X_{i} | \leq M$ for all $i$ . This means no single outcome can be larger than $M$ or smaller than $- M$ .
We know the total variance: Let $V = \sum_{i = 1}^{n} Var (X_{i})$ . The variance measures the "spread" of each variable.

With these ingredients, the Bernstein Inequality states that for any positive number $t$ :

P (\sum_{i = 1}^{n} X_{i} \geq t) \leq \exp (- \frac{t^{2} / 2}{V + M t / 3})

Let's break this down with a table:

Symbol	Name	What It Means
$P (. . .)$	Probability	The chance that the event inside the parentheses happens. Our goal is to find a maximum value for this.
$\sum_{i = 1}^{n} X_{i}$	Sum of Variables	The total outcome from all our $n$ random events added together.
$t$	Deviation Threshold	A positive number you choose. It represents how far away from the expected sum (which is 0 in our setup) you're concerned about.
$\exp (z)$	Exponential Function	This is just $e^{z}$ , where $e \approx 2.718$ . The key thing to know is that when the exponent is a large negative number, the result is a very, very small positive number.
$V$	Total Variance	The sum of the individual variances. A larger $V$ means your data is naturally more spread out, making large deviations more likely (and the bound looser).
$M$	Maximum Bound	The absolute maximum value any of your $X_{i}$ variables can take. A larger $M$ also makes the bound looser.

The formula essentially says that the probability of your sum being off by at least $t$ gets exponentially smaller as your threshold $t$ increases, and as your number of samples $n$ (which increases $V$ ) grows.

Worked Example 1: Flipping a Biased Coin

Example 1

Let's say we flip a biased coin $n = 100$ times. The probability of getting heads is $p = 0.6$ . What is the probability of getting 70 or more heads? The expected number of heads is $100 \times 0.6 = 60$ .

Step 1: Define the Random Variables.
Let $C_{i} = 1$ if the $i$ -th flip is heads, and $C_{i} = 0$ if it's tails. The expected value is $E [C_{i}] = 0.6$ . To use our formula, we need variables with a mean of 0. So, we define $X_{i} = C_{i} - 0.6$ . Now, $E [X_{i}] = 0$ .

Step 2: Find the Parameters M and V.
The possible values for $X_{i}$ are $1 - 0.6 = 0.4$ (for heads) and $0 - 0.6 = - 0.6$ (for tails). The largest absolute value is $0.6$ , so our bound is $M = 0.6$ .
The variance of a single Bernoulli trial is $p (1 - p)$ . So, $Var (C_{i}) = 0.6 (1 - 0.6) = 0.24$ . The variance of $X_{i} = C_{i} - 0.6$ is the same, so $Var (X_{i}) = 0.24$ .
The total variance is $V = \sum_{i = 1}^{100} Var (X_{i}) = 100 \times 0.24 = 24$ .

Step 3: Define the Deviation Threshold t.
We are interested in the event "getting 70 or more heads." This is equivalent to $\sum C_{i} \geq 70$ . In terms of our zero-mean variables, this is $\sum (X_{i} + 0.6) \geq 70$ , which simplifies to $\sum X_{i} \geq 70 - (100 \times 0.6) = 10$ . So, our deviation threshold is $t = 10$ .

Step 4: Apply the Bernstein Inequality.
Now we plug $t = 10$ , $V = 24$ , and $M = 0.6$ into the formula:

P (\sum_{i = 1}^{100} X_{i} \geq 10) \leq \exp (- \frac{10^{2} / 2}{24 + (0.6) (10) / 3})

\leq \exp (- \frac{50}{24 + 2})

\leq \exp (- \frac{50}{26}) \approx \exp (- 1.923) \approx 0.146

Conclusion: The Bernstein Inequality guarantees that the probability of getting 70 or more heads is no more than $0.146$ , or $14.6 %$ . The actual probability (which can be calculated using the binomial distribution) is smaller, but this gives us a quick and powerful upper bound.

Worked Example 2: Quality Control in a Factory

Example 2

A factory produces electronic chips, and each chip has an independent $p = 0.05$ (or $5 %$ ) probability of being defective. A quality control inspector checks a batch of $n = 1000$ chips. What is the probability that they find 65 or more defective chips?

Step 1: Define the Random Variables.
Let $D_{i} = 1$ if chip $i$ is defective and $D_{i} = 0$ otherwise. The expected value is $E [D_{i}] = p = 0.05$ . The total expected number of defects is $1000 \times 0.05 = 50$ .
We center the variables: $X_{i} = D_{i} - 0.05$ . Now $E [X_{i}] = 0$ .

Step 2: Find the Parameters M and V.
The possible values for $X_{i}$ are $1 - 0.05 = 0.95$ and $0 - 0.05 = - 0.05$ . The largest absolute value is $0.95$ , so $M = 0.95$ .
The variance is $Var (X_{i}) = p (1 - p) = 0.05 (0.95) = 0.0475$ .
The total variance is $V = n \times Var (X_{i}) = 1000 \times 0.0475 = 47.5$ .

Step 3: Define the Deviation Threshold t.
We want the probability of finding 65 or more defects: $\sum D_{i} \geq 65$ .
In terms of our centered variables: $\sum X_{i} \geq 65 - (1000 \times 0.05) = 65 - 50 = 15$ . So, our threshold is $t = 15$ .

Step 4: Apply the Bernstein Inequality.
Plug in $t = 15$ , $V = 47.5$ , and $M = 0.95$ :

P (\sum_{i = 1}^{1000} X_{i} \geq 15) \leq \exp (- \frac{15^{2} / 2}{47.5 + (0.95) (15) / 3})

\leq \exp (- \frac{112.5}{47.5 + 4.75})

\leq \exp (- \frac{112.5}{52.25}) \approx \exp (- 2.153) \approx 0.116

Conclusion: The probability of finding 65 or more defective chips in the batch is less than or equal to $0.116$ , or $11.6 %$ . This gives the factory manager a solid upper limit on the risk of seeing a particularly bad batch.

Worked Example 3: Analyzing Average Test Scores

Example 3

A large school district administers a test where scores range from 0 to 100. The district-wide average score is $μ = 72$ with a variance of $σ^{2} = 144$ (so the standard deviation is $σ = 12$ ). A researcher samples $n = 50$ students. What is the probability that the sample average is 78 or higher?

Step 1: Define the Random Variables.
Let $S_{i}$ be the score of the $i$ -th student. We are given $E [S_{i}] = 72$ and $Var (S_{i}) = 144$ .
Let's center them: $X_{i} = S_{i} - 72$ . So $E [X_{i}] = 0$ and $Var (X_{i}) = 144$ .

Step 2: Find the Parameters M and V.
Scores range from 0 to 100. Our centered variable $X_{i}$ therefore ranges from $0 - 72 = - 72$ to $100 - 72 = 28$ . The largest absolute value is 72, so $M = 72$ .
The total variance is $V = n \times Var (X_{i}) = 50 \times 144 = 7200$ .

Step 3: Define the Deviation Threshold t.
We are interested in the sample average being 78 or higher. Let $\bar{S}$ be the sample average.
$\bar{S} \geq 78$
$\frac{1}{50} \sum S_{i} \geq 78$
$\sum S_{i} \geq 50 \times 78 = 3900$
Now, we convert this to our centered variables:
$\sum X_{i} \geq 3900 - (50 \times 72) = 3900 - 3600 = 300$ .
Our threshold for the sum is $t = 300$ .

Step 4: Apply the Bernstein Inequality.
Plug in $t = 300$ , $V = 7200$ , and $M = 72$ :

P (\sum_{i = 1}^{50} X_{i} \geq 300) \leq \exp (- \frac{300^{2} / 2}{7200 + (72) (300) / 3})

\leq \exp (- \frac{45000}{7200 + 7200})

\leq \exp (- \frac{45000}{14400}) = \exp (- 3.125) \approx 0.0439

Conclusion: There is less than a $4.4 %$ chance that the average score of a random sample of 50 students will be 78 or higher. This shows how quickly averages tend to converge toward the true mean.

What Are Common Mistakes to Avoid?

While powerful, the Bernstein Inequality must be applied correctly. Here are some common pitfalls to watch out for:

Forgetting Independence: The inequality relies on the assumption that the random variables are independent. If the outcome of one event influences another (e.g., sampling students from the same study group), the formula may not be valid.
Confusing Sum and Average: The formula is written for the sum of variables ( $\sum X_{i}$ ). If your question is about the average, you must convert it to a statement about the sum, as we did in Example 3. A common mistake is to use the deviation of the average directly for $t$ .
Misinterpreting the Result: The inequality gives an upper bound, not an exact probability. If the formula gives a probability of $0.1$ , the true probability could be $0.1$ , $0.05$ , or even $0.0001$ . It will not be $0.11$ . It's a worst-case guarantee.
Using the Wrong Bound (M): The value $M$ is the maximum absolute value of the centered variable ( $X_{i} = S_{i} - μ$ ). Be sure to calculate this correctly based on the range of your original data.
Applying to Unbounded Variables: The version of the inequality we use here requires that the variables be bounded. For variables that are technically unbounded (like human height), you can sometimes set a reasonable practical bound (e.g., no human is taller than 10 feet) to apply the formula.

Bernstein Inequality: A Quick Reference

Here's a quick summary of the key ideas to remember about the Bernstein Inequality.

Core Purpose: To provide a mathematical guarantee (an upper bound) on the probability that the sum or average of many independent random events will be far from its expected value.
Key Ingredients: You need to know three things:
1. $n$ : The number of independent random variables.
2. $V$ : The total variance of the variables, which measures their spread.
3. $M$ : The maximum possible absolute value of any single (centered) variable.
The Big Idea: The probability of a large deviation from the mean shrinks exponentially fast as the number of samples ( $n$ ) grows or the size of the deviation ( $t$ ) you're worried about increases.
The Formula (for zero-mean variables):
$P (\sum X_{i} \geq t) \leq \exp (- \frac{t^{2} / 2}{V + M t / 3})$
When to Use It: Use it when you need a confident estimate of how much a sample average might differ from the true average, such as in polling, scientific experiments, or quality control.

Frequently Asked Questions

Is the Bernstein Inequality always accurate?

The Bernstein Inequality provides a mathematically proven upper bound. This means the true probability is never larger than the value the inequality gives. However, it is often a conservative estimate; the actual probability can be much smaller.

What does it mean for a variable to be 'bounded'?

A bounded variable is one whose possible values are confined to a finite range. For example, a test score between 0 and 100 is bounded. The height of a person is also practically bounded, even if it's not strictly bounded in theory.

How is this different from the Law of Large Numbers?

The Law of Large Numbers is a qualitative statement: it says that the sample average will eventually converge to the true average. The Bernstein Inequality is quantitative: it tells you the specific probability of being a certain distance away from the average for a given sample size.

What if my random variables don't have a mean of zero?

That's almost always the case in real problems! You can easily adapt by 'centering' your variables. If a variable $S_{i}$ has a mean $μ$ , you create a new variable $X_{i} = S_{i} - μ$ . This new variable $X_{i}$ has a mean of zero, and you can apply the formula to it.

Are there other inequalities like this one?

Yes, Bernstein's is part of a family of concentration inequalities. Two other famous ones are Chebyshev's Inequality, which is more general but gives a much looser bound, and Hoeffding's Inequality, which is simpler but sometimes less tight than Bernstein's.

Why is there an 'exp' (exponential function) in the formula?

The exponential function shows that the probability of large deviations drops off extremely quickly. This 'exponential decay' is what makes the bound so powerful and useful, as it guarantees that extreme outcomes are exceptionally rare when you have a large number of samples.

Can I use this for the sum being too low, not just too high?

Absolutely. The inequality is symmetric. You can find the bound for $P (\sum X_{i} \leq - t)$ using the exact same formula. This is because if $X_{i}$ is bounded by $M$ , then so is $- X_{i}$ .