# Bags, probability and recurrence

I need help on this one:

There are two bags, each of them contain $n$ balls.
The first bag contains only white balls. The second bag contains only black balls.
Pick one black ball and input it to first bag. Then choose one ball from first bag randomly and and throw out it. Repeat this process while second bag is not empty.

Question:

What is probability that last selected ball from first bag is white?

I guess there are some recurrence formula for this probability...

• Would you edit your question so that it makes some sense ? "...ball contains only white balls...", "...try to get one black ball..." Nov 28, 2017 at 12:43
• Could this be rephrased as: You have a bag of $n$ white balls. You now do the following steps $n$ times: Add a black ball; remove a ball at random. What is the probability that the last removed ball (i.e., on the $n$th iteration) is white? Nov 28, 2017 at 13:12
• @paw88789, Yes, you are Nov 28, 2017 at 13:46

The problem can be imagined to be a successive dilution problem, say $99L$ of white paint being successively diluted by $1L$ of black paint added, and $1L$ of the mixture discarded at a time.

After the first infusion, $99\%$ or $0.99$ (call this the fraction $f$) of the mixture will be white paint,
and after each iteration, $0.99$ of what was remaining before this iteration will be white paint.

Thus the fraction remaining after one, two, three,.... iterations will be $f$,$f^2,f^3...$

Coming to the instant problem, the only difference is that the infusion-discard is in discrete steps, and what we count after $n$ iterations is the expected fraction of white balls remaining.

Thus P(last ball drawn is white) = $\left(\dfrac{n}{n+1}\right)^n$

I have given a solution that deduces from reasoning at the first few rounds and extending it to the last round.

Let $W_k$ be be the number of white balls in the first bag after the $k$-th iteration, with $W_0 =n$, and let $X_k$ be the indicator that a white ball is chosen in the $k$-th iteration. Then $$W_k = W_{k-1} - X_k \Rightarrow W_k = n - X_1 -X_2 -\cdots - X_k$$ and $$\mathbb{E}[X_k|W_{k-1}] = \frac{W_{k-1}}{n+1} \Rightarrow \mathbb{E}[X_k|X_{1},X_{2},\cdots,X_{k-1}] = \frac{ n - X_1 -X_2 -\cdots - X_{k-1} }{n+1}$$ Taking expected value of both sides and denoting $p_i \equiv \mathbb{E}[X_i]$, we have $$p_k = \frac{ n - p_1 -p_2 -\cdots - p_{k-1} }{n+1} = \frac{n}{n+1}p_{k-1}$$ This can be telescoped to get $$p_k = \left(\frac{n}{n+1}\right)^k, \quad \forall k \in \mathbb{N}$$ and in particular, $p_n = \left( \dfrac{n}{n+1}\right)^n$.