Unit 5: Inequalities and Limit Theorems Study Guide

Learning Objectives for Unit 5: Inequalities and Limit Theorems

Upon completion of this unit, the following goals should be achieved:

• Understand Markov’s inequality and its application in finding upper bounds for tail probabilities of non-negative random variables.

• Utilize Chebyshev’s inequality to determine upper bounds of probabilities relating to deviation from the mean.

• Comprehend Hoeffding’s inequality for finding upper bounds of probabilities for the sample mean.

• Apply the Cauchy-Schwarz inequality to bound the absolute expectation of a product of random variables.

• Identify and differentiate between concave and convex functions based on their properties and graphs.

• Apply Jensen’s inequality, the Central Limit Theorem (CLT), and the Weak Law of Large Numbers (WLLN) in the context of probability convergence.

Introduction to Inequalities and Limit Theorems

• Statistical Estimation: Statistics and data science often involve estimating population distributions or parameters from finite data sets. Because true distributions are rarely computable, mathematicians use well-studied distributions with known properties to approximate unknown ones.

• Error Margins: When dealing with unknown distributions, the margin of error in estimates is uncertain. This unit provides tools to compute the probability that estimates deviate from true population parameters.

• Weak Law of Large Numbers (WLLN): This law dictates that as an experiment is repeated independently many times, the average result approaches the expected value.

• Central Limit Theorem (CLT): This theorem states that for a sufficiently large sample size, the sampling distribution of the mean approximates a normal distribution, regardless of the population's original distribution.

Markov's Inequality

• Tail Probabilities: Probabilities denoted as P(X > t) or $P(X \ge t)$ for t > 0 are referred to as tail probabilities. They quantify the likelihood of extreme events occurring.

• Definition: If $X$ is a non-negative random variable ($X \ge 0$) with a finite mean E(X) < \infty and t > 0, then:     $P(X \ge t) \le \frac{E(X)}{t}$

• Interpretation: The probability that $X$ exceeds a threshold $t$ is bounded by the mean of $X$ divided by $t$.

• Applicable Distributions: Discrete distributions such as Binomial, Poisson, and Geometric are non-negative. Continuous distributions like Exponential, Gamma, and Beta are also non-negative.

Verification via Exponential Distribution

• Setting: Let $X \sim \text{Exponential}(1/2)$. The mean is $E(X) = 2$. The Cumulative Distribution Function (CDF) is $F(x) = 1 - e^{-\frac{x}{2}}$ for $x \ge 0$.

• Markov Bound for t = 6:     $P(X \ge 6) \le \frac{2}{6} = \frac{1}{3} \approx 0.33$

• Direct Computation:     $P(X \ge 6) = 1 - F(6) = e^{-3} \approx 0.05$

• Validation: Since $0.05 \le 0.33$, the inequality holds.

Table 46: Markov’s Bound Comparison ($X \sim \text{Exponential}(1/2)$, $E(X)=2$)

Adapting Markov's Inequality for All Random Variables

• Absolute Value Version: Since Markov's requires non-negativity, we can apply it to the absolute value $|X|$ for any random variable with E(|X|) < \infty:     $P(|X| \ge t) \le \frac{E(|X|)}{t}$

• Example: Suppose $X \sim N(1, 1)$, where $E(|X|) \approx 1.17$. For $t = 3$:

  • Markov Bound: $P(|X| \ge 3) \le \frac{1.17}{3} \approx 0.39$ (39%).

  • Numerical Integration: P(|X| > 3) \approx 0.02.

Function Properties and Invertibility

• Strictly Increasing Function: A function $f: A \rightarrow B$ is strictly increasing if for any x_1 < x_2, f(x_1) < f(x_2).

• Strictly Decreasing Function: A function $f: A \rightarrow B$ is strictly decreasing if for any x_1 < x_2, f(x_1) > f(x_2).

• Invertible (One-to-One/Bijective) Functions: A function is invertible if there exists a function $g: B \rightarrow A$ such that $f(g(y)) = y$ and $g(f(x)) = x$. Every strictly increasing or decreasing function is invertible.

• Monotone Transformation with Markov's: Since $x \mapsto e^x$ is strictly increasing, the event $X \ge t$ is equivalent to $e^X \ge e^t$. Thus:     $P(X \ge t) = P(e^X \ge e^t) \le \frac{E(e^X)}{e^t}$

Chebyshev’s Inequality

• Purpose: While Markov's looks at values exceeding a threshold, Chebyshev's finds bounds for the distance of random variables from their mean.

• Definition: Let $X$ be a random variable with finite mean $\mu = E(X)$ and variance 0 < \sigma^2 = \text{Var}(X) < \infty. For any t > 0:     $P(|X - \mu| \ge t) \le \frac{\sigma^2}{t^2}$

• Standardized Form: Replacing $t$ with $\sigma t$ yields:     $P(|X - \mu| \ge \sigma t) \le \frac{1}{t^2}$

• Standardization Concept: The quantity $Z = \frac{X - \mu}{\sigma}$ centers data to zero and scales variance to one, which is vital for leveling the "playing field" in data science applications.

Table 47: Verifying Chebyshev’s Bound with $X \sim \text{Beta}(2,3)$

• Parameters: $E(X) = \frac{2}{2+3} = \frac{2}{5} = 0.4$.

• Variance: $\text{Var}(X) = \frac{2 \times 3}{(2+3)^2(2+3+1)} = \frac{6}{25 \times 6} = \frac{1}{25} = 0.04$.

• Bound for $X \sim \text{Beta}(2,3)$: $P(|X - 0.4| \ge t) \le \frac{1}{25t^2}$.

Hoeffding’s Inequality

• Strengths: Hoeffding’s inequality provides tighter bounds than Chebyshev's for sums of independent random variables, given the assumption that the variables are bounded within a finite range.

• General Definition: Let $X_1, X_2, \dots, X_n$ be i.i.d. random variables where $a \le X_i \le b$ and $\mu = E(X_i)$. For the sample mean $\bar{X} = \frac{1}{n} \sum X_i$ and t > 0:     $P(\bar{X} - \mu \ge t) \le e^{-\frac{2nt^2}{(b-a)^2}}$

• Two-Sided (Absolute) Bound:     $P(|\bar{X} - \mu| \ge t) \le 2e^{-\frac{2nt^2}{(b-a)^2}}$

Hoeffding’s for Bernoulli Random Variables

• For $X_i \sim \text{Bernoulli}(p)$, where $a = 0$ and $b = 1$:     $P(|\bar{X} - p| \ge t) \le 2e^{-2nt^2}$

• Solving for Sample Size ($n$): If we want the probability of deviation to be less than a small threshold $2\alpha$, we set $2\alpha = 2e^{-2nt^2}$ and solve for $n$:     $n = \frac{-\ln(\alpha)}{2t^2}$

• Example Coin Toss: To ensure the estimate of heads $p$ is within $t=0.01$ with probability $1 - 0.02 = 0.98$ ($2\alpha = 0.02, \alpha = 0.01$):     $n = \frac{-\ln(0.01)}{2 \times (0.01)^2} \approx 23,026 \text{ data points}$

Example 5.1: Machine Learning Model Accuracy

• Context: A model is trained on 1000 examples with actual accuracy $p$. Xi = 1 if correct.

• Goal: Find the upper bound for the probability that observed accuracy differs from actual accuracy by more than 1% ($t = 0.01$).

• Solution: Using $n=1000$, $t=0.01$, $a=0$, and $b=1$:     $P(|\bar{X} - p| \ge 0.01) \le 2e^{-2 \times 1000 \times (0.01)^2} = 2e^{-0.2} \approx 1.637$

Cauchy-Schwarz Inequality

• Linear Algebra Motivation: Derived from inner products of vectors where $|\langle \mathbf{u}, \mathbf{v} \rangle| \le \|\mathbf{u}\| \|\mathbf{v}\|$.

• Definition for Random Variables: Let $X$ and $Y$ have finite variances. Then:     $E(|XY|) \le \sqrt{E(X^2) E(Y^2)}$

• Correlation and Covariance: For zero-mean, unit-variance variables, $E(XY)$ represents the correlation. If variables are strongly correlated, $|E(XY)|$ is near 1; if independent, it is near 0.

Example 5.2: Product Expectation Estimate

• Given: $E(X)=1, E(Y)=2, \text{Var}(X)=1, \text{Var}(Y)=1$.

• Step 1: Calculate second moments.     $E(X^2) = \text{Var}(X) + (E(X))^2 = 1 + 1^2 = 2$     $E(Y^2) = \text{Var}(Y) + (E(Y))^2 = 1 + 2^2 = 5$

• Step 2: Apply Cauchy-Schwarz.     $E(|XY|) \le \sqrt{2 \times 5} = \sqrt{10} \approx 3.16$

Jensen’s Inequality

• Convex Function Definition: A function $g$ is convex if for any two points, the line segment connecting them lies above the graph. Quantitatively: $g(\alpha x + (1-\alpha)y) \le \alpha g(x) + (1-\alpha)g(y)$.

• Concave Function Definition: A function $g$ is concave if the line segment lies below the graph. Quantitatively: $g(\alpha x + (1-\alpha)y) \ge \alpha g(x) + (1-\alpha)g(y)$.

• Second Derivative Test:

  • $g''(x) \ge 0 \implies \text{Convex}$

  • $g''(x) \le 0 \implies \text{Concave}$

• Jensen’s Equality:

  • If $g$ is convex: $E[g(X)] \ge g(E[X])$

  • If $g$ is concave: $E[g(X)] \le g(E[X])$

• Applications:

  • Checking variance: Let $g(x) = x^2$ (convex). Thus $E(X^2) \ge (E(X))^2$, which confirms $\text{Var}(X) = E(X^2) - (E(X))^2 \ge 0$.

  • Logs: Since $g(x) = \ln(x)$ is concave (g''(x) = -\frac{1}{x^2} < 0), then $E[\ln(X)] \le \ln(E[X])$.

The Weak Law of Large Numbers (WLLN)

• Formal Statement: Let $X_1, X_2, \dots, X_n$ be random variables with E(X_i) = \mu < \infty. For any t > 0:     \lim_{n \to \infty} P(|\bar{X} - \mu| > t) = 0

• Interpretation: As sample size increases to infinity, the probability that the sample mean deviates from the true mean by any fixed amount approaches zero. This is known as convergence in probability.

• Proof via Chebyshev:     P(|\bar{X} - \mu| > t) \le \frac{\text{Var}(\bar{X})}{t^2} = \frac{\sigma^2}{nt^2}     As $n \to \infty$, the right side goes to 0.

The Central Limit Theorem (CLT)

• Formal Statement: Let $X_1, \dots, X_n$ be i.i.d. with mean $\mu$ and finite variance \sigma^2 > 0. Let $\bar{X}_n$ be the sample mean. The standardized sample mean $Z_n$ is defined as:     $Z_n = \frac{\bar{X}_n - \mu}{\frac{\sigma}{\sqrt{n}}}$     As $n \to \infty$, the distribution of $Z_n$ approaches the standard normal distribution $N(0,1)$. For any $z \in \mathbb{R}$:     $\lim_{n \to \infty} P(Z_n \le z) = \int_{-\infty}^{z} \frac{1}{\sqrt{2\pi}} e^{-\frac{t^2}{2}} \,dt$

• Key Results:

  • The sample mean is approximately normally distributed: $\bar{X}_n \sim N(\mu, \frac{\sigma^2}{n})$.

  • This holds regardless of the original population distribution (e.g., tested with Uniform and Exponential distributions).

  • QQ-Plots: Quantile-Quantile plots confirm normality when data points follow a straight line (empirical quantiles match theoretical quantiles).

Example 5.3: Sample Mean from Beta(2,3)

• Sample size: $n=50$.

• Parameters: $\mu = 0.4$, $\sigma^2 = \frac{1}{25} = 0.04$.

• CLT Result: $\bar{X} \sim N(0.4, \frac{0.04}{50}) \implies N(0.4, 0.0008)$.

Example 5.4: IQ Scores

• Parameters: Average IQ = 100, $\sigma = 15$.

• Part A (Single Person): Probability a random person has IQ > 103.     P(X > 103) = P(Z > \frac{103 - 100}{15}) = P(Z > 0.2) \approx 0.4207 \text{ (42.07%)}

• Part B (Sample size 64): Probability the sample average IQ > 103.     $SD(\bar{X}) = \frac{15}{\sqrt{64}} = \frac{15}{8} = 1.875$     P(\bar{X} > 103) = P(Z > \frac{103 - 100}{1.875}) = P(Z > 1.6) \approx 0.0548 \text{ (5.48%)}

Example 5.5: Referendum Likelihood

• Context: 50 million voters total. 5000 fixed "yes" votes. The remaining 49,995,000 are undecided ($X_i \sim \text{Bernoulli}(0.5)$). To pass, 25,000,000 total votes are needed.

• Goal: Calculate chance of passing.     P(\sum_{i=1}^{49,995,000} X_i + 5000 > 25,000,000) = P(\sum X_i > 24,995,000)     P(\frac{1}{n} \sum X_i > \frac{24,995,000}{49,995,000})

• The law of large numbers and CLT allows calculating the high-precision probability of this sum exceeding the threshold (though the transcript cuts off the final numerical result).