Where Will the Sorting Hat Put You?

You are waiting in line to be sorted into one of the four houses of Logwarts by a fussy sorting hat. The hat refuses to place two consecutive students in the same house: if a student silently requests the house the previous student was given, the hat instead picks uniformly among the other three; otherwise it grants the request. Every student’s request is a uniformly random house, except yours.

You are tenth in line, and you will request Graphindor. The first student in line is sorted into Graphindor. At that point, what is the probability that you are sorted into Graphindor?

The Fiddler, Zach Wissner-Gross, November 8, 2024(original post)

Solution

Track only one thing: whether each student lands in Graphindor. Let $g_k$ be the probability that student $k$ is. A student reaches Graphindor only when the previous one did not, since the hat never repeats a house; and given the previous student was elsewhere, the current student lands in Graphindor with probability $\tfrac13$ (whether by requesting it and being granted, or by requesting the previous house and being bounced there). So $$g_{k+1}=\frac{1-g_k}{3},$$ and from $g_1=1$ this gives $g_2=0,\ g_3=\tfrac13,\dots,g_9=\tfrac{547}{2187}$. Your request is certainly Graphindor, and you get it exactly when the ninth student did not, so $$P(\text{you}\to\text{Graphindor})=1-g_9=1-\frac{547}{2187}= \boxed{\tfrac{1640}{2187}}\approx74.99\%.$$ The recursion has fixed point $\tfrac14$, so $g_k\to\tfrac14$ and your chance hovers just under $1-\tfrac14=\tfrac34$.

The computation

Run the line itself: start everyone’s predecessor in Graphindor, draw each student’s random request, apply the hat’s no-repeat rule, and see how often the ninth student ends up outside Graphindor (which is when you get it).

import numpy as np
rng = np.random.default_rng(0); M = 3_000_000
prev = np.zeros(M, dtype=int)              # student 1 -> Graphindor (house 0)
for k in range(2, 10):                     # students 2..9
    req, alt = rng.integers(0, 4, M), rng.integers(0, 3, M)
    prev = np.where(req == prev, (prev + 1 + alt) % 4, req)   # no-repeat: pick another house
print((prev != 0).mean())                  # ~0.7499  (you get Graphindor iff student 9 did not)

Extra Credit

Let $p=\tfrac{1640}{2187}$ be the answer above. Now you are $N$th in line with $N$ much larger than ten. You doze off, and wake to hear the hat sort some student into Graphindor; that student is equally likely to be any of the first $N-1$. What is the smallest $N$ for which your probability of Graphindor exceeds $p$?

Solution

From a known Graphindor student $d$ places ahead, the same recurrence runs forward: the student just before you is in Graphindor with probability $G_d$, where $G_0=1$ and $G_{d+1}=\tfrac{1-G_d}{3}$, and you get Graphindor with probability $1-G_d$. The heard sorting sits at a uniformly random distance $d=0,\dots,N-2$, so $$P(\text{you})=\frac{1}{N-1}\sum_{d=0}^{N-2}\bigl(1-G_d\bigr),$$ which rises toward $\tfrac34$ from below. Since $\tfrac34-p=\tfrac{1}{8748}$ is tiny, $N$ must be large; the first one that pushes $P(\text{you})$ above $p$ is $$N=\boxed{4922}.$$

The computation

Iterate the exact recurrence for $G_d$, accumulate the running average of $1-G_d$, and stop at the first $N$ whose average exceeds $p$.

from fractions import Fraction as F
p = F(1640, 2187)
G, ssum, N = F(1), F(0), 1                 # G_0 = 1
while True:
    N += 1; ssum += 1 - G                  # add the d = N-2 term
    if ssum / (N - 1) > p: break
    G = (1 - G) / 3                        # advance to the next distance
print(N)                                    # 4922