Probability no one needs to wait for changes when buying tickets .

Question

There are $2 \cdot n$ people in the queue to the theater office; n people on only banknotes worth $20$ zlotys, and the remaining n people only have banknotes worth $10$ zlotys . At the beginning of the sale at the box office there is no money. Each person buys one ticket worth 10 zlotys.

If one with only $20$-zlotys banknotes is in the first of the queue, then he/she needs to wait for another guy with only 10-zlotys banknote to complete his/her transaction, because the ticket office does not have any change to offer at that time.

What is the probability that no one will wait for the change?

$A$ = no one will wait for the rest. $P (A) = 1-P (A ')$, that is, it subtracts the waiting persons from the whole and will leave me without waiting, but I do not know how to calculate it.

Answer 1

Not a full answer but a hint and not so elegant. The elegant approach would count random walks with increments $(1,\pm 1)/\sqrt{2}$ staying at or above a line of slope $-1/2.$

You are asking for the number $K_n$ of $$x=(x_1, \ldots, x_{2n})\in \{2,-1\}^{2n}$$ divided by $$\binom{2n}{n}$$ to make it a probability, with exactly $n$ $x_i$ equal to $2$ such that the partial sums $$ S(x,t)=\sum_{k=1}^t x_t,\quad t=1,\ldots,2n, $$ are all nonnegative. A recursive approach starting with $n=1,$ obviously works but there may be a nice closed form.

I won't do the division. When $n=1,$ $(2,-1)$ is fine but $(-1,2)$ is not so $K_1=1.$

As far as the recursion if a $2n$ pattern fails all its extensions fail. Since the non failing pattern for $n=1,$ has sum $1$ both of its extensions will pass, thus $K_2=2,$ with sums $0$ or $3$. The next step is similar and note that if a sum is $1$ or more it is safe for the next iteration, it cant go negative.

Answer 2

The number of ten-zloty notes in the cash box goes up by one when a customer with a ten-zloty note comes to the window, and it goes down by one when a customer with a twenty-zloty note comes to the window, so this is a question about Catalan numbers and Dyck paths. If you Google either of those terms, you'll get lots of hits, and you'll see how to solve the problem.

If I recall the formula correctly for the catalan numbers correctly,, the answer is $${1\over n+1}$$

Answer 3

Define $P(a,b)$ as the probability of reaching the end with no one waiting when there are still $a$ people with 10-zlotyes and $b$ people with 20-zlotyes left. So the answer to your problem is $P(n,n)$ in this notation.

Obviously we have

• $P(a,0) = 1$
• $P(a,b) = 0 \quad(\text{when } a<b)$

And the recurrence relation $$ P(a,b) = \frac{a}{a+b}P(a-1, b) + \frac{b}{a+b}P(a, b-1) $$

You can manually calculate a few layers $P(a,1)$, $P(a,2)$ etc. It won't be long before you start to find there is an simple expression for it $$ P(a,b) = 1 - \frac{b}{a+1} \quad (\text{when } a\geq b) $$

Now let me prove this is the correct expression.

1. Obviously it is true for $b=0$.
2. Even though we are only interested in the cases when $a\geq b$, but it can be easily verified that the expression above also holds for $b=a+1$ ($P(a,a+1)=0$). So when we are calculating $P(a,a)$, we can still use the expression above to represent $P(a-1,a)$.
3. Now the main step $$ P(a,b) = \frac{a\frac{a-b}{a-1+1} + b \frac{a+2-b}{a+1}}{a+b} = 1 + \frac{-2b(a+1) + b(a+2-b)}{(a+1)(a+b)} = 1 - \frac{b}{a+1} $$

Now, it is easy to see from this general expression that $$ P(n,n) = \frac{1}{n+1} $$