Random Variables, Expectation and Variance

Chance is described with numbers: the number of heads in ten tosses, the number of probes in a hash table, the waiting time until a server responds. A random variable attaches a number to each outcome of an experiment, so that we can talk about its distribution, its average value (expectation) and its spread (variance). These three ideas are used throughout algorithm analysis (expected running time, expected number of collisions in hashing), performance modelling and statistics.

A random variable (RV) $X$ is a function from the sample space $S$ to $\mathbb{R}$. Example: toss three coins and let $X$ be the number of heads; the outcome $HTH$ gives $X = 2$. The event $\{X = x\}$ is the set of outcomes mapped to $x$.

The cumulative distribution function (cdf) is defined for every RV as

Properties: $F$ is non-decreasing, right-continuous, $F(x) \to 0$ as $x \to -\infty$ and $F(x) \to 1$ as $x \to \infty$; $P(a < X \le b) = F(b) - F(a)$. For a discrete RV, $F$ is a step function jumping by $p(x)$ at each value $x$. For a continuous RV, $F$ is continuous and $F'(x)=f(x)$ almost everywhere (and at every point where the chosen density $f$ is continuous). For a continuous RV, $<$ and $\le$ give the same probabilities.

The expected value (mean) $E[X] = \mu$ is the probability-weighted average:

provided the sum or integral converges absolutely (otherwise $E[X]$ does not exist).

Law of the unconscious statistician (LOTUS): for a function $g$, $E[g(X)] = \sum_x g(x) p(x)$ or $\int g(x) f(x)\,dx$. There is no need to find the distribution of $g(X)$ first.

Linearity of expectation: for any RVs $X, Y$ and constants $a, b$,

whether or not $X$ and $Y$ are independent. This is a key fact in probabilistic algorithm analysis.

Products: $E[XY] = E[X]\,E[Y]$ if $X$ and $Y$ are independent. The converse is false.

Indicator variables. For an event $A$, the indicator $I_A$ is 1 if $A$ occurs and 0 otherwise, so $E[I_A] = P(A)$. Writing a count as a sum of indicators and using linearity avoids computing its distribution (Example 3).

Tail-sum formula. For an RV taking values in $\{0, 1, 2, \ldots\}$, $E[X] = \sum_{k \ge 1} P(X \ge k)$.

The second form (the shortcut) follows by expanding the square and using linearity. Properties, for constants $a, b$:

Variance convention. The variance of a random variable (a population quantity) is defined as the expectation $E[(X - \mu)^2]$, with no $n$ or $n - 1$ divisor. The sample variance of observed data uses a divisor $n - 1$ and is covered in Descriptive Statistics.

For discrete $X, Y$, the joint pmf $p(x, y) = P(X = x, Y = y)$ gives the marginals $p_X(x) = \sum_y p(x, y)$. $X$ and $Y$ are independent if $p(x, y) = p_X(x)\,p_Y(y)$ for all $x, y$. When both variances are finite and positive, the correlation coefficient $\rho=\operatorname{Cov}(X,Y)/(\sigma_X\sigma_Y)$ lies in $[-1,1]$. If either variable is constant, $\rho$ is undefined, not automatically zero. With finite positive variances, independence implies $\rho=0$; uncorrelated does not imply independent: if $X$ is uniform on $\{-1, 0, 1\}$ and $Y = X^2$, then $\operatorname{Cov}(X, Y) = 0$ but $Y$ is determined by $X$.

Every rule involving correlation below assumes finite, strictly positive variances for both variables.

For RVs $X, Y, Z$ and constants $a, b, c, d$:

Conditional expectation. For discrete RVs, $E[X \mid Y = y] = \sum_x x\,P(X = x \mid Y = y)$. The law of total expectation is the expectation form of total probability:

$X$ uniform on $\{1, \ldots, 6\}$. $E[X] = 21/6 = 3.5$. $E[X^2] = 91/6$, so $\operatorname{Var}(X) = 91/6 - 49/4 = 35/12 \approx 2.917$. For the sum $T$ of two independent dice: $E[T] = 7$, $\operatorname{Var}(T) = 35/6$. For $Y = 2X + 3$: $E[Y] = 10$, $\operatorname{Var}(Y) = 4 \cdot 35/12 = 35/3$.

$f(x) = 2x$ for $0 \le x \le 1$, and 0 otherwise. Check: $\int_0^1 2x\,dx = 1$. CDF: $F(x) = x^2$ on $[0, 1]$. $E[X] = \int_0^1 2x^2\,dx = 2/3$; $E[X^2] = \int_0^1 2x^3\,dx = 1/2$; $\operatorname{Var}(X) = 1/2 - 4/9 = 1/18$. $P(X > 1/2) = 1 - F(1/2) = 3/4$. The median $m$ solves $F(m) = 1/2$: $m = 1/\sqrt{2} \approx 0.707$.

A random permutation of $n$ items. Let $I_i$ indicate that item $i$ is in place; $P(I_i = 1) = 1/n$. The number of fixed points $X = \sum I_i$ has $E[X] = n \cdot (1/n) = 1$, for every $n$, although the $I_i$ are dependent.

$k$ keys hashed independently and uniformly into $m$ slots. Slot $j$ is empty with probability $(1 - 1/m)^k$, so the expected number of empty slots is $m(1 - 1/m)^k$. With $m = k = 100$ this is about $36.6$, close to $m/e$. The expected number of colliding pairs is $\binom{k}{2}/m$.

$P(X = x) = k\,x$ for $x = 1, 2, 3, 4$. Then $k(1 + 2 + 3 + 4) = 1$, so $k = 1/10$; $E[X] = (1 + 4 + 9 + 16)/10 = 3$; $E[X^2] = (1 + 8 + 27 + 64)/10 = 10$; $\operatorname{Var}(X) = 1$.

$E[X] = 0.7$, $E[Y] = 0.6$, and $E[XY] = P(X = 1, Y = 1) = 0.5$, so $\operatorname{Cov}(X, Y) = 0.5 - 0.42 = 0.08$. As Bernoulli variables, $\operatorname{Var}(X) = 0.7 \times 0.3 = 0.21$ and $\operatorname{Var}(Y) = 0.6 \times 0.4 = 0.24$, so $\rho = 0.08/\sqrt{0.21 \times 0.24} \approx 0.356$. $X$ and $Y$ are dependent: $p(0, 0) = 0.2 \ne 0.3 \times 0.4 = 0.12$. Finally $\operatorname{Var}(X + Y) = 0.21 + 0.24 + 2(0.08) = 0.61$, which matches the direct computation from the pmf of $X + Y$ (values 0, 1, 2 with probabilities 0.2, 0.3, 0.5).

Roll a fair die, then toss a fair coin as many times as the die shows. Let $N$ be the die result, hence the number of coin tosses. Given $N=n$, the expected number of heads is $n/2$, so $E[H] = \sum_{n=1}^{6} \frac{n}{2} \cdot \frac16 = \frac{E[N]}{2} = 1.75$.

In a random permutation of $n$ distinct keys, each of the $\binom{n}{2}$ pairs is out of order with probability $1/2$. By indicators and linearity, the expected number of inversions is $\binom{n}{2}/2 = n(n - 1)/4$: 3 for $n = 4$, 4950/2 = 2475 for $n = 100$. This is the average number of adjacent swaps in bubble sort and adjacent-swap insertion sort; in the usual shift-based insertion sort it is the average number of rightward shifts.

$X$ uniform on $[0, 1]$ and $Y = X^2$. Use the cdf: for $0 \le y \le 1$, $F_Y(y) = P(X \le \sqrt{y}) = \sqrt{y}$, so $f_Y(y) = 1/(2\sqrt{y})$, a density that is unbounded near 0 yet integrates to 1. By LOTUS, $E[Y] = \int_0^1 x^2\,dx = 1/3$, which differs from $(E[X])^2 = 1/4$ by $\operatorname{Var}(X) = 1/12$. The median of $Y$ is $(1/2)^2 = 1/4$: medians pass through increasing functions, means do not.