Skip to content
Get started

Couples filling a long bench

A very long bench has NN seats in a row. Couples arrive one at a time. Each couple picks, uniformly at random, one of the pairs of adjacent seats that are both still empty, and sits there. This continues until no two adjacent seats are both empty. As N→∞N\to\infty, what fraction of the seats is expected to be left empty? Give a decimal to four places.

Show hints (2)+
  1. Give every adjacent pair an independent exponential arrival time; a pair that comes up when one of its seats is taken does nothing.
  2. For the end seat of a half-infinite bench, q′(t)=−e−tq(t)q'(t)=-e^{-t}q(t). An interior seat needs both of its sides to fail, independently.

Answer

Reveal answer →

0.1353 (± 0.001)

Create a free account to see the full worked solution and track your progress.

Interview format: Market Maker, Hedge Fund Quant

Related questions