Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search