Expectation and Variance

Expectation and variance are two fundamental concepts in probability theory that describe the central tendency and spread of a random variable's distribution.

Throughout, identities between finite expectations assume integrability: $E|X|<\infty$, and variance/covariance formulas assume finite second moments. A nonnegative expectation may be $+\infty$, but subtraction of infinities is not allowed. The continuous formulas below use measurable functions and the usual integral rules.

Expected Value (Mean)

The expected value, also known as the mean or expectation, represents the average value of a random variable over many trials.

For Discrete Random Variables

$$\mathbb{E}[X] = \mu_X = \sum_{x} x \cdot p_X(x)$$

where:

• $p_X(x)$ is the probability mass function (PMF)
• The sum is taken over all possible values of $X$

Properties:

• Linearity and Homogeneity: $\mathbb{E}[aX + b] = a\mathbb{E}[X] + b$
• For two random variables: $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$
• For independent random variables: $\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$

Proofs of Key Properties

ProofLinearity

For $a, b \in \mathbb{R}$

$$\begin{aligned} \mathbb{E}[aX + b] &= \sum_{x} (ax + b) \cdot p_X(x) \\ &= a\sum_{x} x \cdot p_X(x) + b\sum_{x} p_X(x) \\ &= a\mathbb{E}[X] + b \end{aligned}$$

ProofAdditivity

$$\begin{aligned} \mathbb{E}[X + Y] &= \sum_{x}\sum_{y} (x + y) \cdot p_{X,Y}(x,y) \\ &= \sum_{x}\sum_{y} x \cdot p_{X,Y}(x,y) + \sum_{x}\sum_{y} y \cdot p_{X,Y}(x,y) \\ &= \mathbb{E}[X] + \mathbb{E}[Y] \end{aligned}$$

ProofProduct for Independent Variables

If $X$ and $Y$ are independent, then $p_{X,Y}(x,y) = p_X(x)p_Y(y)$, so:

$$\begin{aligned} \mathbb{E}[XY] &= \sum_{x}\sum_{y} xy \cdot p_{X,Y}(x,y) \\ &= \sum_{x}\sum_{y} xy \cdot p_X(x)p_Y(y) \\ &= \left(\sum_{x} x p_X(x)\right)\left(\sum_{y} y p_Y(y)\right) \\ &= \mathbb{E}[X]\mathbb{E}[Y] \end{aligned}$$

For Continuous Random Variables

$$\mathbb{E}[X] = \mu_X = \int_{-\infty}^{\infty} x \cdot f_X(x)dx$$

where:

• $f_X(x)$ is the probability density function (PDF)

Variance

Variance measures how much the values of a random variable deviate from its mean.

DefinitionVariance

$$\mathbb{V}(X) = \sigma_X^2 = \mathbb{E}[(X - \mu_X)^2] = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$$

These illustrative distributions have the same mean but different spreads, hence different variances.

For Discrete Random Variables

$$\mathbb{V}(X) = \sum_{x} (x - \mu_X)^2 \cdot p_X(x)$$

For Continuous Random Variables

$$\mathbb{V}(X) = \int_{-\infty}^{\infty} (x - \mu_X)^2 \cdot f_X(x)dx$$

Standard Deviation

The standard deviation is the square root of the variance:

$$\sigma_X = \sqrt{\mathbb{V}(X)}$$

Properties of Variance

• $\mathbb{V}(X) \geq 0$
• $\mathbb{V}(a) = 0$ for any constant $a$
• $\mathbb{V}(aX) = a^2 \mathbb{V}(X)$
• $\mathbb{V}(X + a) = \mathbb{V}(X)$
• For independent random variables: $\mathbb{V}(X + Y) = \mathbb{V}(X) + \mathbb{V}(Y)$

Proofs of Variance Properties

ProofScaling

For $a \in \mathbb{R}$

$$\begin{aligned} \mathbb{V}(aX) &= \mathbb{E}[(aX - \mathbb{E}[aX])^2] \\ &= \mathbb{E}[(aX - a\mathbb{E}[X])^2] \\ &= \mathbb{E}[a^2(X - \mathbb{E}[X])^2] \\ &= a^2\mathbb{E}[(X - \mathbb{E}[X])^2] \\ &= a^2\mathbb{V}(X) \end{aligned}$$

ProofShift Invariance

$$\begin{aligned} \mathbb{V}(X + a) &= \mathbb{E}[(X + a - \mathbb{E}[X + a])^2] \\ &= \mathbb{E}[(X + a - \mathbb{E}[X] - a)^2] \\ &= \mathbb{E}[(X - \mathbb{E}[X])^2] \\ &= \mathbb{V}(X) \end{aligned}$$

ProofAdditivity for Independent Variables

If $X$ and $Y$ are independent:

$$\begin{aligned} \mathbb{V}(X + Y) &= \mathbb{E}[(X + Y)^2] - (\mathbb{E}[X + Y])^2 \\ &= \mathbb{E}[X^2 + 2XY + Y^2] - (\mathbb{E}[X] + \mathbb{E}[Y])^2 \\ &= \mathbb{E}[X^2] + 2\mathbb{E}[X]\mathbb{E}[Y] + \mathbb{E}[Y^2] - \mathbb{E}[X]^2 - 2\mathbb{E}[X]\mathbb{E}[Y] - \mathbb{E}[Y]^2 \\ &= (\mathbb{E}[X^2] - \mathbb{E}[X]^2) + (\mathbb{E}[Y^2] - \mathbb{E}[Y]^2) \\ &= \mathbb{V}(X) + \mathbb{V}(Y) \end{aligned}$$

ProofSecond-moment identity and zero variance

Put $\mu=E[X]$. Expansion and linearity give $E[(X-\mu)^2]=E[X^2]-2\mu E[X]+\mu^2=E[X^2]-\mu^2$. Nonnegativity follows from the squared integrand. A constant has zero centered square. Conversely, if the expectation of that square is zero, each event $\{|X-\mu|\ge1/k\}$ has probability zero by the pointwise lower bound $(X-\mu)^2\ge k^{-2}$ on the event. Their countable union is $\{X\ne\mu\}$, so zero variance means $X=\mu$ almost surely.

Examples

ExampleDiscrete Case (Die Roll)

For a fair six-sided die:

• PMF: $p_X(x) = \frac{1}{6}$ for $x \in \{1, 2, 3, 4, 5, 6\}$

Expected Value:

$$\mathbb{E}[X] = \sum_{x=1}^{6} x \cdot \frac{1}{6} = \frac{1+2+3+4+5+6}{6} = \frac{21}{6} = 3.5$$

Variance:

$$\mathbb{E}[X^2] = \sum_{x=1}^{6} x^2 \cdot \frac{1}{6} = \frac{1+4+9+16+25+36}{6} = \frac{91}{6}$$$$\mathbb{V}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = \frac{91}{6} - (3.5)^2 = \frac{91}{6} - \frac{49}{4} = \frac{182 - 147}{12} = \frac{35}{12} \approx 2.92$$

ExampleContinuous Case (Normal Distribution)

For $X \sim N(\mu, \sigma^2)$:

• PDF: $f_X(x) = \frac{1}{\sigma\sqrt{2\pi}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}$

Expected Value: $\mathbb{E}[X] = \mu$

Variance: $\mathbb{V}(X) = \sigma^2$

ExampleContinuous Case (Uniform Distribution)

For $X \sim U(a, b)$:

• PDF: $f_X(x) = \frac{1}{b-a}$ for $a \leq x \leq b$

Expected Value:

$$\mathbb{E}[X] = \int_a^b x \cdot \frac{1}{b-a} dx = \frac{a+b}{2}$$

Variance:

$$\mathbb{V}(X) = \int_a^b \left(x - \frac{a+b}{2}\right)^2 \cdot \frac{1}{b-a} dx = \frac{(b-a)^2}{12}$$

Expectation of Functions of Random Variables

When we apply a function to a random variable, we obtain a new random variable. Computing the expectation of this new random variable is a fundamental problem in probability theory.

Law of the Unconscious Statistician (LOTUS)

The core principle for computing expectations of functions of random variables is the Law of the Unconscious Statistician (LOTUS). This law states that to compute $\mathbb{E}[g(X)]$, we don't need to first find the distribution of $g(X)$. Instead, we can work directly with the original distribution of $X$.

Computation Formula

For a function $g: \mathbb{R} \to \mathbb{R}$ and random variable $X$, the expectation of $g(X)$ is:

$$\mathbb{E}[g(X)] = \begin{cases} \sum_{x} g(x) \cdot p_X(x) & \text{(discrete)} \\ \int_{-\infty}^{\infty} g(x) \cdot f_X(x) dx & \text{(continuous)} \end{cases}$$

Important Properties

1. Linearity: $\mathbb{E}[a \cdot g(X) + b \cdot h(X)] = a\mathbb{E}[g(X)] + b\mathbb{E}[h(X)]$
2. Monotonicity: If $g(x) \leq h(x)$ for all $x$, then $\mathbb{E}[g(X)] \leq \mathbb{E}[h(X)]$

ProofLOTUS and monotonicity

In the discrete case, group values by $y=g(x)$. Since $P(g(X)=y)=\sum_{x:g(x)=y}p_X(x)$, substitution in $E[g(X)]$ and regrouping gives $\sum_x g(x)p_X(x)$. Regrouping is valid for nonnegative terms or an absolutely convergent sum.

For a density, first take an indicator $g=\mathbf1_B$: both sides equal $P(X\in B)=\int_B f_X$. Linearity gives the claim for simple functions, finite linear combinations of indicators. Approximate a nonnegative measurable $g$ increasingly by simple functions and apply monotone convergence; for integrable signed $g$, subtract positive and negative parts. This proof uses the monotone convergence theorem as an integration prerequisite, whose general proof is not yet in the calculus notes. The same argument works for joint distributions. Finally $h-g\ge0$ implies $E[h(X)]-E[g(X)]\ge0$, proving monotonicity whenever the difference is defined.

Application Examples

ExampleExpectation of Square Function

For any random variable $X$, computing $\mathbb{E}[X^2]$:

• Discrete case: $\mathbb{E}[X^2] = \sum_{x} x^2 \cdot p_X(x)$
• Continuous case: $\mathbb{E}[X^2] = \int_{-\infty}^{\infty} x^2 \cdot f_X(x) dx$

This result gives the standard variance formula: $\mathbb{V}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2$

ExampleExpectation of Exponential Function

For any random variable $X$, computing $\mathbb{E}[e^{tX}]$:

• Discrete case: $\mathbb{E}[e^{tX}] = \sum_{x} e^{tx} \cdot p_X(x)$
• Continuous case: $\mathbb{E}[e^{tX}] = \int_{-\infty}^{\infty} e^{tx} \cdot f_X(x) dx$

This is the definition of the moment generating function, which has wide applications in probability theory.

Numerical Estimation Methods

When functions are complex or distributions are non-standard, analytical solutions may be difficult to obtain. In such cases, we can use Taylor series approximation for numerical estimation.

Taylor Series Approximation Method

For a random variable $X$ with mean $\mu$ and variance $\sigma^2$, the expectation and variance of $f(X)$ can be approximated using Taylor expansion.

ProofApproximation Derivation for Expectation

1. Perform second-order Taylor expansion of $f(X)$ around $\mu$:

$$f(X) = f(\mu) + f'(\mu)(X-\mu) + \frac{f''(\mu)}{2}(X-\mu)^2 + R_2$$

where $R_2$ is the remainder term.

2. Take expectation of both sides:

$$\mathbb{E}[f(X)] = \mathbb{E}[f(\mu)] + \mathbb{E}[f'(\mu)(X-\mu)] + \mathbb{E}\left[\frac{f''(\mu)}{2}(X-\mu)^2\right] + \mathbb{E}[R_2]$$

3. Since $f(\mu)$, $f'(\mu)$, and $f''(\mu)$ are constants:

$$\mathbb{E}[f(X)] = f(\mu) + f'(\mu)\mathbb{E}[X-\mu] + \frac{f''(\mu)}{2}\mathbb{E}[(X-\mu)^2] + \mathbb{E}[R_2]$$

4. Using $\mathbb{E}[X-\mu] = 0$ and $\mathbb{E}[(X-\mu)^2] = \sigma^2$, and ignoring higher-order remainder terms:

$$\mathbb{E}[f(X)] \approx f(\mu) + \frac{f''(\mu)}{2}\sigma^2$$

ProofApproximation Derivation for Variance

1. Use first-order Taylor expansion (usually sufficient for variance calculation):

$$f(X) \approx f(\mu) + f'(\mu)(X-\mu)$$

2. Since $f(\mu)$ is constant, it doesn't affect variance:

$$\mathbb{V}[f(X)] \approx \mathbb{V}[f'(\mu)(X-\mu)]$$

3. Constant factors can be factored out:

$$\mathbb{V}[f(X)] \approx [f'(\mu)]^2 \mathbb{V}[X-\mu]$$

4. Since $\mathbb{V}[X-\mu] = \mathbb{V}[X] = \sigma^2$:

$$\mathbb{V}[f(X)] \approx [f'(\mu)]^2 \sigma^2$$

Summary Formulas:

$$\begin{aligned} \mathbb{E}\left[f(X)\right] &\approx f(\mu) + f''(\mu)\frac{\sigma^2}{2} \\ \mathbb{V}\left[f(X)\right] &\approx \left(f'(\mu)\right)^2\sigma^2 \end{aligned}$$

Approximation Accuracy Notes

• The expectation approximation uses second-order expansion, providing higher accuracy
• The variance approximation uses first-order expansion; for strongly nonlinear functions, higher-order terms may be needed
• When $f(X)$ is a linear function, the approximation is exact
• Approximation quality depends on the remainder bounds below.

A small variance alone does not control Taylor remainders. If $|f^{(3)}|\le M$ on every segment between $\mu$ and a possible value of $X$, Taylor's remainder gives

$$\left|E[f(X)]-f(\mu)-\tfrac12f''(\mu)\sigma^2\right| \le\frac{M}{6}E|X-\mu|^3.$$

For the linear approximation write $f(X)=f(\mu)+L+R$, with $L=f'(\mu)(X-\mu)$. When the terms have finite second moments, covariance expansion and Cauchy–Schwarz give

$$|\operatorname{Var}(f(X))-\operatorname{Var}(L)| \le2\sqrt{\operatorname{Var}(L)\operatorname{Var}(R)}+\operatorname{Var}(R).$$

These bounds state the actual quantities that must be small; concentration without derivative and tail control does not guarantee accuracy.

Covariance and Correlation

When working with multiple random variables, we often want to measure their relationship.

Covariance

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

Correlation Coefficient

$$\rho_{X,Y} = \frac{\text{Cov}(X,Y)}{\sigma_X \sigma_Y}$$

Properties:

• $-1 \leq \rho_{X,Y} \leq 1$
• $\rho = 1$: Perfect positive linear relationship
• $\rho = -1$: Perfect negative linear relationship
• $\rho = 0$: No linear relationship (but may have non-linear relationship)

ProofCovariance and the correlation bound

Expanding centered products gives $\operatorname{Cov}(X,Y)=E[XY]-E[X]E[Y]$ and

$$\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)+2\operatorname{Cov}(X,Y).$$

For $U=X-E[X]$ and $V=Y-E[Y]$, nonnegativity of $E[(U-tV)^2]$ at $t=E[UV]/E[V^2]$ gives $E[UV]^2\le E[U^2]E[V^2]$. Thus $|\rho|\le1$ when both variances are positive. Equality is equivalent to $U=tV$ almost surely by the zero-variance argument. Positive $t$ gives $\rho=1$, negative $t$ gives $\rho=-1$. With a zero variance, correlation is undefined.

Independence gives zero covariance by the product formula. The converse fails: if $X$ is uniform on $\{-1,0,1\}$ and $Y=X^2$, then $E[X]=E[X^3]=0$, so covariance is zero, yet $Y$ is determined by $X$ and is not constant.

Common Distributions and Their Moments

Distribution	Expected Value	Variance
Bernoulli(p)	$p$	$p(1-p)$
Binomial(n,p)	$np$	$np(1-p)$
Poisson(λ)	$\lambda$	$\lambda$
Uniform(a,b)	$\frac{a+b}{2}$	$\frac{(b-a)^2}{12}$
Normal(μ,σ²)	$\mu$	$\sigma^2$
Exponential(λ)	$\frac{1}{\lambda}$	$\frac{1}{\lambda^2}$

Important Theorems

TheoremLaw of Large Numbers

For i.i.d. random variables $X_1, X_2, ..., X_n$ with mean $\mu$:

$$\frac{1}{n}\sum_{i=1}^{n} X_i \xrightarrow{P} \mu \text{ as } n \to \infty$$

This chapter uses the finite-variance version: an infinite i.i.d. sequence with $E[X_i]=\mu$ and $\operatorname{Var}(X_i)<\infty$. Its complete Chebyshev proof is given in the weak-law note. A finite first moment alone also suffices for the general i.i.d. weak law, but that requires a truncation argument beyond the displayed variance proof.

TheoremCentral Limit Theorem

For i.i.d. random variables with mean $\mu$ and variance $\sigma^2$:

$$\frac{\sum_{i=1}^{n} X_i - n\mu}{\sigma\sqrt{n}} \xrightarrow{D} N(0,1) \text{ as } n \to \infty$$

The assumptions here are an infinite i.i.d. sequence and $0<\sigma^2<\infty$. For zero variance the displayed normalization is undefined. A proof via characteristic functions expands the standardized one-variable transform as $1-t^2/2+o(t^2)$, takes its $n$-th power at $t/\sqrt n$ to obtain $e^{-t^2/2}$, and then applies Lévy's continuity theorem. That last theorem and the expansion under a finite second moment are not established in this collection yet; this statement records a dependency for the planned probability-limit chapter, not a completed proof.

Expectation with Multiple Random Variables

When working with functions of multiple random variables, we need to understand how to compute their expectations.

Expectation of Functions of Multiple Variables

For a function $g(X,Y)$ of two random variables, the expectation is computed using the joint distribution:

$$\mathbb{E}[g(X,Y)] = \begin{cases} \sum_{x}\sum_{y} g(x,y) \cdot p_{X,Y}(x,y) & \text{(discrete)} \\ \iint_{\mathbb{R}^2} g(x,y) \cdot f_{X,Y}(x,y) dx dy & \text{(continuous)} \end{cases}$$

Key Properties

From this definition, we derive important properties:

1. Linearity: $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ (always holds)
2. Products: $\mathbb{E}[XY] = \mathbb{E}[X]\mathbb{E}[Y]$ (holds only when X and Y are independent)

Computing Expectations from Joint Distributions

Geometric Interpretation for Continuous Case

For a joint probability density function $f(x,y)$, computing $\mathbb{E}[X]$ involves integrating over the entire plane:

$$\mathbb{E}[X] = \iint_{\mathbb{R}^2} x \cdot f(x,y) dx dy$$

This can be understood geometrically as finding the "center of mass" in the x-direction of the 3D surface formed by the joint density.

The computation can be done in two equivalent ways:

1. Direct integration: Integrate $x \cdot f(x,y)$ over the entire plane
2. Using marginal density: First find $f_X(x) = \int_{-\infty}^{\infty} f(x,y) dy$, then compute $\mathbb{E}[X] = \int_{-\infty}^{\infty} x \cdot f_X(x) dx$

The second approach works because:

$$\mathbb{E}[X] = \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} x \cdot f(x,y) dy dx = \int_{-\infty}^{\infty} x \left(\int_{-\infty}^{\infty} f(x,y) dy\right) dx = \int_{-\infty}^{\infty} x \cdot f_X(x) dx$$

Connection to Discrete Case

Similarly, for discrete random variables:

$$\mathbb{E}[X] = \sum_{x}\sum_{y} x \cdot p_{X,Y}(x,y) = \sum_{x} x \left(\sum_{y} p_{X,Y}(x,y)\right) = \sum_{x} x \cdot p_X(x)$$

This shows that whether we work with joint distributions directly or first compute marginal distributions, we arrive at the same expectation.

Conditional Expectation

The conditional expectation of $Y$ given $X = x$ is:

$$\mathbb{E}[Y|X = x] = \begin{cases} \sum_{y} y \cdot p_{Y|X}(y|x) & \text{(discrete)} \\ \int_{-\infty}^{\infty} y \cdot f_{Y|X}(y|x) dy & \text{(continuous)} \end{cases}$$

This leads to the law of total expectation:

$$\mathbb{E}[Y] = \mathbb{E}[\mathbb{E}[Y|X]]$$

ProofLaw of total expectation

In the discrete case define the conditional mean only at $x$ with $p_X(x)>0$. Then

$$\sum_x E[Y\mid X=x]p_X(x) =\sum_{x:p_X(x)>0}\sum_y y\,p_{X,Y}(x,y) =E[Y].$$

Zero-marginal points carry no mass and their conditional values may be chosen arbitrarily. Absolute integrability of $Y$ justifies rearrangement. For a joint density replace sums by integrals and use $f_{Y\mid X}(y\mid x)f_X(x)=f_{X,Y}(x,y)$ wherever $f_X(x)>0$, followed by Fubini's theorem. This proves the displayed cases; the general measure-theoretic conditional expectation needs additional construction.

Exercises

ExerciseUniform Discrete Integer Sampling

An integer $N$ is selected uniformly at random from $\{1, 2, \ldots, 10^3\}$.

1. What is the probability that $N$ is divisible by 3? By 5? By 7?
2. Compute the expected value $\mathbb{E}[N]$.
3. Compute the variance $\mathbb{V}(N)$.

Solution

1. Divisibility probabilities:

   • Divisible by 3: $\lfloor 1000/3 \rfloor = 333$ integers, so $P(3 \mid N) = \frac{333}{1000} = 0.333$.
   • Divisible by 5: $\lfloor 1000/5 \rfloor = 200$ integers, so $P(5 \mid N) = \frac{200}{1000} = 0.200$.
   • Divisible by 7: $\lfloor 1000/7 \rfloor = 142$ integers, so $P(7 \mid N) = \frac{142}{1000} = 0.142$.

2. Expected value: For a uniform discrete random variable on $\{1, 2, \ldots, n\}$ with $n = 1000$:

$$\mathbb{E}[N] = \frac{1}{n} \sum_{k=1}^{n} k = \frac{n(n+1)}{2n} = \frac{n+1}{2} = \frac{1001}{2} = 500.5.$$

3. Variance: Using the sum of squares formula $\sum_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$:

$$\mathbb{E}[N^2] = \frac{(n+1)(2n+1)}{6} = \frac{1001 \cdot 2001}{6} = 333833.5.$$$$\mathbb{V}(N) = \mathbb{E}[N^2] - (\mathbb{E}[N])^2 = \frac{n^2 - 1}{12} = \frac{1000^2 - 1}{12} = \frac{999999}{12} = 83333.25.$$

ExerciseTotal Heads in Two Biased Coin Flips

Two coins are flipped independently. The first coin lands on heads with probability $0.6$, and the second lands on heads with probability $0.7$. Let $X$ denote the total number of heads. Find $\mathbb{E}[X]$ and $\mathbb{V}(X)$.

Solution

Let $X_1 \sim \text{Bernoulli}(0.6)$ and $X_2 \sim \text{Bernoulli}(0.7)$ be indicator variables for the first and second coin landing heads. Then $X = X_1 + X_2$.

• By linearity of expectation:

$$\mathbb{E}[X] = \mathbb{E}[X_1] + \mathbb{E}[X_2] = 0.6 + 0.7 = 1.3.$$

• Since the coin flips are independent:

$$\mathbb{V}(X) = \mathbb{V}(X_1) + \mathbb{V}(X_2) = 0.6(1 - 0.6) + 0.7(1 - 0.7) = 0.24 + 0.21 = 0.45.$$

ExerciseBinary Search Questioning

One of the numbers $\{1, 2, \dots, 10\}$ is chosen uniformly at random. You guess the number by asking yes-no questions of the form "Is the number strictly greater than $k$?" following an optimal binary search tree strategy. Compute the expected number of questions asked.

Solution

An optimal binary search strategy on 10 elements queries:

• Query 1: "Is $N > 5$?" (splits into $\{1..5\}$ and $\{6..10\}$).
• For $\{1..5\}$: query "Is $N > 2$?" (splits into $\{1,2\}$ and $\{3,4,5\}$).
• For $\{6..10\}$: query "Is $N > 7$?" (splits into $\{6,7\}$ and $\{8,9,10\}$).

The depths in the decision tree:

• Numbers resolved in 3 questions: 6 numbers.
• Numbers resolved in 4 questions: 4 numbers.

Since all 10 outcomes are equally likely:

$$\mathbb{E}[\text{Questions}] = \frac{6 \times 3 + 4 \times 4}{10} = \frac{18 + 16}{10} = 3.4.$$

ExerciseSt. Petersburg Game

A player tosses a fair coin repeatedly until a tail appears for the first time. If the first tail appears on the $n$-th flip, the player wins $2^n$ dollars. Let $X$ denote the player's winnings. Prove that $\mathbb{E}[X] = +\infty$.

Solution

The number of flips until the first tail follows a Geometric($1/2$) distribution:

$$P(N = n) = \left(\frac{1}{2}\right)^{n-1} \cdot \frac{1}{2} = \frac{1}{2^n}, \quad n \in \{1, 2, 3, \ldots\}$$

When $N = n$, the winnings are $X = 2^n$. The expected payoff is:

$$\mathbb{E}[X] = \sum_{n=1}^{\infty} 2^n \cdot P(N = n) = \sum_{n=1}^{\infty} 2^n \cdot \frac{1}{2^n} = \sum_{n=1}^{\infty} 1 = +\infty.$$

ExerciseInspection Paradox on School Buses

Four buses carrying 148 students arrive at a school. The buses carry 40, 33, 25, and 50 students, respectively.

1. One student is selected uniformly at random from the 148 students. Let $X$ denote the number of students on that selected student's bus.
2. One bus is selected uniformly at random from the 4 buses. Let $Y$ denote the number of students on that selected bus. Compute $\mathbb{E}[X]$ and $\mathbb{E}[Y]$, and explain the discrepancy.

Solution

1. Student perspective ($X$): The probability that the chosen student is on a bus with $i$ passengers is proportional to the bus size:

$$P(X = i) = \frac{i}{148}, \quad i \in \{40, 33, 25, 50\}$$$$\mathbb{E}[X] = \sum i \cdot \frac{i}{148} = \frac{40^2 + 33^2 + 25^2 + 50^2}{148} = \frac{1600 + 1089 + 625 + 2500}{148} = \frac{5814}{148} \approx 39.28.$$

2. Bus perspective ($Y$): Each bus is chosen with probability $\frac{1}{4}$:

$$\mathbb{E}[Y] = \frac{40 + 33 + 25 + 50}{4} = \frac{148}{4} = 37.0.$$

The difference $\mathbb{E}[X] > \mathbb{E}[Y]$ is an instance of the inspection paradox: larger buses contain more students and are therefore more likely to be sampled when choosing a student at random. In fact, $\mathbb{E}[X] = \mathbb{E}[Y] + \frac{\mathbb{V}(Y)}{\mathbb{E}[Y]}$.

ExerciseVariance in the Bus Inspection Paradox

Compute the variances $\mathbb{V}(X)$ and $\mathbb{V}(Y)$ for the random variables $X$ and $Y$ defined in the preceding bus problem.

Solution

1. Variance of $X$:

$$\mathbb{E}[X^2] = \frac{40^3 + 33^3 + 25^3 + 50^3}{148} = \frac{64000 + 35937 + 15625 + 125000}{148} = \frac{240562}{148} \approx 1625.42.$$$$\mathbb{V}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 \approx 1625.42 - (39.2838)^2 \approx 1625.42 - 1543.22 = 82.20.$$

2. Variance of $Y$:

$$\mathbb{E}[Y^2] = \frac{40^2 + 33^2 + 25^2 + 50^2}{4} = \frac{5814}{4} = 1453.5.$$$$\mathbb{V}(Y) = \mathbb{E}[Y^2] - (\mathbb{E}[Y])^2 = 1453.5 - 37^2 = 1453.5 - 1369 = 84.50.$$

ExerciseProper Scoring Rule for Weather Forecasting

A weather forecaster announces a probability $p \in [0, 1]$ that it will rain tomorrow. The forecaster receives a score of $1 - (1 - p)^2$ if it rains, and $1 - p^2$ if it does not rain. Suppose the forecaster's true internal belief is that it will rain with probability $p^*$. What probability $p$ should the forecaster report to maximize their expected score?

Solution

The expected score as a function of the announced probability $p$ is:

$$\begin{aligned} \mathbb{E}[\text{Score}] &= p^* \left[1 - (1 - p)^2\right] + (1 - p^*)\left[1 - p^2\right] \\ &= p^* [2p - p^2] + (1 - p^*)(1 - p^2) \\ &= 2p p^* - p^* p^2 + 1 - p^2 - p^* + p^* p^2 \\ &= 2p p^* - p^2 + 1 - p^*. \end{aligned}$$

To find the maximum, take the derivative with respect to $p$:

$$\frac{d}{dp}\mathbb{E}[\text{Score}] = 2p^* - 2p.$$

Setting the derivative to zero yields $p = p^*$. The second derivative $\frac{d^2}{dp^2}\mathbb{E}[\text{Score}] = -2 < 0$ confirms this is a strict global maximum. Thus, the Brier scoring rule is strictly proper: the forecaster maximizes expected score if and only if reporting their honest probability $p = p^*$.

ExerciseQuotient Form and Independence of CDFs

Explain why the independence of random variables $X_1, X_2, \ldots, X_n$ cannot be formulated using a quotient ratio of CDFs:

$$\frac{F_{X_1, \ldots, X_n}(x_1, \ldots, x_n)}{F_{X_1}(x_1)} = F_{X_2}(x_2) \cdots F_{X_n}(x_n).$$

Solution

Independence is defined by the product rule for joint probabilities: $F_{X_1, \ldots, X_n}(x_1, \ldots, x_n) = \prod_{i=1}^n F_{X_i}(x_i)$.

A quotient of CDFs $\frac{F_{X, Y}(x, y)}{F_X(x)}$ does not correspond to the conditional CDF $P(Y \leq y \mid X \leq x)$ in general because conditioning on $X \leq x$ requires the joint probability $P(X \leq x, Y \leq y)$ divided by $P(X \leq x)$, which is not $F_Y(y)$ unless the variables are independent.

Moreover, writing the condition as a quotient requires assuming $F_{X_1}(x_1) > 0$, failing for all points outside the support. Independence is an intrinsic symmetry between unconditional distributions, correctly stated via products rather than ratios.

ExerciseMoments and Linear Combinations of Independent RVs

Let $X$ and $Y$ be independent discrete random variables with distributions:

$$\begin{array}{c|ccc} x & -1 & 0 & 1 \\ \hline P(X = x) & \frac{1}{6} & \frac{1}{3} & \frac{1}{2} \end{array} \qquad \begin{array}{c|ccc} y & 0 & 2 & 4 \\ \hline P(Y = y) & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \end{array}$$

Let $W = 3Y - 6X$ and $Z = 2X + Y$.

1. Compute $\mathbb{E}[X]$ and $\mathbb{V}(X)$.
2. Compute $\mathbb{E}[W]$.
3. Tabulate the probability distribution of $Z$.

Solution

1. Moments of $X$:

$$\mathbb{E}[X] = (-1)\left(\frac{1}{6}\right) + 0\left(\frac{1}{3}\right) + 1\left(\frac{1}{2}\right) = -\frac{1}{6} + \frac{3}{6} = \frac{1}{3}.$$$$\mathbb{E}[X^2] = (-1)^2\left(\frac{1}{6}\right) + 0^2\left(\frac{1}{3}\right) + 1^2\left(\frac{1}{2}\right) = \frac{1}{6} + \frac{3}{6} = \frac{2}{3}.$$$$\mathbb{V}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 = \frac{2}{3} - \frac{1}{9} = \frac{5}{9}.$$

2. Expectation $\mathbb{E}[W]$: First, compute $\mathbb{E}[Y]$:

$$\mathbb{E}[Y] = 0\left(\frac{1}{4}\right) + 2\left(\frac{1}{2}\right) + 4\left(\frac{1}{4}\right) = 0 + 1 + 1 = 2.$$

By linearity:

$$\mathbb{E}[W] = 3\mathbb{E}[Y] - 6\mathbb{E}[X] = 3(2) - 6\left(\frac{1}{3}\right) = 6 - 2 = 4.$$

3. Distribution of $Z = 2X + Y$: Possible values of $2X$ are $\{-2, 0, 2\}$. Values of $Y$ are $\{0, 2, 4\}$. The possible values of $Z = 2X + Y$ are $\{-2, 0, 2, 4, 6\}$. Since $X$ and $Y$ are independent, $P(X=x, Y=y) = P(X=x)P(Y=y)$:
   • $P(Z = -2) = P(X=-1, Y=0) = \frac{1}{6} \cdot \frac{1}{4} = \frac{1}{24}$.

$$P(Z = 0) = P(X=-1, Y=2) + P(X=0, Y=0) = \frac{1}{6} \cdot \frac{1}{2} + \frac{1}{3} \cdot \frac{1}{4} = \frac{1}{12} + \frac{1}{12} = \frac{1}{6}$$

.

$$P(Z = 2) = P(X=-1, Y=4) + P(X=0, Y=2) + P(X=1, Y=0) = \frac{1}{6}\cdot\frac{1}{4} + \frac{1}{3}\cdot\frac{1}{2} + \frac{1}{2}\cdot\frac{1}{4} = \frac{1}{24} + \frac{1}{6} + \frac{1}{8} = \frac{1}{3}$$

.

$$P(Z = 4) = P(X=0, Y=4) + P(X=1, Y=2) = \frac{1}{3}\cdot\frac{1}{4} + \frac{1}{2}\cdot\frac{1}{2} = \frac{1}{12} + \frac{1}{4} = \frac{1}{3}$$

.

• $P(Z = 6) = P(X=1, Y=4) = \frac{1}{2}\cdot\frac{1}{4} = \frac{1}{8}$.

$$\begin{array}{c|ccccc} z & -2 & 0 & 2 & 4 & 6 \\ \hline P(Z = z) & \frac{1}{24} & \frac{1}{6} & \frac{1}{3} & \frac{1}{3} & \frac{1}{8} \end{array}$$

ExerciseAdditivity of Variance by Mathematical Induction

Prove that for any sequence of pairwise independent random variables $\{X_1, X_2, \ldots, X_n\}$ with finite variances:

$$\mathbb{V}\left(\sum_{i=1}^n X_i\right) = \sum_{i=1}^n \mathbb{V}(X_i).$$

Proof

We prove the statement by mathematical induction on $n$.

Base Case ($n = 1$): $\mathbb{V}(X_1) = \mathbb{V}(X_1)$, which holds trivially. For $n = 2$, by definition:

$$\begin{aligned} \mathbb{V}(X_1 + X_2) &= \mathbb{E}[(X_1 + X_2)^2] - (\mathbb{E}[X_1 + X_2])^2 \\ &= \mathbb{E}[X_1^2] + 2\mathbb{E}[X_1 X_2] + \mathbb{E}[X_2^2] - (\mathbb{E}[X_1] + \mathbb{E}[X_2])^2. \end{aligned}$$

By independence, $\mathbb{E}[X_1 X_2] = \mathbb{E}[X_1]\mathbb{E}[X_2]$, so the cross-terms cancel:

$$\mathbb{V}(X_1 + X_2) = (\mathbb{E}[X_1^2] - \mathbb{E}[X_1]^2) + (\mathbb{E}[X_2^2] - \mathbb{E}[X_2]^2) = \mathbb{V}(X_1) + \mathbb{V}(X_2).$$

Inductive Step: Assume the property holds for $n = k$, i.e. $\mathbb{V}\left(\sum_{i=1}^k X_i\right) = \sum_{i=1}^k \mathbb{V}(X_i)$. For $n = k + 1$, let $S_k = \sum_{i=1}^k X_i$. Since $X_{k+1}$ is independent of each $X_1, \dots, X_k$, it is independent of their sum $S_k$. Applying the two-variable additivity rule:

$$\mathbb{V}(S_k + X_{k+1}) = \mathbb{V}(S_k) + \mathbb{V}(X_{k+1}) = \sum_{i=1}^k \mathbb{V}(X_i) + \mathbb{V}(X_{k+1}) = \sum_{i=1}^{k+1} \mathbb{V}(X_i).$$

By induction, the property holds for all $n \geq 1$.