• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

some doubts about answers to ticket line question from interview book

I'm reading an interview book called A Practical Guide to Quantitative Finance Interviews (nickname: Greenbook) and cannot understand the answer to the following question:
Question: From Chapter 5/5.2
Ticket Line:
At a theater ticket office, 2n people are waiting to buy tickets, n of them have only 5 dollar bills and the other n people have only 10 dollar bills. The ticket seller has no change to start with. If each person buys one $5 ticket, what is the probability that all people will be able to buy their tickets without having to change positions?
I have some doubts (highlighted in bold below) about the answer and really appreciate your advice.
Here is the answer from the book:
Assign +1 to the n people with 5 dollar bills, and assign -1 to the n people with 10 dollar bills. Consider the process as a walk. Let (a,b) represent that after a steps, the walk ends at b. So we start at (0,0) and reaches (2n,0) after 2n steps. For these 2n steps, we need to choose n steps as +1, so there are 2n Cr n = 2n!/(n!*n!) possible paths. We are interested in the paths that have the property "b>=0, ∀a<2n and a>0". It's easier to calculate the number of complement paths that reach b=-1, ∃a<2n and a>0. As shown in the attached screenshot

, if we reflect the path across the line y = -1 after a path first reaches -1,
Doubt: how come we can assume a path reaches -1 because I think we're interested in b>=0 and we never reaches b below 0
for every path that reaches (2n,0) at step 2n, we have one corresponding reflected path that reaches (2n,-2) at step 2n. For a path to reach (2n,-2),there are (n-1) steps of +1 and (n+1) steps of -1. So there are [2n Cr (n-1)] = 2n!/((n-1)!*(n+1)!) such paths. The number of paths that have the property b = -1, ∃ a<2n and a>0, given that the paths reaches (2n,0) is also [2n Cr (n-1)]
Doubt: why the number of paths that have the property b = -1 is [2n Cr (n-1)] ?
And the number of paths that have the property b>=0, ∀ a<2n and a>0 is: [2n Cr n]-[2n Cr (n-1)] = (1/(n+1))*[2n Cr n]. Hence, the probability that all people will be able to buy their tickets without having to change positions is 1/(n+1)
 

Attachments

  • IMG_4725.JPG
    IMG_4725.JPG
    1.4 MB · Views: 29
Top