1.1 Expectations of Sums

The expectation of a sum is the sum of the expectations, whether or not the terms are independent. Writing a count as a sum of indicator variables, each equal to \(1\) if some event happens and \(0\) otherwise, therefore turns a hard counting problem into several easy ones, since \(E(I_A) = P(A)\).

Example 1.1.1. Three fair dice are thrown. Find the expected total score.

Solution. Let \(X_i\) be the score on the \(i\)th die. Each takes the values \(1, \dots , 6\) with probability \(\frac 16\), so \(E(X_i) = \frac {1 + 2 + \cdots + 6}{6} = \frac 72\). The total is \(X = X_1 + X_2 + X_3\), and \[E(X) = E(X_1) + E(X_2) + E(X_3) = 3\cdot \frac 72 = 10.5 .\]

Example 1.1.2 (The matching problem). At a party \(N\) people throw their hats into the centre of a room. The hats are mixed and each person picks one at random. Find the mean and variance of the number who get their own hat.

Solution. Let \(X_i = 1\) if person \(i\) picks their own hat and \(0\) otherwise, and \(X = \sum _{i=1}^N X_i\). Each person is equally likely to get any of the \(N\) hats, so \(P(X_i = 1) = \frac 1N\) and \[E(X) = \sum _{i=1}^N E(X_i) = N\cdot \frac 1N = 1 .\] For the variance, \(\var (X) = \sum _i\var (X_i) + 2\sum _{i<j}\cov (X_i, X_j)\). Each \(X_i\) is Bernoulli with \(p = \frac 1N\), so \(\var (X_i) = \frac 1N\left (1 - \frac 1N\right ) = \frac {N - 1}{N^2}\). For \(i\ne j\), both get their own hats with probability \(P(X_i = 1)P(X_j = 1\mid X_i = 1) = \frac 1N\cdot \frac {1}{N - 1}\), so \[\cov (X_i, X_j) = E(X_iX_j) - E(X_i)E(X_j) = \frac {1}{N(N - 1)} - \frac {1}{N^2} = \frac {1}{N^2(N - 1)} .\] There are \(\binom N2\) pairs \(i<j\), so \[\var (X) = N\cdot \frac {N - 1}{N^2} + 2\binom N2\frac {1}{N^2(N - 1)} = \frac {N - 1}{N} + \frac {1}{N} = 1 .\] Both answers are free of \(N\). For large \(N\) the number of matches is approximately Poisson with mean \(1\), and the probability that nobody gets their own hat tends to \(e^{-1} = 0.368\).

Example 1.1.3 (Coupons). There are \(25\) types of coupon, and each coupon obtained is equally likely to be any type, independently of the others. Find the expected number of distinct types in a set of \(10\) coupons.

Solution. Let \(X_i = 1\) if type \(i\) appears at least once among the \(10\) coupons. A given coupon is not of type \(i\) with probability \(\frac {24}{25}\), so \(P(X_i = 0) = \left (\frac {24}{25}\right )^{10}\) and \(E(X_i) = 1 - \left (\frac {24}{25}\right )^{10}\). The number of distinct types is \(X = \sum _{i=1}^{25}X_i\), so \[E(X) = 25\left [1 - \left (\frac {24}{25}\right )^{10}\right ] = 25(1 - 0.6648) = 8.38 .\] The indicators are dependent (if one type is missing the others are a little more likely to appear), but that does not affect the expectation.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.