Queue for five-dollar tickets with no change
Question
Tickets cost $5. A queue of people forms in random order: of them pay with a $5 bill and 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
. 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 , out of 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 solutionLessons behind this question
- The Reflection Principle and the Ballot Problem
- Gambler's Ruin and First Passage Times
- Simple Random Walks — Symmetric and Asymmetric
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