The Lumenary · Early undergraduate

Probability theory

Name: ______________________

Date: ______________________

You will learn to

Define random variables, distributions and expectation, and compute means and variances of the binomial, geometric, Poisson, uniform, exponential and normal distributions
Use linearity of expectation and indicator variables, including for dependent events
Work with joint distributions, independence and covariance, and know exactly when $E[XY] = E[X]E[Y]$ and $\operatorname{Var}(X + Y) = \operatorname{Var} X + \operatorname{Var} Y$
Prove Markov's and Chebyshev's inequalities and the weak law of large numbers
State the central limit theorem precisely, use the normal approximation, and explain what the theorem does not say

1.
You roll a fair die until the first six appears. What is the expected number of rolls, including the roll that shows the six?
2.
A fair coin is flipped $41$ times. A double is a position $i$ ( $1 \le i \le 40$ ) where flips $i$ and $i + 1$ are both heads; overlapping doubles count separately (HHH contains two). What is the expected number of doubles?
3.
In which of these situations is $E[XY] = E[X]\,E[Y]$ guaranteed? (All variables have finite variance. Choose all that apply.)
- A. $X$ and $Y$ are independent
- B. $\operatorname{Cov}(X, Y) = 0$
- C. $X$ and $Y$ have the same distribution
- D. $E[X + Y] = E[X] + E[Y]$
4.
Let $S$ be the number of heads in $400$ flips of a fair coin. What is the smallest $c$ for which Chebyshev's inequality guarantees $P(|S - 200| \ge c) \le \tfrac14$ ?
5.
The proof of the weak law of large numbers has four steps: (1) $E[\bar X_n] = \mu$ ; (2) $\operatorname{Var} \bar X_n = \sigma^2/n$ ; (3) apply Chebyshev's inequality to $\bar X_n$ ; (4) let $n \to \infty$ . Which step uses the hypothesis that the $X_i$ are pairwise uncorrelated?
- A.Step 1
- B.Step 2
- C.Step 3
- D.Step 4
6.
Which statement is a correct consequence of the central limit theorem?
- A.A large enough sample from any population has a histogram that looks like a normal curve.
- B.If $X_1, X_2, \dots$ are i.i.d. with finite variance $\sigma^2 > 0$ , then $P\big((S_n - n\mu)/(\sigma\sqrt n) \le x\big) \to \Phi(x)$ for every $x$ .
- C.Averages of independent Cauchy variables become approximately normal for large $n$ .
- D.For $n \ge 30$ the standardised sum has exactly the normal distribution.
7.
Ten letters are put into ten addressed envelopes uniformly at random. Let $N$ be the number of letters in the right envelope. What is $\operatorname{Var} N$ ?
- A. $0.9$
- B. $1$
- C. $10$
- D. $1/e$
8.
Which Lean statement correctly formalises Chebyshev's inequality $c^2\,P(|X - E X| \ge c) \le \operatorname{Var} X$ ? (Here μ is a probability measure, μ[X] is $E X$ and Var[X; μ] is $\operatorname{Var} X$ .)
- A.theorem (hX : MemLp X 2 μ) {c : ℝ} (hc : 0 < c) : c ^ 2 * μ.real {ω | c ≤ |X ω - μ[X]|} ≤ Var[X; μ]
- B.theorem (hX : MemLp X 2 μ) {c : ℝ} : c ^ 2 * μ.real {ω | c ≤ |X ω - μ[X]|} ≤ Var[X; μ]
- C.theorem (hX : MemLp X 2 μ) {c : ℝ} (hc : 0 < c) : c ^ 2 * μ.real {ω | c ≤ |X ω - μ[X]|} ≥ Var[X; μ]
- D.theorem (hX : MemLp X 2 μ) {c : ℝ} (hc : 0 < c) : c * μ.real {ω | c ≤ |X ω - μ[X]|} ≤ Var[X; μ]
9.
Write tail(n, k) returning the exact probability, as a Fraction, that the number of heads $S$ in $n$ fair coin flips satisfies $|S - n/2| \ge k$ . Then write chebyshev(n, k) returning Chebyshev's bound $\frac{n/4}{k^2}$ as a Fraction. The tests check that the bound always holds and is far from sharp for large $n$ .
Computational — Practice

Answer key — Probability theory

1.
The number of rolls $X$ is geometric with $p = \tfrac16$ : $P(X = k) = (\tfrac56)^{k-1}\tfrac16$ for $k \ge 1$ . Differentiating the geometric series gives $E[X] = \sum_k k\,q^{k-1}p = p/(1-q)^2 = 1/p = 6$ .
2.
Let $A_i$ be the event that flips $i$ and $i+1$ are both heads, so $P(A_i) = \tfrac14$ . The number of doubles is $D = \sum_{i=1}^{40} \mathbf 1_{A_i}$ , and by linearity $E[D] = 40 \cdot \tfrac14 = 10$ . The events $A_i$ and $A_{i+1}$ are dependent (both need flip $i+1$ to be heads), but linearity of expectation holds regardless.
3.
$E[XY] - E[X]E[Y] = \operatorname{Cov}(X, Y)$ , so the identity holds exactly when $X$ and $Y$ are uncorrelated. Independence implies this (product rule). Equal distributions do not ( $X = Y$ a fair coin indicator gives $\tfrac12 \ne \tfrac14$ ), and linearity of expectation holds for every pair, so it guarantees nothing.
4.
$\operatorname{Var} S = 400 \cdot \tfrac12 \cdot \tfrac12 = 100$ , so Chebyshev gives $P(|S - 200| \ge c) \le 100/c^2$ , which is $\le \tfrac14$ exactly when $c^2 \ge 400$ , i.e. $c \ge 20$ (two standard deviations, $k = 2$ , $1/k^2 = \tfrac14$ ). The true probability is much smaller: by the normal approximation, $P(|S - 200| \ge 20) \approx P(|Z| \ge 1.95) \approx 0.05$ .
5.
Only step 2. Without uncorrelatedness, $\operatorname{Var}\bar X_n = \frac{1}{n^2}\big(n\sigma^2 + 2\sum_{i<j}\operatorname{Cov}(X_i, X_j)\big)$ , which need not tend to $0$ : if all $X_i$ equal $X_1$ , then $\bar X_n = X_1$ for every $n$ and the law of large numbers fails.
6.
Only the second statement is right. The CLT concerns the distribution of the standardised sum $(S_n - n\mu)/(\sigma\sqrt n)$ of i.i.d. variables with finite positive variance, and it gives convergence, not exactness at any finite $n$ . Data themselves keep their own distribution, and without finite variance (Cauchy) the conclusion fails.
7.
Each indicator has variance $\tfrac1{10}\cdot\tfrac9{10} = 0.09$ , total $0.9$ . For $i \ne j$ , $\operatorname{Cov}(\mathbf 1_{A_i}, \mathbf 1_{A_j}) = \frac1{90} - \frac1{100} = \frac{1}{900}$ , and there are $10 \cdot 9 = 90$ ordered pairs, contributing $0.1$ . So $\operatorname{Var} N = 0.9 + 0.1 = 1$ — the same for every $n \ge 2$ , as the lesson shows and the experiment checks for $n \le 7$ .
8.
Statement (a) is right. (b) drops the hypothesis $c > 0$ , and fails for negative $c$ ; (c) reverses the inequality; (d) has $c$ instead of $c^2$ and fails for $X = \pm\tfrac12$ (each with probability $\tfrac12$ ) and $c = \tfrac12$ : the left side is $\tfrac12 \cdot 1 = \tfrac12$ but $\operatorname{Var} X = \tfrac14$ . In Lean, μ.real s is the probability of s as a real number.
9.
```
from fractions import Fraction
from math import comb

def tail(n, k):
    count = sum(comb(n, s) for s in range(n + 1) if abs(2 * s - n) >= 2 * k)
    return Fraction(count, 2 ** n)

def chebyshev(n, k):
    return Fraction(n, 4 * k * k)
```
The variance of $S$ is $n/4$ , so Chebyshev gives $P(|S - n/2| \ge k) \le \frac{n}{4k^2}$ . For $n = 400$ , $k = 40$ (four standard deviations) the bound is $\frac1{16}$ , while the exact tail is about $7 \times 10^{-5}$ : Chebyshev uses only the variance, so it must allow for the worst distribution with that variance.