Lecture 20: Definitions and Inequalities

What this lecture covers

This lecture continues the course's probability and statistics unit, building the tools needed before moving to gradient descent and deep learning. It develops the expected value and variance in terms of probabilities, proves two classical bounds on probability (Markov's and Chebyshev's inequalities), and then constructs the covariance matrix from joint probabilities of multiple experiments run together.

By the end you should be able to compute expected value and variance from a probability distribution, state and apply Markov's and Chebyshev's inequalities, and explain how the covariance matrix captures dependence between two or more experiments, including why it is always positive semidefinite.

Key ideas

• Expected value: E[X] = sum(P_i * X_i), the probability-weighted average of all possible outcomes, distinct from a sample average computed from actual trials.
• Variance, two equivalent forms: Var(X) = E[(X - M)^2], which algebraically simplifies to E[X^2] - M^2, a form that is often faster to compute.
• Markov's inequality: for X >= 0, P(X >= a) <= E[X] / a; proved directly from the definition of the mean by isolating the probabilities of outcomes at or above a.
• Chebyshev's inequality: P(|X - M| >= a) <= Sigma^2 / a^2, derived by applying Markov's inequality to the nonnegative variable Y = (X - M)^2.
• Joint probabilities: when two experiments happen together, their joint outcomes form a probability matrix (or, for three experiments, a tensor); the row and column sums of this matrix recover the individual ("marginal") probabilities.
• Covariance matrix construction: V_ij = sum over outcomes of P_ij * (X_i - mean_X)(Y_j - mean_Y), giving a symmetric matrix whose diagonal entries are the individual variances.
• Independence vs. dependence: independent experiments (unglued coins) give a diagonal covariance matrix with zero off-diagonal covariance; fully dependent experiments (glued coins) give a singular, positive semidefinite matrix.

Walkthrough

Expected value and two forms of variance (1:01)

Strang reviews the expected value E[X] as a probability-weighted sum, then defines variance as E[(X-M)^2] and works through the algebra to show it equals E[X^2] - M^2, a computationally convenient alternative.

Markov's inequality (8:12)

For nonnegative outcomes, Markov's inequality bounds P(X >= a) by E[X]/a. Strang proves this with a concrete numeric example (outcomes 1 through 5, mean equal to 1, bounding P(X >= 3) by 1/3), showing the bound falls out directly from the probabilities summing to 1 and all being nonnegative.

Chebyshev's inequality (21:39)

Chebyshev's inequality, P(|X - M| >= a) <= Sigma^2/a^2, drops the nonnegativity requirement on X by instead applying Markov's inequality to the new nonnegative variable Y = (X - M)^2, whose mean is exactly the variance Sigma^2.

Joint probabilities and tensors (30:08)

Using the example of two coins flipped together, Strang builds a 2x2 matrix of joint probabilities, contrasting the "unglued" independent case (each entry 1/4) with the "glued" fully dependent case (probability 1/2 on the matching outcomes, 0 elsewhere). Extending to three coins introduces the idea of a probability tensor, a three-way array of joint probabilities.

Building the covariance matrix (43:25)

The covariance matrix is defined entry by entry as a probability-weighted sum of products of deviations from the mean, (X_i - mean_X)(Y_j - mean_Y). Strang shows its diagonal entries reduce to the ordinary variances of each experiment, and that it is always symmetric and positive semidefinite, since it is built from probability-weighted rank-one (column times row) pieces.

Independence and dependence in the covariance matrix (52:37)

The lecture closes by contrasting the two coin-flip scenarios: independent coins give a diagonal covariance matrix, while fully glued coins give a singular covariance matrix, illustrating how the off-diagonal covariance terms capture dependence between experiments.

Before you watch

• Review the sample mean, expected mean, and sample variance from the previous lecture, since this lecture builds directly on them.
• Basic familiarity with probability distributions (discrete outcomes with associated probabilities) is assumed.

Check your understanding

1. Why must Markov's inequality require all outcomes to be nonnegative, while Chebyshev's inequality does not?
2. How does Chebyshev's inequality follow from Markov's inequality applied to a new variable?
3. What does the off-diagonal entry of a 2x2 covariance matrix measure, and why is it zero for independent experiments?
4. Why is the covariance matrix always positive semidefinite?