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 reach $(2n,0)$ after $2n$ steps. For these $2n$ steps, we need to choose $n$ steps as +1, so there are ${2n \choose n} = 2n!/(n!*n!)$ possible paths. We are interested in the paths that have the property $b \geq 0$, for all $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)