The Puzzle Of Misanthropic Neighbours

The misanthropes are coming. Suppose there is a row of some number, $N$, of houses in a new, initially empty development. Misanthropes are moving into the development one at a time and selecting a house at random from those that have nobody in them and nobody living next door. They keep on coming until no acceptable houses remain. At most, one out of two houses will be occupied; at least one out of three houses will be. But what’s the expected fraction of occupied houses as the development gets larger, that is, as $N$ goes to infinity?

The Riddler, FiveThirtyEight(original post)

Solution

Let $E_n$ be the expected number of occupied houses in a clean row of $n$, meaning a block with empty houses and no occupied neighbour just outside either end. The first misanthrope picks one of the $n$ houses uniformly. If they take house $k$, that house is occupied and houses $k-1$ and $k+1$ become forbidden, splitting what remains into two independent clean rows of lengths $k-2$ and $n-k-1$. Averaging over $k$, and using that the two pieces contribute symmetrically, $$E_n = 1 + \frac{2}{n}\sum_{j=0}^{n-2} E_j, \qquad E_0 = 0,\ E_1 = 1.$$

To extract the large-$n$ behaviour, gather the $E_n$ into the generating function $G(x) = \sum_{n\ge 0} E_n x^n$. Multiplying the recurrence by $n x^n$ and summing turns it into the differential equation $$G'(x) = \frac{1}{(1-x)^2} + \frac{2x}{1-x}\,G(x),$$ a first-order linear ODE. Its integrating factor is $(1-x)^2 e^{2x}$, and solving with $G(0)=0$ gives the closed form $$G(x) = \frac{1 - e^{-2x}}{2\,(1-x)^2}.$$ Now read off the density. The factor $1/(1-x)^2 = \sum (n+1)x^n$ carries coefficients growing like $n$, while the analytic factor $(1-e^{-2x})/2$ tends to $(1-e^{-2})/2$ as $x \to 1$. So $E_n / n$ converges to that constant, and the limiting occupied fraction is $$\lim_{N\to\infty} \frac{E_N}{N} = \frac{1 - e^{-2}}{2} \approx \boxed{0.4323}.$$ This sits, as promised, between $\tfrac13$ and $\tfrac12$.

The computation

Run the development directly: repeatedly pick a uniformly random house that is empty with empty neighbours, occupy it, forbid its neighbours, and continue until none remain. For a long row the occupied fraction settles near $0.4323$.

import numpy as np
rng = np.random.default_rng(0)
n, runs = 2000, 4000
total = 0
for _ in range(runs):
    free = set(range(n)); occupied = 0
    while free:
        h = rng.choice(list(free))       # a random allowed house
        occupied += 1
        free.discard(h)
        free.discard(h - 1); free.discard(h + 1)   # forbid neighbours
    total += occupied
print(total / (n * runs))                # ~0.4323 = (1 - e**-2) / 2