Skip to content

Queue for five-dollar tickets with no change

Question

Tickets cost $5. A queue of 2n2n people forms in random order: nn of them pay with a $5 bill and nn with a $10 bill. The box office opens with no cash. What is the probability that the cashier always has a $5 bill available whenever someone pays with a $10?

Short answer

1n+1\tfrac{1}{n+1}. Treat a $5 payer as a step up and a $10 payer as a step down; the walk must never go below zero. The number of such paths is the Catalan number 1n+1(2nn)\tfrac{1}{n+1}\binom{2n}{n}, out of (2nn)\binom{2n}{n} equally likely orderings.

Adapted from Zhou, A Practical Guide to Quantitative Finance Interviews, sec. 5.2 Martingale and Random Walk, 'Ticket line', p.116; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free