Chapter 157

Is This Bathroom Occupied?

Riddler Express

A class of $30$ children and their teacher stand in a circle, $31$ people in all. The teacher holds a fair coin and a potato. On each turn the teacher tosses the coin: whoever holds the potato passes it left on heads and right on tails. The game ends when every child except one has held the potato, and the remaining child wins. What is each child’s probability of winning?

The Riddler, FiveThirtyEight, August 4, 2017(original post)

Solution

Surprisingly, every child has the same probability of winning, $1/30$ , independently of where they stand in the circle.

Fix a child Carol, and let Anna and Bob be her two immediate neighbours in the circle (one of them may be the teacher). The potato starts with the teacher and moves by a simple symmetric random walk on the circle until it has visited every child but one. Carol wins precisely when she is the only child never visited, which is the same as saying that the potato reaches Anna and Bob without ever first reaching Carol, and at the moment the potato first lands on the second of the two, it has already touched every other child.

The cleanest way to see why $1/30$ comes out is to condition on which neighbour the potato visits first. Suppose the potato hits Anna before Bob. For Carol to win, the potato must after that moment travel all the way around the ring through the remaining $28$ children and land on Bob before ever coming back to Carol. The position of the potato is a random walk on the circle; once it stands on Anna, what matters is whether it reaches Bob before Carol. Lay the $30$ children out as a line by cutting the circle at Carol; Anna sits one step from Carol on one side and Bob is $29$ steps away on the other. The probability that an unbiased random walk starting at Anna reaches Bob before Carol is, by the standard gambler’s-ruin formula on a line of length $30$ , $\Pr(\text{reach Bob before Carol} \mid \text{start at Anna}) = \frac{1}{30}.$ By the same argument, if the potato hits Bob first, Carol’s winning probability is again $1/30$ (the picture is the mirror image). The two cases are mutually exclusive and exhaust all possibilities, so the unconditional probability is the same weighted average, $\Pr(\text{Carol wins}) = \frac{1}{30}.$ Carol was an arbitrary child, so every child has the same chance of winning.

$\boxed{\,\Pr(\text{each child wins}) = \tfrac{1}{30}.\,}$

A neat sanity check: the $30$ children’s probabilities must sum to $1$ , since exactly one child is left out, and $30 \cdot 1/30 = 1$ . The teacher plays the role of starting position, not of a winner.

The computation

Simulate the actual game many times and tally how often each position survives unvisited. The simulator starts the potato with the teacher (index $0$ ) and tracks the set of visited children (indices $1$ to $30$ ); the game ends when $29$ of the $30$ children have been visited.

Place $31$ players around a circle, indexing the teacher $0$ and the children $1, \ldots, 30$ .
Hold the potato at index $0$ . Repeatedly flip a fair coin and move the potato $+1$ or $-1$ mod $31$ .
Record the set of children visited; stop when $29$ distinct children have held it.
The remaining child is the winner; tally the winner index over many trials.

import random
def play(rng):
    pos = 0
    visited = set()
    while len(visited) < 29:
        pos = (pos + (1 if rng.random() < 0.5 else -1)) % 31
        if pos != 0:
            visited.add(pos)
    survivor = (set(range(1, 31)) - visited).pop()
    return survivor

rng = random.Random(0)
wins = [0] * 31
trials = 300_000
for _ in range(trials):
    wins[play(rng)] += 1
print([round(wins[i] / trials, 4) for i in range(1, 31)])
# all entries close to 0.0333 = 1/30

Each child’s empirical win rate clusters tightly around $0.0333 = 1/30$ , confirming the uniform distribution.

Riddler Classic

An office bathroom has one toilet and a sign on the door that slides between “Vacant” and “Occupied”. Of the people who use the bathroom, $1/3$ are oblivious to the sign and never touch it (group U), $1/3$ slide it to “Occupied” on entering but forget to reset it on leaving (group S), and $1/3$ are conscientious: “Occupied” on entering, “Vacant” on leaving (group C). The bathroom is occupied exactly half of the time. Two questions: (a) given the sign reads “Occupied”, what is the probability the bathroom really is occupied? (b) given the sign reads “Vacant”, what is the probability the bathroom really is vacant? Extra credit: what happens as the fraction of conscientious users varies?

The Riddler, FiveThirtyEight, August 4, 2017(original post)

Solution

The key observation is that a U-user neither reads nor changes the sign, so the sign you see is determined by the most recent non-U user to have used the bathroom, together with whether that user is still inside. Equivalently, walk backwards through the stream of users until you find the first non-U (call them the latest setter); the sign reads whatever the latest setter left.

If the latest setter was a C and has left, the sign reads “Vacant”.
If the latest setter was a C and is still inside, the sign reads “Occupied”.
If the latest setter was an S (whether still inside or not), the sign reads “Occupied”.

Because among the non-U users C and S are equally likely (each $1/3$ of the population), the latest setter is independently either C or S, each with probability $1/2$ . We assume this independence: the type of the most recent non-U user is independent of whether the bathroom is occupied right now, which holds when bathroom occupancy at a random moment is governed by user arrival/departure statistics symmetric across types.

Building the joint distribution. Write $O$ and $V$ for “occupied” and “vacant” (the truth), and “Occ” / “Vac” for what the sign reads. Each visit is a Bernoulli trial: with probability $1/2$ the bathroom is occupied, and (given occupied) the current user is one of C, S, U each with probability $1/3$ . The latest non-U setter, independently, is C or S with probability $1/2$ each. Tabulating:

Occupied by C ( $1/6$ ): C entered, set sign to “Occupied”, currently inside, so $\text{Occ}$ .
Occupied by S ( $1/6$ ): S entered, set sign to “Occupied”, currently inside, so $\text{Occ}$ .
Occupied by U ( $1/6$ ): U doesn’t touch the sign; the sign reads what the latest non-U setter left. If they were S ( $1/2$ ) the sign reads “Occupied”; if C ( $1/2$ ) the sign reads “Vacant”. Contribution: $1/12$ each to $(\text{Occ}, O)$ and $(\text{Vac}, O)$ .
Vacant ( $1/2$ ): no one is inside, so the sign reads whatever the latest non-U setter left. S ( $1/2$ ) gives “Occupied”; C ( $1/2$ ) gives “Vacant”. Contribution: $1/4$ each to $(\text{Occ}, V)$ and $(\text{Vac}, V)$ .

Part (a). Add up the joint masses with sign reading “Occupied”: $\Pr(\text{Occ}) = \tfrac{1}{6} + \tfrac{1}{6} + \tfrac{1}{12} + \tfrac{1}{4} = \tfrac{2}{3}.$ Of this, the bathroom is genuinely occupied with mass $\tfrac{1}{6} + \tfrac{1}{6} + \tfrac{1}{12} = \tfrac{5}{12}$ . Hence $\Pr(O \mid \text{Occ}) = \frac{5/12}{2/3} = \frac{5}{8} = 62.5\%.$

Part (b). The remaining mass is $\Pr(\text{Vac}) = 1 - 2/3 = 1/3$ , of which the bathroom really is vacant with mass $1/4$ , so $\Pr(V \mid \text{Vac}) = \frac{1/4}{1/3} = \frac{3}{4} = 75\%.$

$\boxed{\,\Pr(O \mid \text{Occ}) = \tfrac{5}{8},\quad \Pr(V \mid \text{Vac}) = \tfrac{3}{4}.\,}$

A vacant sign is the more trustworthy of the two: only a C user can have set it to “Vacant”, and even after they leave a U-user inside is the only way for the sign to be wrong. The “Occupied” sign, by contrast, is contaminated by S-users who leave it set whether they are inside or not.

Extra credit. Replace the equal thirds by population shares $c, s, u$ with $c + s + u = 1$ , and condition the latest setter on being C or S, with probabilities $c/(c+s)$ and $s/(c+s)$ . The same construction yields $\begin{aligned} \Pr(O \mid \text{Occ}) &= \frac{(c+s)/2 + (u/2)\cdot s/(c+s)} {(c+s)/2 + (u/2)\cdot s/(c+s) + (1/2)\cdot s/(c+s)}, \\[6pt] \Pr(V \mid \text{Vac}) &= \frac{(1/2)\cdot c/(c+s)} {(1/2)\cdot c/(c+s) + (u/2)\cdot c/(c+s)} = \frac{1}{1 + u}. \end{aligned}$ The “Vacant” reliability depends only on the U fraction, dropping from $1$ (no obvious U-users) to $1/2$ (everyone is a U-user). The “Occupied” reliability climbs from $1/2$ (all S) to $1$ (all C), monotone in the C share. Intuition: conscientious users make every sign more accurate; oblivious users only degrade the “Vacant” reading.

The computation

Simulate an event-driven model: an infinite queue of visitors, each independently C, S, or U; bathroom occupancy alternates between empty and occupied for a single visitor. Track sign state and bathroom truth at random sampling moments.

Generate a stream of $N$ visitors with i.i.d. types in $\{C, S, U\}$ .
Alternate occupied / vacant intervals of equal expected length (one visitor per occupied interval, one “gap” of independent length between).
At the start of each gap and at the start of each occupied interval, record (sign reading, truth).
Estimate $\Pr(O \mid \text{Occ})$ and $\Pr(V \mid \text{Vac})$ .

import random
rng = random.Random(0)
N = 400_000
sign = "Vac"
samples = []
for _ in range(N):
    t = rng.choice("CSU")
    if t == "C": sign_enter = "Occ"; sign_exit = "Vac"
    elif t == "S": sign_enter = "Occ"; sign_exit = "Occ"
    else: sign_enter = sign_exit = sign
    # gap before user: vacant interval
    samples.append((sign, "V"))
    sign = sign_enter
    # while user is inside: occupied interval
    samples.append((sign, "O"))
    sign = sign_exit

occ_total = sum(1 for s, _ in samples if s == "Occ")
occ_true  = sum(1 for s, t in samples if s == "Occ" and t == "O")
vac_total = sum(1 for s, _ in samples if s == "Vac")
vac_true  = sum(1 for s, t in samples if s == "Vac" and t == "V")
print(round(occ_true / occ_total, 4))   # ~0.625 = 5/8
print(round(vac_true / vac_total, 4))   # ~0.75  = 3/4

Each side is sampled at uniform rate (one observation per visitor-arrival and one per visitor-departure), and the bathroom is occupied half the time by construction. The empirical conditionals match $5/8$ and $3/4$ to three digits.