# In a queue for £1 tickets, there are $m$ people with a £1 coin and $n$ people with a £2 coin. What is the probability that everyone receives change?

I am selling raffle tickets for £1 per ticket. In the queue for tickets, there are $$m$$ people each with a single £1 coin and $$n$$ people each with a single £2 coin. Each person in the queue wants to buy a single raffle ticket and each arrangement of people in the queue is equally likely to occur. Initially, I have no coins and a large supply of tickets. I stop selling tickets if I cannot give the required change.

Show that the probability that I am able to serve everyone in the queue is $$\frac{m+1-n}{m+1}$$

This problem comes from a STEP question (see Q3 here) where the solution is shown in the cases $$n=1,2$$ or $$3$$. However they involve conditioning on permutations of the first couple of people in a way that I don't see how to generalise.

• Do you know "reflection" method in 1-D drunken walk? I think it can be used to solve this generally - I haven't tried but it should work Jul 20, 2020 at 13:01
• @aman_cc I see. We're interested in the number of walks (up and right only) from $(0,0)$ to $(m,n)$ that don't touch the line $y=x+1$. By reflection, the number of lines that touch $y=x+1$ is the same as the number of lines from $(-1,1)$ to $(m,n)$. Thanks Jul 20, 2020 at 13:12
• yes I just worked it out and I way typing the answer - it works. I'm gonna be lazy and not type it now :) cheers Jul 20, 2020 at 13:14
• There are similar questions on MSE from before addressing the same "Reflection" method. Here is one example - math.stackexchange.com/questions/990747/… Jul 20, 2020 at 15:46

This problem is equivalent to Bertrand's ballot theorem and this answer follows the argument found on Wikipedia. Thanks to aman_cc for pointing out this solution.

This problem can be visualised as counting the number of paths from $$(0,0)$$ to $$(m,n)$$ where:

• a step right represents a person with a £1 coin
• a step up represents a person with a £2 coin

All the tickets are sold if and only if the number of £1 coin customers is greater than the number of £2 coin customers - i.e the path does not intersect the line $$y=x+1$$.

To count the number of paths that intersect the line $$y=x+1$$, the following correspondence is helpful. If a path intersects the line $$y=x$$, then reflect the path up to the first point of intersection. This creates a new path from $$(-1,1)$$ to $$(m,n)$$. In the picture below the blue path is 'reflected' into the red path.

Thus the probability of failure is:

$$\frac{ \text{ \# {paths from (-1,1) to (m,n) } } }{ \text{ \# {paths from (0,0) to (m,n) } } } = \frac {\binom{m+n}{n-1} }{ \binom{m+n}{n} } =\frac{n}{m+1}$$

Hence the probability of success is $$\frac{m+1-n}{m+1}$$