Probability Inequalities

Learning Objectives

The Problem: Bounding the Unknown

In real-world applications, we rarely know the exact probability distribution of our data. Even when we do, computing exact tail probabilities can be intractable. Yet we needguarantees about unlikely events:

• Casino owners need to bound the probability of extreme losses in a night
• Insurance companies must guarantee solvency under rare catastrophic events
• ML engineers need confidence that a model trained on n samples will generalize (PAC learning)
• A/B testers want to know when observed differences are statistically significant

The Central Question: Given limited information about a distribution (just its mean, or mean and variance), what can we definitively say about the probability of extreme values?

Probability inequalities provide distribution-free bounds - guarantees that hold regardless of the specific shape of the distribution. This is incredibly powerful: we get certain statements about uncertain quantities.

Historical Context

These inequalities represent some of the most elegant results in probability theory, developed over two centuries:

Markov's Inequality

Markov's inequality is the simplest and most general tail bound. It only requires the random variable to be non-negative with a finite mean.

Intuitive Meaning

Think of it this way: if the average income in a city is $50,000, then at most 10% of people can earn $500,000 or more. Why? Because if more than 10% earned that much, the average would have to be higher!

The mean must "support" all the probability mass. If too much probability is in the high tail, the mean would be pulled up. This geometric constraint is what Markov's inequality captures.

The Proof (One Line!)

The proof is beautifully simple. For non-negative X:

The first inequality holds because we're dropping the contribution from $X < a$. The second holds because when $X geq a$, we have $X geq a$. Dividing both sides by a gives the result.

Examples

1. Salary bounds: If average salary is $50K, at most 20% earn ≥ $250K (since 50K/250K = 0.2)
2. Website latency: If average response time is 100ms, at most 10% of requests take ≥ 1 second
3. Model loss: If expected loss is 0.1, the probability of loss ≥ 1 is at most 0.1

Interactive: Markov's Inequality

Explore how Markov's bound compares to the true tail probability. Notice how the bound only depends on the mean, not the shape of the distribution.

Chebyshev's Inequality

Chebyshev's inequality uses more information - both the mean and variance - to provide a tighter bound. Most importantly, it works for any distribution with finite variance.

Alternative Form

Sometimes written in terms of deviation $epsilon$ from the mean:

Intuitive Meaning

Chebyshev tells us that no matter the distribution shape, at least$1 - 1/k^2$ of the probability mass lies within k standard deviations of the mean:

Why Chebyshev is Powerful

The key insight is that Chebyshev is distribution-free. It works for:

• Symmetric or asymmetric distributions
• Light-tailed or heavy-tailed distributions
• Discrete or continuous distributions
• Any distribution with finite variance

This universality makes it invaluable when you don't know the exact distribution shape - which is almost always the case in practice!

Interactive: Chebyshev's Inequality

Compare different distributions with the same mean and variance. All satisfy Chebyshev's bound, but some concentrate much better than others.

One-Sided Chebyshev (Cantelli's Inequality)

Sometimes we only care about one tail - for example, "what's the probability of extreme losses" (not gains). Cantelli's inequality provides a tighter one-sided bound:

This is tighter than halving the two-sided Chebyshev bound! For k=2, Cantelli gives ≤20% (vs 12.5% from two-sided/2).

Chernoff Bounds

Chernoff bounds are exponentially tight - they decrease as $e^{-cn}$ rather than $1/n$ or $1/n^2$. This makes them essential for analyzing large deviations.

For Sum of Bernoulli Trials

The most common application is for the sum of n independent Bernoulli(p) trials, $S_n = sum_{i=1}^n X_i$ with mean $mu = np$:

Hoeffding's Inequality

Hoeffding's inequality is the workhorse of modern machine learning theory. It gives exponentially tight bounds for sums of bounded independent random variables.

Simplified Form (for [0, 1] variables)

When all $X_i in [0, 1]$ (common in ML for losses, accuracies):

The PAC Learning Connection

This directly gives us sample complexity bounds! If we want the empirical mean to be within ε of the true mean with probability at least 1 - δ:

This is the foundation of PAC (Probably Approximately Correct) learning!

Interactive: Hoeffding for PAC Learning

Calculate how many samples you need to achieve a given accuracy with a specified confidence level. This is the fundamental calculation behind statistical learning theory.

Interactive: Inequality Comparison

See all the inequalities side-by-side on the same problem. Watch how they compare as you adjust the sample size and deviation threshold.

Summary: When to Use Which

AI/ML Applications

1. Generalization Bounds

The fundamental question in ML: will my model perform well on new data? Hoeffding tells us that with n training samples, the difference between training and test error is bounded:

This is why more data = better generalization is a mathematical certainty, not just empirical observation.

2. Stochastic Gradient Descent

When we use mini-batches, the gradient estimate concentrates around the true gradient. For batch size b:

This justifies why larger batches give more stable training (but with diminishing returns beyond a point).

3. Dropout Analysis

Dropout randomly masks neurons. With dropout rate p, the output is a random variable. Concentration inequalities show that the masked network's output concentrates around the expected (full network) output, explaining why dropout works as regularization.

4. A/B Testing

When comparing two models (A vs B), Hoeffding tells us when we have enough samples to be confident the observed difference is real:

Python Implementation

1import numpy as np
2from scipy import stats
3
4def markov_bound(mean: float, threshold: float) -> float:
5    """
6    Markov's Inequality: P(X >= a) <= E[X]/a for X >= 0
7
8    Args:
9        mean: Expected value E[X]
10        threshold: The threshold 'a'
11
12    Returns:
13        Upper bound on P(X >= threshold)
14    """
15    if threshold <= 0:
16        return 1.0
17    return min(mean / threshold, 1.0)
18
19
20def chebyshev_bound(variance: float, epsilon: float) -> float:
21    """
22    Chebyshev's Inequality: P(|X - μ| >= ε) <= Var(X)/ε²
23
24    Args:
25        variance: Var(X)
26        epsilon: Deviation threshold
27
28    Returns:
29        Upper bound on P(|X - μ| >= epsilon)
30    """
31    if epsilon <= 0:
32        return 1.0
33    return min(variance / (epsilon ** 2), 1.0)
34
35
36def chebyshev_k_form(k: float) -> float:
37    """
38    Chebyshev's Inequality in k-form: P(|X - μ| >= kσ) <= 1/k²
39
40    Args:
41        k: Number of standard deviations
42
43    Returns:
44        Upper bound on tail probability
45    """
46    if k <= 0:
47        return 1.0
48    return 1.0 / (k ** 2)
49
50
51def cantelli_bound(variance: float, epsilon: float) -> float:
52    """
53    Cantelli's Inequality (one-sided Chebyshev):
54    P(X - μ >= ε) <= σ²/(σ² + ε²)
55
56    Args:
57        variance: Var(X) = σ²
58        epsilon: Deviation threshold
59
60    Returns:
61        Upper bound on P(X - μ >= epsilon)
62    """
63    if epsilon <= 0:
64        return 1.0
65    return variance / (variance + epsilon ** 2)
66
67
68def hoeffding_bound(n: int, epsilon: float, a: float = 0, b: float = 1) -> float:
69    """
70    Hoeffding's Inequality: P(|X̄ - μ| >= ε) <= 2*exp(-2nε²/(b-a)²)
71
72    Args:
73        n: Sample size
74        epsilon: Deviation threshold
75        a: Lower bound of random variables
76        b: Upper bound of random variables
77
78    Returns:
79        Upper bound on tail probability
80    """
81    if epsilon <= 0 or n <= 0:
82        return 1.0
83    range_sq = (b - a) ** 2
84    return min(2 * np.exp(-2 * n * epsilon**2 / range_sq), 1.0)
85
86
87def hoeffding_sample_size(epsilon: float, delta: float, a: float = 0, b: float = 1) -> int:
88    """
89    Calculate required sample size for Hoeffding bound.
90
91    Given desired accuracy ε and failure probability δ,
92    find n such that P(|X̄ - μ| >= ε) <= δ
93
94    Args:
95        epsilon: Desired accuracy
96        delta: Allowed failure probability
97        a: Lower bound of random variables
98        b: Upper bound of random variables
99
100    Returns:
101        Required sample size n
102    """
103    range_sq = (b - a) ** 2
104    return int(np.ceil(np.log(2 / delta) * range_sq / (2 * epsilon ** 2)))
105
106
107# Example usage
108if __name__ == "__main__":
109    print("=== Probability Inequalities Demo ===\n")
110
111    # Example 1: Markov's Inequality
112    mean = 100  # E[X] = 100
113    threshold = 500
114    bound = markov_bound(mean, threshold)
115    print(f"Markov: If E[X] = {mean}, P(X >= {threshold}) <= {bound:.4f}")
116
117    # Example 2: Chebyshev's Inequality
118    variance = 25  # σ² = 25, σ = 5
119    epsilon = 10  # 2 standard deviations
120    bound = chebyshev_bound(variance, epsilon)
121    print(f"Chebyshev: If Var(X) = {variance}, P(|X - μ| >= {epsilon}) <= {bound:.4f}")
122
123    # Example 3: Compare Normal true probability vs Chebyshev
124    k = 2
125    true_prob = 2 * (1 - stats.norm.cdf(k))  # Two-tailed
126    chebyshev = chebyshev_k_form(k)
127    print(f"\nFor k = {k} std devs from mean:")
128    print(f"  Normal true P: {true_prob:.6f}")
129    print(f"  Chebyshev bound: {chebyshev:.6f}")
130
131    # Example 4: Hoeffding sample size calculation
132    desired_epsilon = 0.02  # Within 2%
133    desired_delta = 0.05    # 95% confidence
134    n = hoeffding_sample_size(desired_epsilon, desired_delta)
135    print(f"\nHoeffding: For ±{desired_epsilon*100:.0f}% accuracy at {(1-desired_delta)*100:.0f}% confidence:")
136    print(f"  Required samples: {n:,}")

Common Pitfalls

Test Your Understanding

Summary

The Big Picture: Probability inequalities let us make guaranteed statements about uncertain quantities. They are the bridge between probability theory and practical ML engineering - turning "this probably works" into "this is guaranteed to work with high probability."