11. Probability States · Mastering AMC 10/12

11.00%

States

In this section you will be able to turn a game that could last forever into a few equations: one unknown per state, then solve.

Amelia and Blaine take turns tossing coins, and the first head wins. The game could go on forever. So how can you add up every way Amelia wins?

You don’t add them up. Look: after two misses, the game is exactly where it started. Amelia is about to toss again. Each such position is a state.

Give each state an unknown: the chance of winning from there. Follow every arrow out of a state to write its equation. Then solve the system. A game that never ends becomes two lines of algebra.

Look:if two positions look the same from the rules’ point of view, they have the same chance. Merge them into one state.

Exploreplay first, formulas later

Try this: Read the two equations. Why does Blaine's equation have no "Amelia wins" term, only a term with a?
Try this: Press Next step. Which equation was solved first, and where did it get substituted?
Try this: Look at the arrows out of each state. Why must their chances always add up to 1?
Try this: Open Show me on Symmetry in States, then turn on Merge symmetric states. Why can four corner squares become one state?

Name it

Concept 11.0.1 · States

We use states when we want the probability of “a win” from different positions or turns. For a states problem, follow three steps:

Assign a variable to the probability of winning from each position.
Write an equation for the probability of winning from each position, in terms of the other states.
Solve the system of equations.

Concept 11.0.2 · Symmetry in States

Always look out for symmetry in states problems: positions you have an equal probability of winning from can share one variable. That makes the equations much simpler.

Remark 11.0.3

Often in states problems with a lot of states, you may have to write a state recursion equation: one rule that links each state to its neighbors, like $p_n = \frac12 p_{n-1} + \frac12 p_{n+1}$ .

Watch itpredict, then reveal

Example 11.1

AMC 12

Tom, Dick, and Harry are playing a game. Starting at the same time, each of them flips a fair coin repeatedly until he gets his first head, at which point he stops. What is the probability that all three flip their coins the same number of times?

1
Picture one round: all three flip at once. What is the chance that all three get tails, so nobody stops?

Predict first:
Your prediction

open on YouTube

Example 11.2

AMC 10

Frieda the frog begins a sequence of hops on a $3 \times 3$ grid of squares, moving one square on each hop and choosing at random the direction of each hop: up, down, left, or right. She does not hop diagonally. When the direction of a hop would take Frieda off the grid, she "wraps around" and jumps to the opposite edge. For example if Frieda begins in the center square and makes two hops "up", the first hop would place her in the top row middle square, and the second hop would cause Frieda to jump to the opposite edge, landing in the bottom row middle square. Suppose Frieda starts from the center square, makes at most four hops at random, and stops hopping if she lands on a corner square. What is the probability that she reaches a corner square on one of the four hops?

Every state in a group sends the same chances to each group, so merging is safe.

After 0 steps, chance of Corner:

0

Chance of each state after each step
n	Center	Edge	Corner	total
0	1	0	0	1

1
Group the 9 squares by symmetry. How many different kinds of square are there?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 11.3.1

AMC 10

Amelia has a coin that lands on heads with probability $\frac13$ , and Blaine has a coin that lands on heads with probability $\frac25$ . Amelia and Blaine alternately toss their coins until someone gets a head; the first one to get a head wins. All coin tosses are independent. Amelia goes first. The probability that Amelia wins is $\frac{p}{q}$ , where $p$ and $q$ are relatively prime positive integers. What is $q - p$ ?

Problem 11.3.2

AMC 10

Debra flips a fair coin repeatedly, keeping track of how many heads and how many tails she has seen in total, until she gets either two heads in a row or two tails in a row, at which point she stops flipping. What is the probability that she gets two heads in a row but she sees a second tail before she sees a second head?

Problem 11.3.3

AMC 10

A frog sitting at the point $(1, 2)$ begins a sequence of jumps, where each jump is parallel to one of the coordinate axes and has length $1$ , and the direction of each jump (up, down, right, or left) is chosen independently at random. The sequence ends when the frog reaches a side of the square with vertices $(0, 0)$ , $(0, 4)$ , $(4, 4)$ , and $(4, 0)$ . What is the probability that the sequence of jumps ends on a vertical side of the square?

Problem 11.3.6

AMC 12Challenge

In a small pond there are eleven lily pads in a row labeled $0$ through $10$ . A frog is sitting on pad $1$ . When the frog is on pad $N$ , $0 < N < 10$ , it will jump to pad $N - 1$ with probability $\frac{N}{10}$ and to pad $N + 1$ with probability $1 - \frac{N}{10}$ . Each jump is independent of the previous jumps. If the frog reaches pad $0$ it will be eaten by a patiently waiting snake. If the frog reaches pad $10$ it will exit the pond, never to return. What is the probability that the frog will escape without being eaten by the snake?

Checkpoint for section 11.0

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

11.10%

States with Recursion

In this section you will be able to find the chance of being in each state after exactly n steps, with a table built row by row.

A cricket hops between 4 leaves, always to a different leaf. After 4 hops, what is the chance it is back where it started?

Some questions ask about a fixed number of moves, not “who wins eventually”. Then build a table: one row per step, one column per state. Each row comes from the row above it.

Look:every row of chances adds up to 1. If it doesn’t, you’ve lost a path somewhere.

Exploreplay first, formulas later

leaves4

After 0 hops: back on A =

1

Chance of each leaf after every hop
Hop	A★	each other	all leaves (total = 1)
0	1	0

Each bar is split by leaf color. Every bar is full: the chances always add up to 1.

Try this: Hop 4 times. Does each row of the table still add up to 1?
Try this: Watch leaf A. Why is its chance after a hop always (1 − its previous chance) ÷ 3?
Try this: Change to 5 leaves. Which number replaces the 3 in that rule?

Name it

Concept 11.1.1 · State Tables

For states recursions, it is often a good idea to simply make a table of the probability of being at each location at every time step. Remember: the total probability at each step must always be $1$ .

Remark 11.1.2

Recursive equations together with states are useful for questions like “After 10 moves, what is the probability of being on point $A$ ?”

“Top→Bottom” means: on the bottom face, just came down from the top.

After 1 steps, chance of Bottom→Top / Top→Top:

\tfrac{1}{3}

Chance of each state after each step
n	Bottom→Top	Top→Top	Top→Bottom	Bottom→Bottom	total
1	1/3	0	0	2/3	1

An ant on a cube (Example 11.5): each row of the table comes from the row above it.

Remark 11.1.3

The same table trick works even when probabilities are not involved. Instead, put the number of ways in each box of the table.

Each cell counts the paths that end in that state.

After 1 steps, ways to be in Bottom→Top / Top→Top:

1

Number of ways to be in each state after each step
n	Bottom→Top	Top→Top	Top→Bottom	Bottom→Bottom	total
1	1	0	0	2	3

The ant's table again, counting paths instead of chances. Each row's total doubles.

Watch itpredict, then reveal

Example 11.3

AMC

A cricket randomly hops between 4 leaves, on each turn hopping to one of the other 3 leaves with equal probability. After 4 hops what is the probability that the cricket has returned to the leaf where it started?

After 0 hops: back on A =

1

Chance of each leaf after every hop
Hop	A★	each other	all leaves (total = 1)
0	1	0

Each bar is split by leaf color. Every bar is full: the chances always add up to 1.

1
Call the start leaf $A$ , and let $p_n$ be the chance the cricket is on $A$ after $n$ hops. $p_0 = 1$ . What is $p_1$ ?

Predict first:
Your prediction

open on YouTube

Example 11.4

AMC 10

Raashan, Sylvia, and Ted play the following game. Each starts with $\$1$ . A bell rings every 15 seconds, at which time each of the players who currently have money simultaneously chooses one of the other two players independently and at random and gives $\$1$ to that player. What is the probability that after the bell has rung 2019 times, each player will have $\$1$ ? (For example, Raashan and Ted may each decide to give $\$1$ to Sylvia, and Sylvia may decide to give her dollar to Ted, at which point Raashan will have $\$0$ , Sylvia will have $\$2$ , and Ted will have $\$1$ , and that is the end of the first round of play. In the second round Raashan has no money to give, but Sylvia and Ted might choose each other to give their $\$1$ to, and the holdings will be the same at the end of the second round.)

Every state in a group sends the same chances to each group, so merging is safe.

After 0 steps, chance of 1, 1, 1:

1

Chance of each state after each step
n	1, 1, 1	2, 1, 0 (any order)	total
0	1	0	1

1
There are $\$3$ in total. Up to the order of the players, how many kinds of holdings are possible?

Predict first:
Your prediction

open on YouTube

Example 11.5

AIME

An ant makes a sequence of moves on a cube where a move consists of walking from one vertex to an adjacent vertex along an edge of the cube. Initially the ant is at a vertex of the bottom face of the cube and chooses one of the three adjacent vertices to move to as its first move. For all moves after the first move, the ant does not return to its previous vertex, but chooses to move to one of the other two adjacent vertices. All choices are selected at random so that each of the possible moves is equally likely. The probability that after exactly 8 moves that ant is at a vertex of the top face on the cube is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

1
The exact vertex doesn't matter: only which face the ant is on, and where it came from. After the first move, there are 4 different states. What are they?

Contest cornerreal contest problems

Problem 11.3.4

AIME

Lily pads $1, 2, 3, \ldots$ lie in a row on a pond. A frog makes a sequence of jumps starting on pad $1$ . From any pad $k$ the frog jumps to either pad $k + 1$ or pad $k + 2$ chosen randomly with probability $\frac12$ and independently of other jumps. The probability that the frog visits pad $7$ is $\frac{p}{q}$ , where $p$ and $q$ are relatively prime positive integers. Find $p + q$ .

Problem 11.3.5

AMC 10/12

A frog hops along the number line according to the following rules:

It starts at $0$ .
If it is at $0$ , then it moves to $1$ with probability $\frac12$ and disappears with probability $\frac12$ .
For $n = 1, 2, 3$ , if it is at $n$ , then it moves to $n + 1$ with probability $\frac14$ , to $n - 1$ with probability $\frac14$ , and disappears with probability $\frac12$ .

What is the probability that the frog reaches $4$ ?

Checkpoint for section 11.1

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

11.20%

Expected Value States

In this section you will be able to find expected numbers of steps with states: the same equations, plus 1 for the step you take.

Two equally strong tennis players play until someone wins three games in a row. On average, how many games is that?

Expected value states work just like probability states. Each state gets an unknown: the expected number of steps still to go. The only change: every equation gets a +1, for the step you are about to take.

An end state is worth $0$ : no more steps to take.

Exploreplay first, formulas later

One equation per state (expected steps left)

Each state's equation: follow every arrow out of it.

$a = 1 + \tfrac{1}{2}\,b_A + \tfrac{1}{2}\,b_B$
$b_A = 1 + \tfrac{1}{2}\,c_A + \tfrac{1}{2}\,b_B$
$b_B = 1 + \tfrac{1}{2}\,c_B + \tfrac{1}{2}\,b_A$
$c_A = 1 + \tfrac{1}{2}\,b_B$
$c_B = 1 + \tfrac{1}{2}\,b_A$

Expected steps from “Start” = (press Next step)

Try this: Why does every equation start with 1 +?
Try this: Turn on Merge symmetric states. Why are "A won 1" and "B won 1" really the same state?
Try this: Press Solve all, merged and unmerged. Do you get the same expected number of games?

Name it

Concept 11.2.1 · Expected Value States

Expected value states work almost exactly like probability states. The only difference: in every equation, we add 1. For example,

\text{expected moves from } A = \text{expected moves from } B + 1.

We add $1$ because it takes $1$ move to go from $A$ to $B$ .

Watch itpredict, then reveal

Example 11.6

SMT

Suppose two equally strong tennis players play against each other until one player wins three games in a row. The results of each game are independent, and each player will win with equal probability. What is the expected value of the number of games they will play?

1
The key idea is the symmetry between the players. How many possible states are there for the match?

Predict first:
Your prediction

Contest cornerreal contest problems

Problem 11.3.8(additional)

AIMEChallenge

Freddy the frog is jumping around the coordinate plane searching for a river, which lies on the horizontal line $y = 24$ . A fence is located at the horizontal line $y = 0$ . On each jump, Freddy randomly chooses a direction parallel to one of the coordinate axes and moves one unit in that direction. When he is at a point where $y = 0$ , with equal likelihoods he chooses one of three directions where he either jumps parallel to the fence or jumps away from the fence, but he never chooses the direction that would have him cross over the fence to where $y < 0$ . Freddy starts his search at the point $(0, 21)$ and will stop once he reaches a point on the river. Find the expected number of jumps it will take Freddy to reach the river.

Checkpoint for section 11.2

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

11.3

Practice Problems

In this section you will be able to use states and symmetry on a harder contest problem.

A particle wanders inside a square until it hits the edge. Nine starting points, but symmetry cuts them down to three states.

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

Contest cornerreal contest problems

Problem 11.3.7(additional)

AMC 12Challenge

A square is drawn in the Cartesian coordinate plane with vertices at $(2, 2)$ , $(-2, 2)$ , $(-2, -2)$ , $(2, -2)$ . A particle starts at $(0, 0)$ . Every second it moves with equal probability to one of the eight lattice points (points with integer coordinates) closest to its current position, independently of its previous moves. In other words, the probability is $1/8$ that the particle will move from $(x, y)$ to each of $(x, y + 1)$ , $(x + 1, y + 1)$ , $(x + 1, y)$ , $(x + 1, y - 1)$ , $(x, y - 1)$ , $(x - 1, y - 1)$ , $(x - 1, y)$ , or $(x - 1, y + 1)$ . The particle will eventually hit the square for the first time, either at one of the $4$ corners of the square or at one of the $12$ lattice points in the interior of one of the sides of the square. The probability that it will hit at a corner rather than at an interior point of a side is $m/n$ , where $m$ and $n$ are relatively prime positive integers. What is $m + n$ ?