0
$\begingroup$

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 screenshotScreenshot, 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)

$\endgroup$
1
  • 3
    $\begingroup$ Please use proper formatting to make your question more readable. As of now I find it very hard to follow $\endgroup$
    – Cettt
    Nov 18, 2019 at 14:54

1 Answer 1

4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.