Expected Seated Count with No-Adjacent Rule

HardProbability

Reported in interviews at eBay Squarepoint Capital Two Sigma

Problem statement

There are $n$ seats in a row, numbered $1$ through $n$. People arrive one by one in random order. Each arriving person looks at all currently free seats that are not adjacent to any occupied seat and picks one uniformly at random. If no such seat exists, the person leaves without sitting.

Let $N_n$ denote the total number of people seated at the end of the process.

  1. Derive a recursion for $E[N_n]$.
  2. Obtain an exact or asymptotic formula for $E[N_n]$ as $n \to \infty$.
Show hint

What happens to the rest of the row once the very first person sits, and do the pieces left over look like smaller copies of the original problem?

Relevant roles: Data Scientist, Applied Scientist and Research Scientist.

Related free problems