Problem
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?
Solution
from random import sample
= 10000
runs = 1000
n = 0
total_occupancy for _ in range(runs):
= set(range(n))
remaining_houses = []
chosen_houses while remaining_houses:
= sample(remaining_houses, 1)[0]
chosen_house
chosen_houses.append(chosen_house)
remaining_houses.discard(chosen_house)for adj in [-1, 1]:
+ adj)
remaining_houses.discard(chosen_house += len(chosen_houses)
total_occupancy print(total_occupancy/(n*runs))
The fraction of the occupied houses for large \(n\) is approximately is \(0.4325773\).