Discrete Math › Section D · Counting › Topic D.10
Random variables and expected value
A random variable turns each outcome of an experiment into a number, and its expected value is the long-run average of that number. Linearity of expectation, combined with simple 0-or-1 variables, solves counting-flavoured problems that would be very hard to attack directly.
From outcomes to numbers
"Counting and probability" measured the chance of events. Often the question is numerical instead: how many heads, how many fixed points, how many draws until something happens? A random variable \(X\) is a function from the sample space \(S\) to the real numbers, assigning one number to each outcome. Choose a random 3-bit string and let \(X\) be its weight. The 8 strings are equally likely, and grouping them by weight gives the distribution of \(X\): \(P(X = 0) = \frac{1}{8}\), \(P(X = 1) = \frac{3}{8}\), \(P(X = 2) = \frac{3}{8}\) and \(P(X = 3) = \frac{1}{8}\). The numerators are row 3 of Pascal's triangle.
Expected value
The expected value of \(X\) is the probability-weighted average of its values:
For the weight of a 3-bit string,
Equivalently, add \(X(s)P(s)\) over the individual outcomes \(s\). The expected value is the long-run average over many repetitions, not a value you expect to see: a fair die has \(E(X) = 3.5\), which no roll can show. The statistics course develops the same definition, with standard deviation, in "Expected value and standard deviation".
Worked example: is the raffle worth it?
A school raffle sells 500 tickets at $2 each. One ticket wins $300 and two tickets win $50 each. You buy one ticket. 1. Let \(W\) be your winnings. \(P(W = 300) = \frac{1}{500}\), \(P(W = 50) = \frac{2}{500}\), and otherwise \(W = 0\). 2. In dollars,
3. Your net gain is \(W - 2\), so its expected value is \(0.80 - 2 = -1.20\) dollars. 4. Check with totals: the school takes in $1,000 and pays out $400, keeping $600, which is $1.20 per ticket. On average each ticket loses $1.20, which is the point of a fundraiser.
Linearity of expectation
For any random variables \(X\) and \(Y\) on the same sample space, and any constants \(a\) and \(b\),
The reason is short: \(E(X + Y) = \sum_s (X(s) + Y(s))P(s)\), and the sum splits into two. Nothing in that argument needs \(X\) and \(Y\) to be independent, and that is the source of the rule's power. It extends to any finite sum, so the expected value of a total is the total of the expected values, even when the parts depend on each other in complicated ways. The step \(W - 2\) in the raffle example was already linearity at work.
Indicator variables
The indicator of an event \(A\) is the random variable \(I_A\) that equals 1 when \(A\) happens and 0 when it does not. Its expected value is
Indicators pair perfectly with linearity: to find the expected number of something, write the count as a sum of indicators, one per possible occurrence, and add their probabilities. The weight of a random \(n\)-bit string is the sum of \(n\) indicators, one per bit, each with probability \(\frac{1}{2}\), so its expected value is \(\frac{n}{2}\). For \(n = 3\) that is 1.5, matching the direct calculation without building any distribution.
Worked example: names drawn from a hat
In a gift exchange, \(n\) people each draw one name at random from a hat holding all \(n\) names. On average, how many people draw their own name? 1. Let \(I_k\) indicate that person \(k\) draws their own name. 2. Each person is equally likely to draw any of the \(n\) names, so \(E(I_k) = \frac{1}{n}\). 3. The number of self-draws is \(X = I_1 + \cdots + I_n\), so \(E(X) = n \cdot \frac{1}{n} = 1\). 4. The indicators are not independent, but linearity does not care. The answer is 1 for every \(n\). A full check over the 120 draws for \(n = 5\) confirms an average of exactly 1. Contrast this with "Advanced counting: derangements and functions", where finding the probability of no self-draws took full inclusion-exclusion.
Worked example: shared birthdays
In a group of 30 people, how many pairs share a birthday, on average? Assume 365 equally likely birthdays, independent between people, and ignore leap days. 1. There are \(\binom{30}{2} = 435\) pairs of people. 2. For each pair, let an indicator record whether its two birthdays match. Whatever the first person's birthday is, the second matches it with probability \(\frac{1}{365}\). 3. By linearity, the expected number of matching pairs is \(\frac{435}{365} \approx 1.19\). 4. That is more than one, which helps explain why a shared birthday in a group of 30 is not surprising. "Probability in algorithms and security" applies the same count to collisions in hash functions.
Waiting times and coupon collecting
If each independent attempt succeeds with probability \(p\), the expected number of attempts up to and including the first success is \(\frac{1}{p}\), as the statistics topic "The geometric distribution" shows. Combined with linearity, this solves the coupon collector problem. A cereal brand hides one of 6 equally likely toys in each box. After you hold \(j\) different toys, a new box brings a new toy with probability \(\frac{6 - j}{6}\), so that stage takes \(\frac{6}{6 - j}\) boxes on average. Adding the six stages gives
boxes. With \(n\) types the expectation is \(n(1 + \frac{1}{2} + \cdots + \frac{1}{n})\), which grows like \(n \ln n\): about 225 boxes for 50 types.
Spread: the variance
Expected value says nothing about spread. The variance measures it:
For one fair die, \(E(X^2) = \frac{1^2 + 2^2 + \cdots + 6^2}{6} = \frac{91}{6}\), so \(\text{Var}(X) = \frac{91}{6} - 3.5^2 = \frac{35}{12}\). Unlike expectation, variance is not additive in general: \(\text{Var}(X + Y) = \text{Var}(X) + \text{Var}(Y)\) holds when \(X\) and \(Y\) are independent, but can fail when they are not.
Common mistakes to avoid
First, reading the expected value as the most likely value, or as a value that must occur: a die never shows 3.5. Second, thinking linearity needs independence; it never does, although the rule for adding variances does. Third, writing \(E(XY) = E(X)E(Y)\) without independence. Fourth, defining indicators carelessly, so that the sum does not equal the count you want, for example one indicator per person when the question counts pairs. Fifth, treating the coupon collector's 14.7 boxes as a guarantee; it is a long-run average, and an unlucky collector may need many more.
Key takeaways
A random variable assigns a number to each outcome, and its distribution lists \(P(X = x)\). The expected value \(E(X) = \sum_x x\,P(X = x)\) is a long-run average. Linearity, \(E(X + Y) = E(X) + E(Y)\), always holds, even for dependent variables. An indicator has expected value equal to the probability of its event, so expected counts are sums of probabilities: one self-draw from the hat for any \(n\), and about 1.19 shared-birthday pairs among 30 people. Geometric waits average \(\frac{1}{p}\), and collecting \(n\) coupons takes about \(n \ln n\) draws.
Flashcards
Flashcard
A function from the sample space to the real numbers
Test your understanding
Question 1 of 5
X takes the values 0, 1, 2 and 4 with probabilities 0.4, 0.3, 0.2 and 0.1. What is E(X)?
Question 2 of 5
A biased coin lands heads with probability 0.3. What is the expected number of heads in 20 flips?
Question 3 of 5
Fifty people each draw one of their fifty names at random from a hat. What is the expected number who draw their own name?
Question 4 of 5
Assuming 365 equally likely birthdays, what is the expected number of pairs sharing a birthday in a group of 20 people?
Question 5 of 5
Each box holds one of 4 equally likely toys. What is the expected number of boxes needed to collect all 4 toys?
