# 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 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) • Please use proper formatting to make your question more readable. As of now I find it very hard to follow – Cettt Nov 18 '19 at 14:54 ## 1 Answer The way I understand this approach: • you start at $$A = (0, 0)$$. • Every time a 5\$ person wants to buy a ticket you move one unit to the right and unit up.
• Every time a 10\$person wants to buy a ticket you move one unit to the right and unit down. • This way, after all $$2n$$ person were served you get a path starting from $$A$$ and ending at some point $$B = (2n, 0)$$. • The number of all possible paths is simple to determine: $$N_\text{total} = {2n \choose n} = \frac{(2n)!}{n! \cdot n!}.$$ • We are only interested in valid paths: these are paths were all customers can buy a ticket. A path is valid if it never touches or crosses the horizontal line $$y = -1$$. Why is that? Because a 10\$ person can only be served if there was a 5\$in line before them. For example, assume that the first person in line is a 5\$ person and the second one in line is a 10\$person. Then the beginning of the corresponding path looks like this: $$(0,0) \rightarrow (1,1) \rightarrow (2, 0).$$ • The reflection principle can now be used the count the number of invalid paths. Let's remember that all paths (valid and invalid) start at $$A = (0, 0)$$ and end at $$B = (2n, 0)$$. Now lets consider an invalid path. Because this path is invalid, there exists one point (say point $$C$$) on this path where it touches the line $$y = -1$$ (otherwise it would be a valid line). So we have $$C = (x, -1)$$ where $$x > 0$$ and $$x < 2n$$. • Now we construct the reflected path (as in the graphic): the reflected path is the same as the original path between $$A$$ and $$C$$ and is reflected at $$y = -1$$ between $$C$$ and $$B$$. Since the original path ends at $$B$$ the new path ends at $$\widetilde{B} = (2n, -2)$$. To sum up: the reflected path goes from $$A$$ to $$\widetilde{B}$$. • Note that each invalid path corresponds bijectively to one reflected path. Therefore the number of invalid paths is the same as the number of the reflected invalid paths. • The invalid paths all start at $$A = (0, 0)$$ and end at $$\widetilde{B} = (2n, -2)$$. This corresponds to a similar problem as our initial problem with $$n-1$$ 5\$ people and $$n+1$$ 10\\$ people. Therefore the number of invalid paths is equal to $$N_\text{invalid} = {2n \choose n+1} = \frac{(2n)!}{(n+1)! \cdot (n-1)!}.$$

• Therefore the number of valid paths is $$N_\text{valid} =N_\text{total} - N_\text{invalid}$$.

• Finally the probability of a valid path is $$p = \frac{N_\text{valid}}{N_\text{total}} = 1 - \frac{n! \cdot n!}{(n+1)! \cdot (n-1)!} = 1 - \frac{n}{n+1} = \frac{1}{n+1}.$$

• Thanks a lot @Cettt, your explanation is extremely clear for me!! Really appreciate it! You saved me before my interview:) – M00000001 Nov 21 '19 at 16:46