Combinatorics · Chapter 9

Expected Value

Weighted averages, fair games and the most useful trick in contest probability: linearity of expectation with indicator variables.

What's this chapter about?

9.0 Expected Value and Linearity
9.1 Practice Problems

You'll need

open on YouTube

9.00%

Expected Value and Linearity

In this section you will be able to find expected values as weighted averages, and split hard ones into easy pieces with linearity of expectation.

A 100-dollar casino game pays 500 dollars with chance 5% and 250 dollars with chance 20%. Should you play?

You can’t know what one game pays. But you can find what it pays on average. Weight each prize by its chance and add: that is the expected value.

The real power tool is linearity of expectation. To count something random, split it into small 0-or-1 pieces called indicators. Each piece’s expected value is just its probability. Add them up, even when the pieces depend on each other.

Look:expected value is an average, not a promise. A die’s expected value is 3.5, a roll you can never get.

Exploreplay first, formulas later

Try this: Look at the arrow column (x · P(x)). Which outcome adds the most to E? Is it the most likely one?
Try this: Press Play 1,000 times, then again. Does the running average settle near the dashed line E?
Try this: Move probability from Nothing to Big win until E reaches 100. How likely must the big win be for a fair game?
Try this: Open Show me on the Expected Value theorem. Why is E = 3.5 when no roll ever shows 3.5?

Name it

Definition 9.0.1 · Expected Value

Expected value is the weighted average of the outcomes: each outcome counts in proportion to how likely it is.

A $\$2$ game: roll a die, and a 6 pays the prize. Raise the prize until the expected winnings equal the price.

Theorem 9.0.2 · Expected Value

The expected value of a random quantity $X$ is

E(X) = \sum x_i \cdot P(x_i),

where the $x_i$ are the possible values of $X$ and $P(x_i)$ is the probability that each one happens.

In words: multiply each value by its probability, then add.

Theorem 9.0.4 · Linearity of Expectation

For any random quantities $x_1, x_2, \dots, x_n$ , independent or dependent,

E(x_1 + x_2 + \cdots + x_n) = E(x_1) + E(x_2) + \cdots + E(x_n).

The expected value of a total is the sum of the expected values of its parts.

7 boys and 13 girls in a row. Each gap is an indicator: 1 when its two neighbors differ. The total $S$ is the sum of the 19 indicators.

Watch itpredict, then reveal

Example 9.1

AHSME

Suppose that 7 boys and 13 girls line up in a row. Let $S$ be the number of places in the row where a boy and a girl are standing next to each other. For example, for the row GBBGGGBGBGGGBGBGGBGG we have $S = 12$ . Find the expected value of $S$ .

1
We will use linearity of expectation. How many places are there where a boy and a girl could be standing next to each other?

Predict first:
Your prediction

Example 9.2

AHSME

1
The book prints Example 9.1 again, word for word. Try it without scrolling up. What is the chance that one particular place holds a boy and a girl?

Predict first:
Your prediction

Example 9.3

AMC 10

Five balls are arranged around a circle. Chris chooses two adjacent balls at random and interchanges them. Then Silva does the same, with her choice of adjacent balls to interchange being independent of Chris's. What is the expected number of balls that occupy their original positions after these two successive transpositions?

1
Give each ball an indicator: $1$ if it ends in its own spot. The answer is the expected sum of the 5 indicators. Is every ball equally likely to end at home?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 9.4

AMC 12

What is the average number of pairs of consecutive integers in a randomly selected subset of 5 distinct integers chosen from the set $\{1, 2, 3, \dots, 30\}$ ? (For example the set $\{1, 17, 18, 19, 30\}$ has 2 pairs of consecutive integers.)

1
Give each pair $(i, i+1)$ an indicator: $1$ if both numbers are chosen. How many such pairs are there in $\{1, \dots, 30\}$ ?

Predict first:
Your prediction

open on YouTube

Example 9.5

I have a calculator with 4 buttons: $1$ , $2$ , $+$ , $-$ . Initially, I randomly press one of the four buttons and from there, I alternate between pressing a number and an operation. If I press the button a total of 100 times, what is the expected value of the output?

1
We can ignore all the numbers after the first operation button is pressed. Why?

Predict first:
Click a choice or type its letter (A–E).

Try it

Problem 9.1.1

Mark is playing a game at the casino. The game costs $\$100$ . There is a $5\%$ chance he will win $\$500$ and a $20\%$ chance he will win $\$250$ and $75\%$ chance he will win $\$0$ . What is the expected value for the money he will lose?

Contest cornerreal contest problems

Problem 9.1.2

AMC 10

A player pays $\$5$ to play a game. A die is rolled. If the number on the die is odd, the game is lost. If the number on the die is even, the die is rolled again. In this case the player wins if the second number matches the first and loses otherwise. How much should the player win if the game is fair? (In a fair game the probability of winning times the amount won is what the player should pay.)

Problem 9.1.3

AMC 12

Awnik repeatedly plays a game that has a probability of winning of $\frac13$ . The outcomes of the games are independent. What is the expected value of the number of games he will play until he has both won and lost at least once?

Problem 9.1.4(additional)

AMC 12

A school has 100 students and 5 teachers. In the first period, each student is taking one class, and each teacher is teaching one class. The enrollments in the classes are 50, 20, 20, 5, and 5. Let $t$ be the average value obtained if a teacher is picked at random and the number of students in their class is noted. Let $s$ be the average value obtained if a student was picked at random and the number of students in their class, including the student, is noted. What is $t - s$ ?

Checkpoint for section 9.0

Get 2 of 3 right to master this section. One try each, no hints.

9.1

Practice Problems

In this section you will be able to use linearity, symmetry and geometric series on harder expected value problems.

Three AIME-style problems. Each one looks like a monster sum until you split it with linearity of expectation.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 9.1.5(additional)

AIME

Let $\mathcal{S}$ be the set of real numbers that can be represented as repeating decimals of the form $0.\overline{abc}$ where $a, b, c$ are distinct digits. Find the sum of the elements of $\mathcal{S}$ .

Problem 9.1.6(additional)

AIME

For each permutation $a_1, a_2, a_3, \dots, a_{10}$ of the integers $1, 2, 3, \dots, 10$ , form the sum

|a_1 - a_2| + |a_3 - a_4| + |a_5 - a_6| + |a_7 - a_8| + |a_9 - a_{10}|.

The average value of all such sums can be written in the form $\frac{p}{q}$ , where $p$ and $q$ are relatively prime positive integers. Find $p + q$ .

Problem 9.1.7(additional)

NIMO

One day, a bishop and a knight were on squares in the same row of an infinite chessboard, when a huge meteor storm occurred, placing a meteor in each square on the chessboard independently and randomly with probability $p$ . Neither the bishop nor the knight were hit, but their movement may have been obstructed by the meteors. For what value of $p$ is the expected number of valid squares that the bishop can move to (in one move) equal to the expected number of squares that the knight can move to (in one move)?