1
$\begingroup$

Suppose there are $N$ seats and people come in one by one to take a seat randomly. They cannot take a seat that has been taken or is neighbor to a seat that has been taken. The process stops when there are no more valid seats available. What is the expected number of seats taken at the end?
My solution is kind of brute force - let $f(n)$ be the expected number of seats taken if there are $n$ seats to start with, then we have the recursion that when $n\geq4$ $$f(n)=\frac{2}{n}f(n-2)+\frac{1}{n}[(f(0)+f(n-3))+(f(1)+f(n-4))+...+(f(n-3)+f(0))]$$ since with $\frac{1}{n}$ probability the first person takes the first seat, which marks two seats unavailable, same situation if they take the last seat, otherwise they would mark three seats unavailable. Simplifying we get $$f(n)=f(n-2)+\frac{2}{n}f(n-3)+\frac{2}{n}$$ Still without a nice closed form expression. Is there a nicer way to solve this problem with a closed form expression?

$\endgroup$
4
  • $\begingroup$ Did you try getting a differential/integral equation for the generating function of $f(n)$ and solving it/feeding it into a CAS? $\endgroup$ Aug 8, 2020 at 19:46
  • $\begingroup$ Alternatively (just barely simpler) : $$f(n) = \frac{1+(n-1) f(n-1) +2 f(n-2)}{n}$$ $\endgroup$
    – leonbloy
    Aug 8, 2020 at 21:22
  • $\begingroup$ Are the seats arranged in a loop or is it a line? The answer for each changes. $\endgroup$
    – 24n8
    May 10, 2021 at 21:28
  • $\begingroup$ Seats are arranged in a line $\endgroup$ May 11, 2021 at 1:05

1 Answer 1

1
$\begingroup$

Please note the number of seats taken (say, $m$ out of $n$) can be between one third to half. You will have to apply the ceiling function to get the exact number.

$\lceil{\dfrac{n}{3}}\rceil \le m \le \lceil{\dfrac{n}{2}}\rceil$

Given how people come in and sit is random (within the rules), you should just look at the possible number of cases for m as per the above range I wrote. The expected number of seats taken is a mean of these cases.

For example, take $n = 11$, there are possibilities of $4$ seats taken, $5$ seats taken and $6$ seats taken. You get that using the above range.

$\endgroup$
1
  • 1
    $\begingroup$ I doubt that this will give a closed form $\endgroup$ Aug 8, 2020 at 19:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .