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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum