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