- Joined
- 11/16/19
- Messages
- 2
- Points
- 13
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)
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)
