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

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.

• I don't understand the question – Zubin Mukerjee Mar 13 at 20:25
• What is PLN 10? Has it to do with Zlotys? Then it should be PLZ 10 perhaps...What is $A'$. And why is no one waiting for the rest of the people? – Dietrich Burde Mar 13 at 20:28
• The question still makes no sense even if zloty ambiguities are resolved – Zubin Mukerjee Mar 13 at 20:39
• @JaroslawMatlak Thank you, this is interesting! – Dietrich Burde Mar 13 at 20:40
• @ZubinMukerjee, hopefully my edit makes it clear – MoonKnight Mar 13 at 21:08

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.

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

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

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