You are outside a well known restaurant, waiting in queue, with 18 couples in front of you. You know there are forty tables inside, and you think an average meal will take one hour.

How long will you have to wait, on average?

PS. This problem comes from queueing theory, but you don't have to know anything about it to find the answer!

Make the following assumption:

Each meal takes exactly one hour.
Each table arrived uniformly right before you started in the line.

Let T[1], ..., T[40] be the time for the i'th table to leave.  Then T[1], ..., T[40] is a sequence of iid uniform random variables U[0, 1].  Let T(i) be the order statistic in which T(1) denote the earliest time and T(40) denote the latest time.  The problem is to find the expected value for T(19), which coincide with the time for you to wait.  Note that P(T[i]<t) = t, P(T[i]>t)=1-t.

Let f[k](t) be the pdf for T(k).  Then

f[k](t)dt = P(T(k)Î[t+dt])
=£UP(T[i]<t)*...*P(T[j]Î[t+dt])*P(T[m]>t)*..., for appropriate values of i, j, and m.  For instance, if k=1, then there are 40 possible values of j, no values of i, and possible values of m is already determined by i and j.  So f[1](t)dt = 40*(1-t)^39.  Then expected value is ¡ì 40*t*(1-t)^39dt, t=0..1, which evaluates to 1/41.

For general k, there are 40 values of j, 39 choose (k-1) (39C(k-1)) values of i.  Thus

f[k](t)dt = 40*39C(k-1)*dt*t^(k-1)*(1-t)^(40-k)

Thus E(T(k)) = ¡ì40*39C(k-1)*t^k*(1-t)^(40-k) dt
= k/41

Then E(T[19]) = 19/41 = 0.463 hr ~ 27.8min.

Note that this calculation "corrects" the slightly wrong answer below that the expected value was estimated by k/40 instead.

 

Edited on August 9, 2004, 9:48 pm

Posted by Bon on 2004-08-09 21:38:57