A tricky conditional probability question involving recursion

Question

I've been trying to answer this question for the past few days, and I'm absolutely stuck. Without further ado, here's the mystery:

We are given a pair of boxes. There are n red balls in box number 1, and n blue balls in box number 2. Every turn, a ball is randomly taken out of the first box, and not returned. After the ball is taken out, a blue ball from the second box is inserted into the first one. This continues until there are no more blue balls to be transferred from box 2 to box 1. That means that there are n+1 turns in which a ball is randomly taken out of box 1.

I am asked to find the probability that the last ball taken out of box 1 (which means in the (n+1)-th turn) is red. Here's what I've got so far:

Event A - the ball taken out of box 1 in the last turn is red.

Event B(i) - i red balls were left in box 1 after n turns.

I'm trying to find P(A). Bayes wasn't helpful, and the law of total probability was not useful as well, since I can't seem to know what P(B(i)) is for any given i (other than, of course, i=0 and i=n-1). I did find a two-dimensional recursive function for P(B(i)), but that doesn't seem to be the right solution.

Any thoughts about how to properly approach (and hopefully solve) this question would be highly appreciated.

Answer 1

Consider a particular red ball. What is the probability that this one will be the last ball chosen? Well, to achieve that it must be passed over the first $n$ times and be selected on the $(n+1)^{st}$ trial. Thus the probability that it will be the last is $$\left(\frac {n-1}{n}\right)^n \frac 1n$$

As there are $n$ of them the probability that one of them will be last is $n$ times this, or$$\left(\frac {n-1}{n}\right)^n$$

Answer 2

Let the proportion of red balls after $k$ transfers be $P_k$. Then $P_0=1$ and for $0\le k<n$

$$E(P_{k+1})=E(P_k(P_k-\frac 1 n)+(1-P_k)P_k)=\frac{n-1}n E(P_k)$$ Hence $$E(P_n)=(\frac {n-1}n)^n\to e^{-1}$$ is the probability you seek.