The Randy Hall Problem

A game show has three doors in a row, $1$, $2$, $3$. 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 $2$, a move goes to $1$ or $3$ with equal chance, and the host fixes a $20$ percent chance of staying at door $2$. You want each door to be almost equally likely after many presses. What stay probability should the button give at door $1$ (and door $3$)?

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

Solution

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

The computation

Build the transition matrix for $p=0.6$ and read off its stationary distribution (the left eigenvector for eigenvalue $1$). It is uniform, $\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

Now door $2$’s stay probability alternates: $20$ percent on the odd presses, $50$ percent on the even ones. What stay probability $p$ at doors $1$ and $3$ makes the doors equally likely in the long run?

Solution

The walk now has period two, so its distribution oscillates; we ask that the time-average be uniform. Writing the door-$2$ probability after an odd and an even press in terms of $p$ and averaging, the uniform condition $\overline{\pi_2}=\tfrac13$ reduces to a quadratic, $$40p^2 - 13p - 9 = 0,\qquad p = \frac{13+\sqrt{1609}}{80} \approx \boxed{0.664}.$$ The alternating stickiness at door $2$ pushes the required stay probability up from $0.6$ to about $0.664$. (The source’s value is behind its paywall; this is my own.)

The computation

Compose the two alternating press-matrices into one two-step cycle, take its stationary distribution, average over the odd and even half-steps, and solve for the $p$ that levels doors $1$ and $2$.

from scipy.optimize import brentq
def avg_pi(p):
    Mo = np.array([[p, 1-p, 0], [0.4, 0.2, 0.4], [0, 1-p, p]])     # odd press
    Me = np.array([[p, 1-p, 0], [0.25, 0.5, 0.25], [0, 1-p, p]])   # even press
    w, v = np.linalg.eig((Mo@Me).T); po = np.real(v[:, np.argmin(abs(w-1))]); po /= po.sum()
    return (po + po@Mo)/2
p = brentq(lambda p: avg_pi(p)[0] - avg_pi(p)[1], 0.4, 0.9)
print(round(p, 5), (13 + np.sqrt(1609))/80)                  # 0.66390  0.66390