At the Box Office

Date: 03/08/99 at 08:42:06
From: Michael Jacks
Subject: Probability (a "random walk" problem)

I was wondering if you could give me some help on answering the 
following question. 

A queue of n + m people is waiting at a box office; n of them have 5-
pound notes and m have 10-pound notes. The tickets cost 5 pounds each. 
When the box office opens there is no money in the till. If each 
customer buys just one ticket, what is the probability that none of 
them will have to wait for change?

Date: 03/09/99 at 07:47:47
From: Doctor Anthony
Subject: Re: Probability (a "random walk" problem)

This problem can be modelled as a random walk.

We imagine walking in the direction of the positive x axis (x increases 
by 1 for each customer) with the y values increasing by 1 for each 'n' 
type customer and decreasing by 1 for each 'm' type customer. What we 
require in this random walk is that we stay above the x axis throughout 
all of the n + m steps. For this to be possible, we MUST have n > m 
because the destination point has coordinates (n + m, n - m) having 
started at (0, 0).

The number of possible paths is the number of ways of choosing n 
positive steps from a total of n + m steps. This is given by

   C(n + m, n).

We need now the number of such paths as are always above the x-axis.  

Clearly, there as many admissible paths from (0, 0) as there are paths 
from (1, 1) that do not touch or cross the x-axis. By the 'reflection 
principle', the latter are calculated using the fact that the total 
number of paths that do touch or cross the x-axis is the total number 
of paths from (1, -1) to (n + m, n - m)

  =  Total number of paths from (1, 1) - total number from (1, -1)

  =  C(n + m - 1, n - 1) - C(n + m - 1, n)

      (n + m - 1)!    (n + m - 1)! 
  =   ----------  -   ------------
      (n - 1)! m!      n! (m - 1)!

      n(n + m)!         m(n + m)!
     -----------   -   ------------ 
     (n + m)n! m!       (n + m)n! m!

      (n + m)!(n - m)      n - m     (n + m)!
  =    -------------   =   -----  x  -------
      (n + m)n! m!         n + m      n! m!

                          (n - m)
                       =   -----  x C(n + m, n)
                           n + m

and the probability that type 'n' is always ahead of type 'm' is

               (n - m)/(n + m) x C(n + m, n)
             = -----------------------------
                      C(n + m, n)

             = (n - m)/(n + m) 
                       
- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/