4
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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 $\endgroup$
    – aman_cc
    Jul 20, 2020 at 13:01
  • 2
    $\begingroup$ @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 $\endgroup$
    – Bysshed
    Jul 20, 2020 at 13:12
  • $\begingroup$ 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 $\endgroup$
    – aman_cc
    Jul 20, 2020 at 13:14
  • $\begingroup$ There are similar questions on MSE from before addressing the same "Reflection" method. Here is one example - math.stackexchange.com/questions/990747/… $\endgroup$
    – Math Lover
    Jul 20, 2020 at 15:46

1 Answer 1

0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .