Consider a bar with N seats arranged in a line.

induction/fat-men-at-bar

Problem

Consider a bar with N seats arranged in a line.  A series of fat men 
enter the bar but each is too big for one seat, so he randomly picks a 
pair of adjacent unoccupied seats and sits on both.  This continues 
until there are no longer any adjacent pairs of unoccupied seats at 
which point we look at the fraction f of the N seats which are occupied. 


Question:  What is the expected value of f (i.e., averaged over the 
random choice each man makes on where to sit) as N becomes infinite?

Show solution

Let y(n) = expected number of EMPTY seats for row of n seats 
f = (n - y(n)) / n 


y(1) = 1 
y(2) = 0 
y(n) = 2 * SUM(i=1 to n-2) [y(i)] / (n-1) 


To see this recurrence, consider the first person to sit down. 
The expected total number of empty seats will the sum of the 
expected number of empty seats to his left and to his right -- 
i.e. the sum of two previous y() values. The first person can 
sit in any of (n-1) equiprobable locations.  Hence, y(n) is the 
sum of left and right portions over all n-1 locations divided 
by n-1. 


To solve this, we are going to have to get rid of the summation. 


By our formula, 
y(n-1) = 2 * SUM(i=1 to n-3) [y(i)] / (n-2) 
(I) (n-2)*y(n-1) = 2 * SUM(i=1 to n-3) [y(i)] 


We can also get this same summation from our formula for 
y(n) by moving the i=(n-2) term out of the summation. 


y(n) = 2 * {SUM(i=1 to n-3) [y(i)] + y(n-2)} / (n-1) 
(II) y(n) = {2 * SUM(i=1 to n-3) [y(i)] + 2*y(n-2)} / (n-1) 


Now substitute for the summation using (I), 


(*) y(n) = {(n-2)*y(n-1) + 2*y(n-2)} / (n-1) 


(n-1)*y(n) - (n-2)*y(n-1) - 2*y(n-2) = 0 


A note on terminology: 
This recurrence would be usually be called linear with nonconstant 
coefficents.  Linearity in difference equations usually refers 
to linearity in the y(n), so that given solutions y1(n) and y2(n), 
(a y1(n) + b y2(n)) is also a solution.) 

One way of handling recurrences of this type (having coefficients 
which are polynomial in n) is to deal with a generating function, 
which is the function Y(z) of the formal variable z which has 
Taylor coefficients y(n): i.e., 
  Y(z) = sum_{n=0}^\infty y(n) z^n 
(here we set y(0)=0 for convenience).  Now coefficients which are 
polynomials in n may be replaced by derivatives of the Y(z), 
giving a differential equation for Y (of order the maximal degree 
of the polynomials in n).  Here, for example (where D = d/dz) 
  0 = sum_{n=0}^\infty z^n[(n+1)*y(n+2) - n*y(n+1) - 2*y(n)] 
    = sum_n [(n+1)*z^n*y(n+2) - n*z^n*y(n+1) - 2*z^n*y(n)] 
    = sum_n [D[y(n+2)*z^{n+1}] - z*D[y(n+1)*z^n] - 2*z^n*y(n)] 
    = sum_n [D[(1/z)*y(n+2)*z^{n+2}] - z*D[(1/z)*y(n+1)*z^{n+1}] 
             - 2*z^n*y(n)] 
      (here I'm going to be cavalier about the summation limits; 
       if you check it, it actually does work out nicely) 
    = [D (1/z) - z D (1/z) - 2]*sum_n z^n*y(n) 
    = (1-z) D (Y(z)/z) - 2*Y(z) 
giving the first-order differential equation 
  Y'(z) / Y(z) = (2*z^2 - z + 1) / (z*(1-z)) 
for the generating function. 


This is mildly ugly but can be solved.  Then Taylor expansion 
gives the coefficients y(n).  In this case, y(n) can be computed 
exactly with a sum over n terms; the terms are well approximated, 
for large n, by y(n) ~ (n+2) exp(-2), for a filling factor (for 
large n) of 1 - exp(-2).