4

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.

Bysshed
  • 1,864
  • 2
    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 – aman_cc Jul 20 '20 at 13:01
  • 2
    @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 – Bysshed Jul 20 '20 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 – aman_cc Jul 20 '20 at 13:14
  • There are similar questions on MSE from before addressing the same "Reflection" method. Here is one example - https://math.stackexchange.com/questions/990747/cashier-has-no-change-catalan-numbers-probability-question – Math Lover Jul 20 '20 at 15:46

1 Answers1

0

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.

A blue path and its reflected red bath

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} $$

Bysshed
  • 1,864