The math you actually need

1. Proof of Linearity of Expectation (Continuous Case)

Let $X$ and $Y$ be continuous random variables with joint probability density function $p(x, y)$. By the definition of mathematical expectation:

$$\mathbb{E}[aX + bY] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} (ax + by) p(x, y) \, dx \, dy$$

Using the linearity of integrals, we can split the double integral into two parts:

$$\mathbb{E}[aX + bY] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} ax p(x, y) \, dx \, dy + \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} by p(x, y) \, dx \, dy$$

Factor out the constants $a$ and $b$, and swap the order of integration:

$$\mathbb{E}[aX + bY] = a \int_{-\infty}^{\infty} x \left( \int_{-\infty}^{\infty} p(x, y) \, dy \right) dx + b \int_{-\infty}^{\infty} y \left( \int_{-\infty}^{\infty} p(x, y) \, dx \right) dy$$

Using the definition of marginal probability density functions:

$$p_X(x) = \int_{-\infty}^{\infty} p(x, y) \, dy, \quad p_Y(y) = \int_{-\infty}^{\infty} p(x, y) \, dx$$

Substituting these back into the equation:

$$\mathbb{E}[aX + bY] = a \int_{-\infty}^{\infty} x p_X(x) \, dx + b \int_{-\infty}^{\infty} y p_Y(y) \, dy = a\mathbb{E}[X] + b\mathbb{E}[Y]$$

Q.E.D. Note that we never assumed $X$ and $Y$ are independent (i.e., we did not use the condition $p(x, y) = p_X(x) p_Y(y)$). Therefore, Linearity of Expectation holds unconditionally for any random variables, regardless of their dependence.

2. Proof of the Variance Formula

Variance is defined as the expected squared deviation of a random variable from its mean (let $\mu = \mathbb{E}[X]$):

$$\text{Var}(X) = \mathbb{E}[(X - \mu)^2]$$

Expanding the squared term inside the expectation operator:

$$(X - \mu)^2 = X^2 - 2\mu X + \mu^2$$

By the linearity of expectation, we apply the expectation operator $\mathbb{E}$ to each term individually:

$$\text{Var}(X) = \mathbb{E}[X^2 - 2\mu X + \mu^2] = \mathbb{E}[X^2] - \mathbb{E}[2\mu X] + \mathbb{E}[\mu^2]$$

Since $\mu = \mathbb{E}[X]$ is a constant, the expectation of a constant is the constant itself, and we can factor constants out of the expectation operator:

$$\mathbb{E}[2\mu X] = 2\mu \mathbb{E}[X] = 2\mu \cdot \mu = 2\mu^2$$ $$\mathbb{E}[\mu^2] = \mu^2$$

Substitute these back into the equation:

$$\text{Var}(X) = \mathbb{E}[X^2] - 2\mu^2 + \mu^2 = \mathbb{E}[X^2] - \mu^2 = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$$

Q.E.D.

1. "Centroid Superposition" of Expectation

If we view a probability density function as a physical mass distribution, the mathematical expectation $\mathbb{E}[X]$ is the center of mass (centroid) of the system.

• When you join two physical bodies with centroids at different coordinates, the centroid of the combined system depends only on the individual centroids and their relative mass weights.
• Even if the two bodies are connected by a stiff spring (dependent), their combined center of mass is still the weighted sum of their individual centers of mass.
• In machine learning, this property forms the basis of ensemble methods like Bagging and Random Forests. The expected prediction of an ensemble is simply the average of the individual models' expectations, regardless of the correlation between the models.

2. Variance and "Moment of Inertia"

In physics, the moment of inertia measures a body's resistance to rotational acceleration and is defined as $\int r^2 dm$, which is mathematically identical to the variance formula $\mathbb{E}[(X - \mu)^2]$:

• The mean $\mu$ acts as the rotation axis (centroid).
• The variance represents the moment of inertia about this axis, describing the spread of the probability mass.
• The variance formula $\text{Var}(X) = \mathbb{E}[X^2] - \mu^2$ is the statistical equivalent of the Parallel Axis Theorem: the moment of inertia about any axis ($\mathbb{E}[X^2]$) is equal to the moment of inertia about the centroid axis ($\text{Var}(X)$) plus the total mass times the squared distance between the axes ($1 \cdot \mu^2$).

Derivation 1: Equivalence of Linear Regression (Gaussian Noise) and MSE Loss

Assume a linear regression model predicts $\hat{y}_i = \mathbf{w}^\top \mathbf{x}_i + b$. Let the model prediction error (noise) be $\epsilon_i = y_i - \hat{y}_i$, where $\epsilon_i$ are independent and identically distributed (i.i.d.) according to a zero-mean Gaussian distribution: $\epsilon_i \sim \mathcal{N}(0, \sigma^2)$.

Thus, given features $\mathbf{x}_i$ and parameters $\mathbf{w}, b$, the target label $y_i$ follows the conditional distribution:

$$y_i \mid \mathbf{x}_i; \mathbf{w}, b \sim \mathcal{N}(\mathbf{w}^\top \mathbf{x}_i + b, \sigma^2)$$

The probability density function for a single point is:

$$p(y_i \mid \mathbf{x}_i; \mathbf{w}, b) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left( -\frac{(y_i - (\mathbf{w}^\top \mathbf{x}_i + b))^2}{2\sigma^2} \right)$$

The likelihood function $L(\mathbf{w}, b)$ over the entire dataset of $n$ samples is the product of individual densities:

$$L(\mathbf{w}, b) = \prod_{i=1}^n p(y_i \mid \mathbf{x}_i; \mathbf{w}, b) = \prod_{i=1}^n \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left( -\frac{(y_i - (\mathbf{w}^\top \mathbf{x}_i + b))^2}{2\sigma^2} \right)$$

Taking the natural logarithm of both sides gives the log-likelihood:

$$\ln L(\mathbf{w}, b) = \sum_{i=1}^n \ln \left( \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left( -\frac{(y_i - (\mathbf{w}^\top \mathbf{x}_i + b))^2}{2\sigma^2} \right) \right)$$ $$\ln L(\mathbf{w}, b) = -\frac{n}{2}\ln(2\pi\sigma^2) - \frac{1}{2\sigma^2} \sum_{i=1}^n (y_i - (\mathbf{w}^\top \mathbf{x}_i + b))^2$$

To find the MLE parameters, we maximize $\ln L(\mathbf{w}, b)$. Since the term $-\frac{n}{2}\ln(2\pi\sigma^2)$ and the coefficient $\frac{1}{2\sigma^2}$ are constants with respect to the optimization parameters $\mathbf{w}$ and $b$:

$$\arg\max_{\mathbf{w}, b} \ln L(\mathbf{w}, b) = \arg\max_{\mathbf{w}, b} \left[ - \sum_{i=1}^n (y_i - (\mathbf{w}^\top \mathbf{x}_i + b))^2 \right] = \arg\min_{\mathbf{w}, b} \sum_{i=1}^n (y_i - (\mathbf{w}^\top \mathbf{x}_i + b))^2$$

Normalizing by the factor $1/n$ does not alter the optimal parameters. Hence, maximizing the likelihood is mathematically equivalent to minimizing the Mean Squared Error (MSE) Loss:

$$\mathcal{L}_{\text{MSE}} = \frac{1}{n} \sum_{i=1}^n (y_i - \hat{y}_i)^2$$

Q.E.D.

Derivation 2: Equivalence of Logistic Regression (Bernoulli Trials) and Binary Cross-Entropy (BCE) Loss

In a binary classification task, labels $y_i \in \{0, 1\}$. Let the predicted probability be $p_i = \sigma(\mathbf{w}^\top \mathbf{x}_i + b) \in [0, 1]$ representing:

$$P(y_i = 1 \mid \mathbf{x}_i; \mathbf{w}, b) = p_i, \quad P(y_i = 0 \mid \mathbf{x}_i; \mathbf{w}, b) = 1 - p_i$$

This conditional probability can be written in the compact Bernoulli distribution form:

$$P(y_i \mid \mathbf{x}_i; \mathbf{w}, b) = p_i^{y_i} (1 - p_i)^{1 - y_i}$$

The likelihood function $L(\mathbf{w}, b)$ for $n$ i.i.d. samples is:

$$L(\mathbf{w}, b) = \prod_{i=1}^n p_i^{y_i} (1 - p_i)^{1 - y_i}$$

Taking the natural logarithm yields the log-likelihood:

$$\ln L(\mathbf{w}, b) = \sum_{i=1}^n \left[ y_i \ln p_i + (1 - y_i) \ln(1 - p_i) \right]$$

Maximizing the log-likelihood is equivalent to minimizing the Negative Log-Likelihood (NLL). Normalizing by $1/n$ gives:

$$\mathcal{L}_{\text{BCE}} = -\frac{1}{n} \sum_{i=1}^n \left[ y_i \ln p_i + (1 - y_i) \ln(1 - p_i) \right]$$

This is exactly the standard Binary Cross-Entropy (BCE) Loss.

Q.E.D.

Bonus: What if the Noise is Laplacian? (Laplace Noise & L1 Loss)

If we assume the error follows a Laplace distribution $\epsilon_i \sim \text{Laplace}(0, b)$, its probability density is $p(\epsilon_i) = \frac{1}{2b} \exp\left(-\frac{|\epsilon_i|}{b}\right)$. The log-likelihood is:

$$\ln L(\mathbf{w}, b) = -n\ln(2b) - \frac{1}{b} \sum_{i=1}^n |y_i - (\mathbf{w}^\top \mathbf{x}_i + b)|$$

Maximizing this likelihood is equivalent to minimizing:

$$\sum_{i=1}^n |y_i - (\mathbf{w}^\top \mathbf{x}_i + b)|$$

This is the L1 Loss (Mean Absolute Error, MAE). Thus: Gaussian Noise $\iff$ L2 Loss (MSE), while Laplacian Noise $\iff$ L1 Loss (MAE). This is a classic conceptual question on the USAIO!

1. Gaussian Noise and the Quadratic Penalty of MSE

The Gaussian distribution assumes that small errors are common, whereas extremely large errors (outliers) are exponentially rare. Thus, if a model makes a massive prediction error, the likelihood of that observation under a Gaussian assumption is virtually zero.

• To prevent this, the loss function uses a **quadratic (L2) penalty** that disproportionately punishes large errors.
• This explains why MSE is highly sensitive to **outliers**: a single outlier with a large error can dominate the loss value and drag the regression line far away from the rest of the data.

2. Laplacian Noise and the Robust L1 Loss

The Laplace distribution is peakier and has fatter tails than the Gaussian distribution, meaning it assigns higher probability to larger deviations (outliers).

• Its corresponding loss function uses a linear absolute (L1) penalty, which does not blow up for large errors.
• This gives L1 Loss its **robustness**: it can tolerate extreme noise and outliers without destabilizing the fitted model.

1. Proof of Discrete Bayes' Rule & Total Probability

Let events $A_1, A_2, \dots, A_k$ partition the sample space (mutually exclusive and exhaustive). For any observable event $B$ with $P(B) > 0$:

$$P(A_i \mid B) = \frac{P(A_i \cap B)}{P(B)}$$

Using the conditional probability definition $P(A_i \cap B) = P(B \mid A_i)P(A_i)$ and expanding the denominator $P(B)$ using the Law of Total Probability:

$$P(B) = \sum_{j=1}^k P(B \mid A_j)P(A_j)$$

Substituting back yields the discrete Bayes' formula:

$$P(A_i \mid B) = \frac{P(B \mid A_i) P(A_i)}{\sum_{j=1}^k P(B \mid A_j) P(A_j)}$$

2. Continuous Case: Beta-Binomial Conjugacy for Parameter Estimation

Suppose we want to estimate the probability $\theta \in [0, 1]$ of a coin landing heads.

• Prior Distribution: Let $\theta$ follow a Beta distribution, $\theta \sim \text{Beta}(\alpha, \beta)$, with density: $$p(\theta) = \frac{1}{\text{B}(\alpha, \beta)} \theta^{\alpha - 1} (1-\theta)^{\beta - 1} \propto \theta^{\alpha - 1} (1-\theta)^{\beta - 1}$$
• Likelihood Function: We perform $n$ independent flips and observe $k$ heads and $n-k$ tails. Under a Binomial model: $$P(\mathcal{D} \mid \theta) = \binom{n}{k} \theta^k (1-\theta)^{n-k} \propto \theta^k (1-\theta)^{n-k}$$
• Posterior Distribution: Applying continuous Bayes' rule: $$p(\theta \mid \mathcal{D}) \propto P(\mathcal{D} \mid \theta) p(\theta) \propto \left[ \theta^k (1-\theta)^{n-k} \right] \cdot \left[ \theta^{\alpha - 1} (1-\theta)^{\beta - 1} \right] = \theta^{k+\alpha-1} (1-\theta)^{n-k+\beta-1}$$

This reveals that the posterior distribution is also a Beta distribution:

$$\theta \mid \mathcal{D} \sim \text{Beta}(\alpha + k, \beta + n - k)$$

Because the prior and posterior belong to the same probability family, Beta is the conjugate prior to the Binomial likelihood. This property allows analytical updates without numerical integration.

Proof of Posterior Variance Shrinkage as $n \to \infty$:

For $\text{Beta}(\alpha + k, \beta + n - k)$, the posterior expectation and variance are:

$$\mathbb{E}[\theta \mid \mathcal{D}] = \frac{\alpha + k}{\alpha + \beta + n}, \quad \text{Var}(\theta \mid \mathcal{D}) = \frac{(\alpha + k)(\beta + n - k)}{(\alpha + \beta + n)^2(\alpha + \beta + n + 1)}$$

As the number of samples $n \to \infty$, the prior parameters $\alpha, \beta$ are overwhelmed:

$$\lim_{n\to\infty} \mathbb{E}[\theta \mid \mathcal{D}] = \lim_{n\to\infty} \frac{k}{n} = \hat{\theta}_{\text{empirical}}$$

For the variance, the denominator is $O(n^3)$ while the numerator is at most $O(n^2)$:

$$\lim_{n\to\infty} \text{Var}(\theta \mid \mathcal{D}) \le \lim_{n\to\infty} \frac{n^2}{n^3} = \lim_{n\to\infty} O\left(\frac{1}{n}\right) = 0$$

This mathematically proves that as the observed data grows to infinity, our posterior expectation converges to the empirical frequency, and the uncertainty (variance) shrinks to 0.

1. The "Spotlight Focusing" Intuition of Bayesian Updates

Bayesian parameter estimation can be visualized as focusing a spotlight on a target value:

• Prior: A broad, dim wash of light cast onto the wall, representing our initial fuzzy guess about the parameters.
• Likelihood: Each incoming data point acts as a physical filter that blocks out parameter values that are highly inconsistent with the observed facts.
• Posterior: The shape of the light after passing through the filter. As data points pile up (multiplying filters), the fuzzy beam of light narrows and sharpens into a bright, precise laser point centered on the true parameter value.

2. The Base Rate Fallacy Explained via Grid Frequency

Why does a test with 99% accuracy on a rare disease (0.1% base rate) only result in a ~9% posterior probability of illness upon a positive result?

• Imagine a population of 100,000 people. With a base rate of 0.1%, only 100 people actually have the disease.
• If we test all 100,000 people: the 100 sick individuals will yield 99 positive tests (True Positives).
• Among the 99,900 healthy individuals, the 1% false positive rate will yield $99,900 \times 1\% \approx 999$ positive tests (False Positives).
• The total number of positive test results is $99 + 999 = 1,098$. Within this group, the probability of actually being sick is $99 / 1,098 \approx 9.01\%$.
• Physical Essence: Because the healthy population is so massive, even a tiny false positive rate produces an absolute number of misdiagnoses that dwarfs the entire pool of true patients.

1. Proof of Markov's Inequality

Let $X$ be a non-negative continuous random variable with PDF $p(x)$. For any constant $a > 0$, the expectation of $X$ is:

$$\mathbb{E}[X] = \int_{0}^{\infty} x p(x) \, dx$$

Split the domain of integration at $a$:

$$\mathbb{E}[X] = \int_{0}^{a} x p(x) \, dx + \int_{a}^{\infty} x p(x) \, dx$$

Since $X \ge 0$ and $p(x) \ge 0$, the first integral is non-negative: $\int_{0}^{a} x p(x) \, dx \ge 0$. Dropping it yields:

$$\mathbb{E}[X] \ge \int_{a}^{\infty} x p(x) \, dx$$

In the interval $[a, \infty)$, we have $x \ge a$. Replacing $x$ with the lower bound $a$ further reduces the integral:

$$\mathbb{E}[X] \ge \int_{a}^{\infty} a p(x) \, dx = a \int_{a}^{\infty} p(x) \, dx$$

By the definition of probability, the remaining integral is exactly $P(X \ge a)$:

$$\mathbb{E}[X] \ge a P(X \ge a) \implies P(X \ge a) \le \frac{\mathbb{E}[X]}{a}$$

Q.E.D.

2. Proof of Chebyshev's Inequality

Let $X$ have mean $\mu$ and variance $\sigma^2$. Define a new random variable $Y = (X - \mu)^2$.

Since $Y$ is a squared term, it is non-negative ($Y \ge 0$). The expectation of $Y$ is the variance of $X$:

$$\mathbb{E}[Y] = \mathbb{E}[(X - \mu)^2] = \text{Var}(X) = \sigma^2$$

Applying Markov's Inequality to $Y$ with threshold $t^2$ (for $t > 0$):

$$P(Y \ge t^2) \le \frac{\mathbb{E}[Y]}{t^2}$$

Substitute $Y = (X - \mu)^2$ and $\mathbb{E}[Y] = \sigma^2$ into the inequality:

$$P((X - \mu)^2 \ge t^2) \le \frac{\sigma^2}{t^2}$$

Since the events $(X-\mu)^2 \ge t^2$ and $|X-\mu| \ge t$ are logically equivalent:

$$P(|X - \mu| \ge t) \le \frac{\sigma^2}{t^2}$$

Q.E.D.

3. Proof Sketch of Hoeffding's Inequality (Chernoff Bound Method)

To prove Hoeffding's inequality, we employ the exponential Chernoff transform:

To bound the probability $P(S_n - \mathbb{E}[S_n] \ge z)$, we multiply by a parameter $s > 0$ and exponentiate both sides:

$$P(S_n - \mathbb{E}[S_n] \ge z) = P\left(e^{s(S_n - \mathbb{E}[S_n])} \ge e^{sz}\right)$$

Applying **Markov's Inequality** to the non-negative exponential term:

$$P(e^{s(S_n - \mathbb{E}[S_n])} \ge e^{sz}) \le e^{-sz} \mathbb{E}\left[ e^{s(S_n - \mathbb{E}[S_n])} \right]$$

Since $S_n = \sum X_i$ and the random variables $X_i$ are independent, the expectation of their product factors:

$$\mathbb{E}\left[ e^{s(S_n - \mathbb{E}[S_n])} \right] = \mathbb{E}\left[ \prod_{i=1}^n e^{s(X_i - \mathbb{E}[X_i])} \right] = \prod_{i=1}^n \mathbb{E}\left[ e^{s(X_i - \mathbb{E}[X_i])} \right]$$

Here, we apply Hoeffding's Lemma: for any random variable bounded in $[a, b]$:

$$\mathbb{E}\left[ e^{s(X_i - \mathbb{E}[X_i])} \right] \le \exp\left( \frac{s^2 (b_i - a_i)^2}{8} \right)$$

Substituting this back into the product expression:

$$P(S_n - \mathbb{E}[S_n] \ge z) \le e^{-sz} \prod_{i=1}^n \exp\left( \frac{s^2 (b_i - a_i)^2}{8} \right) = \exp\left( -sz + \frac{s^2 \sum_{i=1}^n (b_i - a_i)^2}{8} \right)$$

To find the tightest upper bound, we minimize the exponent with respect to $s > 0$. Differentiating and setting to zero yields the optimal value $s^* = \frac{4z}{\sum (b_i - a_i)^2}$. Plugging this back in yields the single-sided bound:

$$P(S_n - \mathbb{E}[S_n] \ge z) \le \exp\left( -\frac{2z^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$$

To estimate the sample mean, we set $\bar{X} = \frac{1}{n} S_n$ and $z = nt$. Symmetrizing for both tails yields the two-sided Hoeffding's inequality:

$$P(|\bar{X} - \mathbb{E}[\bar{X}]| \ge t) \le 2 \exp\left( -\frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$$

Q.E.D.

1. The Information-Bound Hierarchy

These three inequalities showcase how incorporating more information leads to tighter bounds:

• Markov (Mean only): We have minimal information. The bound relies solely on the centroid: to keep the center of mass in place, the distribution cannot place too much weight extremely far out. Because we know nothing about the shape, the bound decays slowly at a linear rate $O(1/t)$.
• Chebyshev (Mean & Variance): We gain information about the spread ($\sigma$). Knowing how much the distribution fluctuates around the mean forces the probability of large deviations to contract at a quadratic rate $O(1/t^2)$.
• Hoeffding's (Independence & Boundedness): The strongest assumption. Because the variables are **independent**, their fluctuations tend to cancel out. The Central Limit Theorem tells us that their sum concentrates tightly around the mean, yielding an **exponentially decaying** probability tail $\exp(-2nt^2)$.

2. The Generalization Gap Safety Rope

In machine learning, we calculate a model's empirical error $E_{\text{in}}$ on a test set, but we care about its true error $E_{\text{out}}$ on unseen data. Hoeffding's Inequality acts as a safety rope: it guarantees that as long as our test data is sampled independently, the probability of our test score lying far from the true generalization ability decays exponentially with the dataset size $n$. This is the foundation of **Probably Approximately Correct (PAC) Learning**.