ZoomNotes for Linear Algebra

Part 11: Basic Statistics: Mean, Variance, Covariance

11.1 Mean and Variance: Actual and Expected

Sample Mean:

$$\bar{\mu} = \frac{1}{N} \sum_{i=1}^N x_i$$

Expected (Population) Mean:

$$m = E[x] = \sum_i p_i x_i$$

where $p_i$ are probabilities with $\sum p_i = 1$.

Law of Large Numbers: As $N \to \infty$, the sample mean converges to the expected mean:

$$\bar{\mu} \to m$$

Sample Variance:

$$S^2 = \frac{1}{N-1} \sum_{i=1}^N (x_i - \bar{\mu})^2$$

The $N-1$ (instead of $N$) is Bessel's correction for unbiased estimation.

Population Variance:

$$\sigma^2 = E[(x - m)^2] = \sum_i p_i (x_i - m)^2 = (\sum_i p_i x_i^2) - m^2$$

Standard Deviation: $\sigma = \sqrt{\sigma^2}$ (same units as the data).

---

11.2 Probability Distributions: Binomial, Poisson, Normal

Binomial Distribution: $\text{Bin}(n, p)$ models the number of successes in $n$ independent trials, each with success probability $p$.

$$P(k \text{ successes}) = \binom{n}{k} p^k (1-p)^{n-k}, \quad k = 0, 1, \dots, n$$

• Mean: $\mu = np$
• Variance: $\sigma^2 = np(1-p)$

Poisson Distribution: The limit of Binomial as $n \to \infty$, $p \to 0$, with $np \to \lambda$ (fixed). Models rare events.

$$P(k \text{ events}) = \frac{\lambda^k e^{-\lambda}}{k!}, \quad k = 0, 1, 2, \dots$$

• Mean: $\mu = \lambda$
• Variance: $\sigma^2 = \lambda$ (mean equals variance!)

Normal (Gaussian) Distribution: $\mathcal{N}(m, \sigma^2)$

$$p(x) = \frac{1}{\sqrt{2\pi\sigma^2}} \exp\left(-\frac{(x-m)^2}{2\sigma^2}\right)$$

Standard Normal: $\mathcal{N}(0,1)$ with $p(x) = \frac{1}{\sqrt{2\pi}} e^{-x^2/2}$.

Central Limit Theorem (CLT): The average of $N$ independent samples from any distribution (with finite mean $m$ and variance $\sigma^2$) approaches a normal distribution as $N \to \infty$:

$$\frac{\bar{x} - m}{\sigma/\sqrt{N}} \to \mathcal{N}(0,1)$$

The CLT is why the normal distribution appears everywhere in statistics.

---

11.3 Covariance Matrices and Joint Probabilities

Covariance measures how two variables vary together:

$$\text{Cov}(X,Y) = E[(X - E[X])(Y - E[Y])] = E[XY] - E[X]E[Y]$$

• Positive covariance: $X$ and $Y$ tend to increase together
• Negative covariance: one increases as the other decreases
• Zero covariance: no linear relationship (but doesn't imply independence)

Covariance Matrix $V$ for a random vector $X = (X_1, \dots, X_n)^T$:

$$V = E[(X - m)(X - m)^T]$$

where $m = E[X]$. Entry $(i,j)$ is $\text{Cov}(X_i, X_j)$. Diagonal entries are variances $\text{Var}(X_i) = \sigma_i^2$.

Properties of Covariance Matrices:

• $V$ is symmetric and positive semidefinite
• $V = \sum$ of rank-1 positive semidefinite matrices
• $V$ is positive definite iff the variables are linearly independent
• For independent variables, $V$ is diagonal (covariances are zero)

Multivariate Normal Distribution:

$$p(\mathbf{x}) = \frac{1}{\sqrt{(2\pi)^n \det V}} \exp\left(-\frac{1}{2} (\mathbf{x} - \mathbf{m})^T V^{-1} (\mathbf{x} - \mathbf{m})\right)$$

The contours of constant probability are ellipsoids defined by $(\mathbf{x} - \mathbf{m})^T V^{-1} (\mathbf{x} - \mathbf{m}) = \text{constant}$, with axes aligned with the eigenvectors of $V$ and axis lengths proportional to $\sqrt{\lambda_i}$.

---

11.4 Three Basic Inequalities of Statistics

1. Markov's Inequality: For a nonnegative random variable $X \geq 0$ and $a > 0$:

$$P(X \geq a) \leq \frac{E[X]}{a}$$

This gives a crude bound on tail probabilities using only the mean.

2. Chebyshev's Inequality: For any random variable $X$ with mean $m$ and variance $\sigma^2$:

$$P(|X - m| \geq a) \leq \frac{\sigma^2}{a^2}$$

This bounds the probability of being far from the mean using only the variance. It implies that most probability mass lies within a few standard deviations of the mean.

3. Chernoff's Inequality: For a sum $S = \sum_{i=1}^n X_i$ of independent random variables:

$$P(|S - E[S]| \geq t) \leq 2 \exp\left(-\frac{t^2}{2\sum \text{Var}(X_i)}\right)$$

This gives exponential tail bounds, which are much sharper than Chebyshev (which only gives $1/a^2$ decay). Chernoff bounds are essential for understanding the concentration of measure phenomenon and are the foundation for PAC learning theory.

---

11.5 Markov Matrices and Markov Chains

A Markov matrix (also called a stochastic matrix) $M$ satisfies:

• $M_{ij} \geq 0$ (all entries nonnegative)
• Each column sums to 1 (the probability leaving a state is distributed to other states)

Perron-Frobenius Theorem:

• The largest eigenvalue is $\lambda_{\max} = 1$
• All other eigenvalues satisfy $|\lambda| \leq 1$
• If all entries are positive (not just nonnegative), then $|\lambda| < 1$ for all $\lambda \neq 1$
• The eigenvector for $\lambda = 1$ has all positive entries (up to scaling)

Markov Chain: A sequence of probability vectors evolving as:

$$p_{n+1} = M p_n = M^n p_0$$

Each entry $p_n(i)$ is the probability of being in state $i$ at step $n$.

Steady State: The stationary distribution $\pi$ satisfies:

$$M \pi = \pi$$

i.e., $\pi$ is the eigenvector of $M$ corresponding to $\lambda = 1$, scaled so that its entries sum to 1.

Convergence to Steady State: The distance from $p_n$ to $\pi$ decays at a rate governed by the second eigenvalue $\lambda_2$:

$$\|p_n - \pi\| \approx |\lambda_2|^n \|p_0 - \pi\|$$

The spectral gap $1 - |\lambda_2|$ determines the mixing time of the Markov chain. A larger gap means faster convergence.

Applications: Markov chains model random processes across physics, chemistry, economics, and computer science -- from Google's PageRank algorithm to Monte Carlo simulations.