Nneetquant
Get started

Making change in line

HardCombinatoricsStochastic Processes~8m

2n2n people queue for $5 tickets: nn carry only a $5 bill and nn carry only a $10 bill, in a uniformly random order. The seller starts with no change and can only give a $10-payer their $5 change from $5 bills collected earlier. What is the probability the seller can serve everyone without ever running short of change? Work it out for n=3n = 3. (to 3 decimals)

Show hints (2)+
  1. Encode $5-payer as +1+1, $10-payer as −1-1; every prefix sum must stay ≥0\ge 0 (a Dyck path).
  2. Valid count is the Catalan number CnC_n; divide by (2nn)\binom{2n}{n} to get 1/(n+1)1/(n+1), then set n=3n=3.

Answer

Reveal answer →

0.25 (± 0.001)

Create a free account to see the full worked solution and track your progress.

Create a free account

Interview format: Market Maker, Systematic & Data-Driven Trading

Related questions