Probability recurrence relations: two University of Tokyo problems explained

What is a probability recurrence relation?

A probability recurrence describes how a probability changes after successive steps of a random process. It combines probability with sequences: define the state probabilities, find how one step redistributes them, and solve the resulting recurrence.

These problems need not involve calculus or advanced probability. The main challenge is often choosing a small enough set of states. The two University of Tokyo entrance-exam problems below illustrate this especially well. The explanations and solutions here are the author's own.

Two problems to try

Problem 1: rolling a regular tetrahedron

A regular tetrahedron rests on a plane. At each step, one of the three edges of the face in contact with the plane is chosen with equal probability, and the tetrahedron is rolled over that edge onto the adjacent face.

Find the probability that, after $n$ steps, the face originally in contact with the plane is again in contact with it.

University of Tokyo, 1991 science-track mathematics, Problem 1.

Problem 2: a random walk through nine rooms

An equilateral triangle is divided into nine triangular rooms as shown below. A ball starts in room $P$. Every second, it moves to one of the rooms sharing an edge with its current room, choosing each available adjacent room with equal probability. It never stays in the same room.

Find the probability that the ball is in room $Q$ after $n$ seconds.

University of Tokyo, 2012 humanities-track Problem 3 and science-track Problem 2.

The basic method

Define probabilities as sequences

For Problem 1, let $p_n$ be the probability that the original face is in contact with the plane after $n$ rolls. Giving the desired probability a name is the first step toward relating it to the previous step.

Draw a transition diagram

Suppose a process has two states, $A$ and $B$, with probabilities $p_n$ and $1-p_n$ after $n$ steps. Suppose it stays in its current state with probability $1/3$ and changes state with probability $2/3$.

The arrows describe conditional probabilities of the next state given the current state. To compute the probability of arriving in $A$, add the contributions from both possible starting states:

$$p_{n+1}=\frac13p_n+\frac23(1-p_n).$$

This is the law of total probability written as a recurrence.

Find an initial value and solve

A first-order affine recurrence has the form $p_{n+1}=ap_n+b$. If $a\ne1$, its fixed point is $L=b/(1-a)$. Subtracting it gives

$$p_{n+1}-L=a(p_n-L),$$

so

$$p_n=L+(p_0-L)a^n.$$

For the transition diagram above, $a=-1/3$ and $L=1/2$, giving

$$p_n=1/2+(p_0-1/2)(-1/3)^n.$$

Five useful checks and shortcuts

1. Reduce the number of states using symmetry and parity

In Problem 1, the original face is special, but the other three faces are symmetric. Track whether the original face is down rather than tracking all four faces separately.

In Problem 2, the ball alternates between two groups of rooms. Separating even and odd times dramatically reduces the number of states that need to be considered.

2. Use the fact that probabilities sum to one

If $q_n$ is the probability that some other face is down in Problem 1, then $q_n=1-p_n$. There is no need to introduce a second independent sequence.

3. Treat unexpectedly large systems as a reason to reconsider the states

These examples can both be reduced to a single recurrence. In other problems a larger system may be necessary, but before doing a long calculation, check whether states are symmetric or whether looking every two steps simplifies the process.

When combining states, verify that the transition probabilities to the groups are consistent for the individual states being combined. Symmetry helps justify this; grouping arbitrary states may not.

4. Start at time zero

An initial value does not have to be the value after one step. At time zero, the tetrahedron certainly has its original face down, and the ball is certainly in room $P$. These observations give initial values without any probability calculation.

5. Check small cases and limiting behavior

Substitute $n=0,1,2$ when you can calculate those probabilities directly. A limit can also be a useful check, but take care with periodic processes: in Problem 2 the full sequence does not have a single limit because all odd-time probabilities are zero.

Solution to Problem 1: the tetrahedron

Choose two states

Call the original face $A$, and let $p_n$ be the probability that $A$ is down after $n$ rolls. The complementary state, “one of the other three faces is down,” has probability $1-p_n$.

• From $A$, the next roll always moves to another face.
• From any other face, exactly one of the three possible rolls returns to $A$, while the remaining two lead to other faces.

Thus

$$p_{n+1}=\frac13(1-p_n),\qquad p_0=1.$$

Solve the recurrence

The fixed point is $1/4$, so

$$p_{n+1}-\frac14=-\frac13\left(p_n-\frac14\right).$$

Therefore

$$p_n-\frac14=\left(-\frac13\right)^n\left(1-\frac14\right),$$

and the answer is

$$\boxed{p_n=\frac14+\frac34\left(-\frac13\right)^n.}$$

For $n\ge1$, an equivalent form is $\frac14\{1-(-\frac13)^{n-1}\}$.

Check the answer

The formula gives $p_0=1$, $p_1=0$, and $p_2=1/3$, as expected. As $n$ tends to infinity, it tends to $1/4$, consistent with the four symmetric faces.

Solution to Problem 2: the triangular rooms

Use reflection symmetry

Label the rooms as in the diagram below. The two rooms marked $C$ are reflections of one another, and one of them is $Q$. Rooms bearing the same letter have equal probabilities by reflection symmetry.

Tracking all six labels separately still looks cumbersome. Parity provides the next simplification.

Separate even and odd times

Starting from $P$:

• After an even number of steps, the ball is in $P$ or one of the two $C$ rooms.
• After an odd number of steps, it is in an $A$, $B$, $D$, or $E$ room.

This follows by induction. It holds at time zero, and every shared edge connects one of these groups to the other. Hence the desired probability is zero for odd $n$.

For even $n$, let $c_n$ be the probability of being in either $C$ room. The probability of being in $P$ is $1-c_n$, and by reflection symmetry the probability of being in $Q$ is $c_n/2$.

Calculate transitions over two seconds

From $P$, the first step goes to $A$ or either of the two $B$ rooms, each with probability $1/3$. The room $A$ leads straight back to $P$. Each $B$ room has two neighbors, $P$ and a $C$ room. Hence the two-step probability of moving from $P$ to the $C$ group is

$$2\times\frac13\times\frac12=\frac13.$$

From either $C$ room, the first step goes to its neighboring $B$, $D$, or $E$ room, each with probability $1/3$. Only the route through $B$ can reach $P$ on the next step, and it does so with probability $1/2$. Thus the two-step probability of moving from the $C$ group to $P$ is

$$\frac13\times\frac12=\frac16.$$

The probability of remaining in the $C$ group after two steps is consequently $5/6$.

Each arrow represents two seconds of elapsed time, from $n$ to $n+2$.

Solve the recurrence at even times

For even $n$,

$$c_{n+2}=\frac56c_n+\frac13(1-c_n)=\frac12c_n+\frac13,\qquad c_0=0.$$

Subtract the fixed point $2/3$:

$$c_{n+2}-\frac23=\frac12\left(c_n-\frac23\right).$$

Writing $n=2k$ gives

$$c_{2k}=\frac23\left(1-\left(\frac12\right)^k\right).$$

Since $Q$ is one of the two equally likely $C$ rooms, the required probability is

$$\boxed{\Pr(X_n=Q)=\begin{cases}0,&n\text{ odd},\\[3pt]\displaystyle\frac13\left(1-\left(\frac12\right)^{n/2}\right),&n\text{ even}.\end{cases}}$$

Check the answer

At time zero the probability is zero. After two seconds, the only route to $Q$ is through the adjacent $B$ room, giving $1/3\times1/2=1/6$, which agrees with the formula.

Along even times, the probability tends to $1/3$. The three downward-pointing rooms $P$ and the two $C$ rooms are symmetric under a rotation of the entire triangle. Along odd times the probability is always zero, so the full sequence does not converge.

What to take away

Choose states before doing algebra. Symmetry can identify equal probabilities; the total-probability condition can remove a variable; and parity can suggest looking at two steps at a time. Once those choices are right, an apparently complicated random process may reduce to a single affine recurrence.

For another example of choosing a method from the structure of a problem, see three strategies for integer problems.