Library · The Fiddler: Solutions · Chapter 50

The Randy Hall Problem

Revised Report an error

A game show has three doors in a row, 11, 22, 33. A contestant starts at one door and presses a button many times; each press either keeps them put or moves them to an adjacent door. From door 22, a move goes to 11 or 33 with equal chance, and the host fixes a 2020 percent chance of staying at door 22. You want each door to be almost equally likely after many presses. What stay probability should the button give at door 11 (and door 33)?

The Fiddler, Zach Wissner-Gross, November 7, 2025(original post)

The three-door walk. Door 2 stays put with probability 0.2 ; doors 1 and 3 stay with probability p , the value to be tuned.
The three-door walk. Door 22 stays put with probability 0.20.2; doors 11 and 33 stay with probability pp, the value to be tuned.

Solution

Call the stay probability at doors 11 and 33 by pp. We want the long-run distribution to be uniform, 13\tfrac13 at each door. The only ways to arrive at door 22 are to stay there (probability 0.20.2) or to step in from door 11 or door 33 (each leaving with probability 1−p1-p). Balance at door 22 with every door at 13\tfrac13, 13=13(1−p)+13(1−p)+13(0.2)  ⟹  1=2(1−p)+0.2,\tfrac13 = \tfrac13(1-p) + \tfrac13(1-p) + \tfrac13(0.2) \;\Longrightarrow\; 1 = 2(1-p) + 0.2, so 2(1−p)=0.82(1-p)=0.8 and p=35.p = \boxed{\tfrac35}.

The computation

Build the transition matrix for p=0.6p=0.6 and read off its stationary distribution (the left eigenvector for eigenvalue 11). It is uniform, 13\tfrac13 at every door.

import numpy as np
p = 0.6
M = np.array([[p, 1-p, 0], [0.4, 0.2, 0.4], [0, 1-p, p]])    # rows sum to 1
w, v = np.linalg.eig(M.T); s = np.real(v[:, np.argmin(abs(w-1))])
print(np.round(s/s.sum(), 4))                                # [0.3333 0.3333 0.3333]

Extra Credit

Moving from door 22 still takes a contestant to door 11 or door 33 with equal chance. But on odd-numbered presses (the first, third, fifth and so on) there is a 2020 percent chance of staying at door 22, and on even-numbered presses a 5050 percent chance. The behaviour at doors 11 and 33 does not depend on the press number. You want the three doors to be nearly equally likely after a large even number of presses. What should the stay probability at door 11 (and door 33) be?

Solution

The rule now changes from press to press, so a single press has no steady state. A pair of presses does, though: an odd press followed by an even press is always the same random step. After a large even number of presses, the contestant has taken many of these double steps. The double step can reach every door and can stay put, so its distribution settles to one long-run distribution from any starting door. We want that distribution to be uniform, 13\tfrac13 at each door.

So start from 13\tfrac13 at each door, apply one odd press and then one even press, and ask for 13\tfrac13 at each door again. Call the stay probability at doors 11 and 33 by pp.

After the odd press. Door 11 keeps a share pp of its own 13\tfrac13 and receives 0.40.4 of door 22’s 13\tfrac13 (half of the 8080 percent that leaves door 22). So it holds (p+0.4)/3(p + 0.4)/3, and door 33 holds the same. Door 22 keeps 0.20.2 of its share and receives 1−p1-p from each side, so it holds (2(1−p)+0.2)/3=(2.2−2p)/3(2(1-p) + 0.2)/3 = (2.2 - 2p)/3.

After the even press. Door 22 now keeps half its share and again receives 1−p1-p from each side. Setting the result equal to 13\tfrac13 and multiplying by 33: 2(1−p)(p+0.4)+0.5 (2.2−2p)  =  1.2(1-p)(p + 0.4) + 0.5\,(2.2 - 2p) \;=\; 1 . Expanding gives −2p2+0.2p+0.9=0-2p^2 + 0.2p + 0.9 = 0, or 20p2−2p−9=020p^2 - 2p - 9 = 0. Doors 11 and 33 are mirror images, so once door 22 holds 13\tfrac13 the other two share the rest equally, and all three are level. The positive root is  p  =  1+18120  ≈  0.7227 \boxed{\ p \;=\; \frac{1 + \sqrt{181}}{20} \;\approx\; 0.7227 \ }

The word “even” matters. With this pp, after a large odd number of presses the doors are not level: the last press was a slippery 2020 percent one, and door 22 holds only about 2525 percent while doors 11 and 33 hold about 3737 percent each. The extra stickiness at door 22 on even presses is what lets door 22 catch up, and it requires doors 11 and 33 to be stickier too, 0.720.72 against 0.60.6 in the main puzzle.

The computation

The check does not use the double-step equation. It runs the actual alternating process: starting with the contestant at door 11, it applies 20002000 presses in order, each with the stay chance at door 22 that its press number dictates, and then searches for the pp that leaves door 22 with exactly 13\tfrac13. It also shows the distribution after an odd number of presses, and from a different starting door.

import numpy as np
from scipy.optimize import brentq
def press(p, stay2):
    return np.array([[p, 1-p, 0], [(1-stay2)/2, stay2, (1-stay2)/2], [0, 1-p, p]])
def after_presses(p, n=2000, start=0):
    dist = np.zeros(3); dist[start] = 1
    for k in range(1, n + 1):                     # press number k
        dist = dist @ press(p, 0.2 if k % 2 else 0.5)
    return dist
p = brentq(lambda p: after_presses(p)[1] - 1/3, 0.5, 0.95, xtol=1e-14)
print("p = %.10f" % p)
print("after 2000 presses:", np.round(after_presses(p), 6))
print("after 2001 presses:", np.round(after_presses(p, 2001), 6))
print("starting at door 2:", np.round(after_presses(p, 2000, start=1), 6))

It prints

p = 0.7226812024
after 2000 presses: [0.333333 0.333333 0.333333]
after 2001 presses: [0.374227 0.251546 0.374227]
starting at door 2: [0.333333 0.333333 0.333333]

The value of pp matches (1+181)/20=0.72268120…(1+\sqrt{181})/20 = 0.72268120\ldots to the ten places shown.

Report an error on this page

Reports are stored by Netlify. See the privacy note.