Interview problem: an unfriendly seating arrangement
The following problem description as well as the solution follows the paper by H. D. Friedman, et al. (1962).
Problem:
There are n seats in a row at a luncheonette and people sit down one at a time at random. They are unfriendly and so never sit next to one another (no moving over). What is the expected number of persons to sit down?
Solution:
Let the $E_n$ be the expected number of person to sit down when there are n consecutively seats. The first person randomly picks the ith seat, which gives the recursion: \begin{equation} E_n = 1 + \frac{1}{n}\sum_{i=1}^n \left(E_{i-2}+E_{n-i-1}\right)\,,\tag{1}\end{equation}with $E_{-1}=E_0=0$.
What I learned from the paper is to solve the above recursion by generating function. For this purpose, we define the generating function $F(x)\equiv \sum_{n=1}^{\infty} E_n \,x^n$, and rewrite the recursion as $n\,E_n = n + 2\sum_{i=1}^{n-2} E_i$. We have \begin{equation}F'(x) = \sum_{n=1}^{\infty} n\, E_n \,x^{n-1}= \sum_{n=1}^{\infty} n\,x^{n-1} + 2 \sum_{n=1}^{\infty} \sum_{i=1}^{n-2} E_i\,x^{n-1}\,.\end{equation} The first term on the right side is $\sum_{n=1}^{\infty} n\,x^{n-1}=\sum_{n=1}^{\infty}\frac{d}{dx}x^{n}=\frac{d}{dx}\sum_{n=1}^{\infty} x^n=\frac{d}{dx}\frac{1}{1-x}=\frac{1}{(1-x)^2}$. The second term on the right side can be computed as \begin{equation}\sum_{n=1}^{\infty} \sum_{i=1}^{n-2} E_i\,x^{n-1}= \sum_{i=1}^{\infty} \sum_{n=i+2}^{\infty}E_i\,x^{n-1}=\sum_{i=1}^{\infty} E_i x^i\sum_{n=i+2}^{\infty}\,x^{n-i-1}=xF(x)\sum_{j=0}^{\infty} x^{j}=\frac{x}{1-x}F(x)\,.
\end{equation} As a result, we obtain a differential equation on $F(x)$ as \begin{equation}F'(x)-2\frac{x}{1-x}F(x)=\frac{1}{(1-x)^2}\,,\tag{2}\end{equation} with initial condition $F(0)=0$.
To solve the differential equation (2), we first solve $F'(x)-2\frac{x}{1-x}F(x)=0$, which gives the solution $F(x)=C\frac{e^{-2x}}{(1-x)^2}$. Putting the ansatz $F(x)=C(x)\frac{e^{-2x}}{(1-x)^2}$ back to Eq.(2) gives an equation $C'(x)=e^{2x}$. With initial condition $C(0)=0$, we have $C(x)=\frac{1}{2}(e^{2x}-1)$. Therefore, we have the solution \begin{equation}F(x)=\frac{1-e^{-2x}}{2\,(1-x)^2}\,.\tag{3}\end{equation}
Finally, by Taylor expansion of (3) to the order of $x^n$, we have \begin{equation} E_n= \sum_{i=0}^{n-1}(n-i)\frac{(-2)^i}{(i+1)!}\,.\end{equation}
Problem:
There are n seats in a row at a luncheonette and people sit down one at a time at random. They are unfriendly and so never sit next to one another (no moving over). What is the expected number of persons to sit down?
Solution:
Let the $E_n$ be the expected number of person to sit down when there are n consecutively seats. The first person randomly picks the ith seat, which gives the recursion: \begin{equation} E_n = 1 + \frac{1}{n}\sum_{i=1}^n \left(E_{i-2}+E_{n-i-1}\right)\,,\tag{1}\end{equation}with $E_{-1}=E_0=0$.
What I learned from the paper is to solve the above recursion by generating function. For this purpose, we define the generating function $F(x)\equiv \sum_{n=1}^{\infty} E_n \,x^n$, and rewrite the recursion as $n\,E_n = n + 2\sum_{i=1}^{n-2} E_i$. We have \begin{equation}F'(x) = \sum_{n=1}^{\infty} n\, E_n \,x^{n-1}= \sum_{n=1}^{\infty} n\,x^{n-1} + 2 \sum_{n=1}^{\infty} \sum_{i=1}^{n-2} E_i\,x^{n-1}\,.\end{equation} The first term on the right side is $\sum_{n=1}^{\infty} n\,x^{n-1}=\sum_{n=1}^{\infty}\frac{d}{dx}x^{n}=\frac{d}{dx}\sum_{n=1}^{\infty} x^n=\frac{d}{dx}\frac{1}{1-x}=\frac{1}{(1-x)^2}$. The second term on the right side can be computed as \begin{equation}\sum_{n=1}^{\infty} \sum_{i=1}^{n-2} E_i\,x^{n-1}= \sum_{i=1}^{\infty} \sum_{n=i+2}^{\infty}E_i\,x^{n-1}=\sum_{i=1}^{\infty} E_i x^i\sum_{n=i+2}^{\infty}\,x^{n-i-1}=xF(x)\sum_{j=0}^{\infty} x^{j}=\frac{x}{1-x}F(x)\,.
\end{equation} As a result, we obtain a differential equation on $F(x)$ as \begin{equation}F'(x)-2\frac{x}{1-x}F(x)=\frac{1}{(1-x)^2}\,,\tag{2}\end{equation} with initial condition $F(0)=0$.
To solve the differential equation (2), we first solve $F'(x)-2\frac{x}{1-x}F(x)=0$, which gives the solution $F(x)=C\frac{e^{-2x}}{(1-x)^2}$. Putting the ansatz $F(x)=C(x)\frac{e^{-2x}}{(1-x)^2}$ back to Eq.(2) gives an equation $C'(x)=e^{2x}$. With initial condition $C(0)=0$, we have $C(x)=\frac{1}{2}(e^{2x}-1)$. Therefore, we have the solution \begin{equation}F(x)=\frac{1-e^{-2x}}{2\,(1-x)^2}\,.\tag{3}\end{equation}
Finally, by Taylor expansion of (3) to the order of $x^n$, we have \begin{equation} E_n= \sum_{i=0}^{n-1}(n-i)\frac{(-2)^i}{(i+1)!}\,.\end{equation}
Comments
Post a Comment