Chapter 141

The Toddler at the Couch and the Ten Dwarves

The Riddler for March 24, 2017. The Express is a random walk on the non-negative integers where the baby’s bias toward home gives a clean geometric stationary distribution; the Classic is a parity-based hat puzzle in which one dwarf sacrifices himself to save the other nine for certain.

Riddler Express

A baby is learning to walk. She begins at the couch. When she is at the couch, with probability $1/4$ she steps forward and with probability $3/4$ she stays put. When she is one or more steps away from the couch, with probability $1/4$ she steps forward, with probability $1/4$ she stays, and with probability $1/2$ she steps back toward the couch. In the long run, what fraction of the time does she cling to the couch?

The Riddler, FiveThirtyEight, March 24, 2017(original post)

Solution

Number the states $0,1,2,\ldots$ by the baby’s distance from the couch in steps. The chain has a bias toward home: from any state $i\ge 1$ the chance of stepping back ( $1/2$ ) is twice the chance of stepping forward ( $1/4$ ). That alone tells us the stationary distribution exists and decays geometrically, and a short balance argument pins the rate.

Let $\pi_i$ be the long-run probability of state $i$ . For the chain to be in equilibrium, the flow from $i$ to $i+1$ must match the reverse flow from $i+1$ to $i$ : $\pi_i \cdot \tfrac{1}{4} \;=\; \pi_{i+1} \cdot \tfrac{1}{2}, \qquad i = 0, 1, 2, \ldots$ The forward rate is $1/4$ at every state (state $0$ and every $i\ge 1$ agree on this), and the back rate is $1/2$ at every $i\ge 1$ . Solving the balance gives $\pi_{i+1} = \pi_i / 2$ , so $\pi_i = \pi_0 \cdot 2^{-i}.$ The probabilities sum to $1$ : $1 \;=\; \sum_{i=0}^{\infty} \pi_0 \cdot 2^{-i} \;=\; 2\pi_0,$ so $\pi_0 = 1/2$ . The baby clings to the couch $\boxed{\,\pi_0 = \tfrac{1}{2}\, = 50\%\,}$ of the time in the long run.

The computation

Encode the random walk directly: simulate the baby step by step under the stated transition rules and report the fraction of steps spent at state $0$ . The chain is positive recurrent, so the empirical fraction converges to the stationary $\pi_0$ regardless of the starting state.

import random
def simulate(N=2_000_000, seed=0):
    rng = random.Random(seed)
    pos = 0
    at_couch = 0
    for _ in range(N):
        if pos == 0:
            at_couch += 1
            if rng.random() < 0.25: pos = 1            # else stay
        else:
            u = rng.random()
            if u < 0.25:    pos += 1                   # forward
            elif u < 0.50:  pass                       # stay
            else:           pos -= 1                   # back toward couch
    return at_couch / N

print(f"empirical pi_0 = {simulate():.4f}")
# empirical pi_0 = 0.5001

Riddler Classic

A troll captures $10$ dwarves and lines them up shortest to tallest, so each dwarf sees the dots on the heads of every shorter dwarf in front of him but cannot see his own dot or those of the taller dwarves behind. A white or black dot is placed on each head, uniformly at random and independently. Starting with the tallest, each dwarf announces a colour. A wrong answer means death; a right answer means freedom. Each dwarf hears the previous answers but does not know whether they were right. The dwarves plan overnight. What strategy minimises the expected deaths, and how many dwarves can they save for sure? Extra credit: what if there are only five dwarves?

The Riddler, FiveThirtyEight, March 24, 2017(original post)

Solution

The dwarves can save $9$ of the $10$ for certain. The tenth, the tallest, has only a $50\%$ chance of survival because his guess depends on a fair coin flip he cannot influence. The strategy is the standard parity trick.

The plan. Treat black as $0$ and white as $1$ . Before the morning, the dwarves agree on a parity convention: the tallest dwarf announces “white” if he sees an odd number of white dots in front of him, and “black” if he sees an even number. He has no information about his own dot, so his guess is right exactly when his own dot agrees with the parity he announced; that happens with probability $1/2$ .

From that announcement every dwarf below can deduce his own dot. The second-tallest dwarf knows the parity $P$ that the tallest reported. He sees the dots of the $8$ dwarves in front of him; call the count of whites among them $W_8$ . The total count of whites that the tallest saw is $W_8$ plus this dwarf’s own dot $d$ . So $d \;=\; P \oplus (W_8 \bmod 2),$ where $\oplus$ is XOR (addition modulo $2$ ). The second-tallest announces $d$ correctly and walks free. The third-tallest then hears two announcements: the first is the parity $P$ , the second is the dot $d$ that the second-tallest had on his head. Subtracting both from his own count gives the parity of whites among the dwarves still ahead of him, which determines his own dot. And so on down the line: every dwarf below the tallest deduces his own dot with certainty.

So the strategy guarantees that the $9$ shorter dwarves all live, and the tallest survives with probability $1/2$ . The boxed answer:

Why no strategy does better.

The tallest dwarf’s announcement is a function of the $9$ dots he sees. His own dot is independent of those $9$ and uniform; whatever rule he uses, the chance his announcement equals his own dot is $1/2$ . So his survival probability is capped at $1/2$ over all strategies, and the parity scheme already attains it while preserving certainty for everyone else.

Extra credit

What if there are only five dwarves?

The argument is the same. The tallest sacrifices himself with parity, and the other four deduce their dots in turn. The strategy saves $4$ for sure and $5$ half the time, for expected survivors $4.5$ out of $5$ . The boxed answer: $\boxed{\,\text{$4$ dwarves saved for sure, expected survivors }= 4.5.\,}$

The general pattern is the same for any $N$ : the tallest is saved with probability $1/2$ and the other $N-1$ are saved for certain, so the expected survivors are $N - 1/2$ .

The computation

Verify by exhaustive simulation. For $N=10$ and $N=5$ , enumerate the strategy on all $2^N$ dot patterns and confirm: the tallest is right on exactly half, and every other dwarf is right always.

Generate every length- $N$ binary string (each dot black or white).
Apply the parity strategy: the tallest’s announcement is the XOR of the dots he sees.
Each later dwarf deduces his own dot by XOR-ing the announcements made so far with the dots he sees ahead.
Count survivors per pattern; report the average and the per-position survival rate.

from itertools import product
def survivors(N):
    total = 0
    per_pos = [0] * N                                  # 0 = tallest, N-1 = shortest
    for hats in product([0, 1], repeat=N):
        # hats[0] = tallest's own dot, hats[i] visible to all j < i
        # Strategy: announcement[0] = XOR of hats[1..N-1] (parity tallest sees)
        announce = [0] * N
        announce[0] = sum(hats[1:]) % 2
        # later dwarves: hats[i] = (sum of announcements so far on dots) XOR
        # (XOR of dots ahead seen) XOR (announce[0])
        for i in range(1, N):
            seen_ahead = sum(hats[i+1:]) % 2
            prior_dots = sum(announce[1:i]) % 2        # dots called by dwarves above i
            announce[i] = announce[0] ^ seen_ahead ^ prior_dots
        alive = [announce[i] == hats[i] for i in range(N)]
        total += sum(alive)
        for i, a in enumerate(alive):
            per_pos[i] += int(a)
    avg = total / 2**N
    rates = [c / 2**N for c in per_pos]
    return avg, rates

for N in (5, 10):
    avg, rates = survivors(N)
    print(f"N={N:2d}: expected survivors = {avg}, per-position survival = {rates}")
# N= 5: expected survivors = 4.5,  per-position = [0.5, 1.0, 1.0, 1.0, 1.0]
# N=10: expected survivors = 9.5,  per-position = [0.5, 1.0, ..., 1.0]