Ticket-Line Probability via the Reflection Principle

# some doubts about answers to ticket line question from interview book


# 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)

## Answer by Cettt (score 5, accepted)

https://quant.stackexchange.com/a/49779

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}. $$