Two urns. What is the probability that the red ball is in the first urn after $n$ draws?

Question

I'm trying to solve this problem:

You have two urns. The first urn contains a red ball and two white balls. The second urn contains five white balls. We draw one ball from each urn and exchange them. What is the probability that the red ball is in the first urn after $n$ times?

I think that I have to use the law of total probability. But I don't know how.

Thanks for any help you can provide.

Answer 1

Following the hint of Ross Millikan in the comment, $p(n)=p(n-1).\frac{2}{3}+ (1-p(n-1)).\frac{1}{5}$, and so $p(n)=\frac{7}{15}p(n-1)+\frac{1}{5}$, with $p(1)=\frac{1}{3}$.

Answer 2

This is a classical example of a Markov chain, a system evolving in time in discrete steps, each step depending only on the current value and not the previous values (ergodicity)

We will solve the problem as follows

Let $p_r^i$, $p_w^i$, $q_r^i$, $q_w^i$ be the expected quantities of red balls in first urn, white balls in first urn, red balls in second urn and white balls in second urn respectively. These may be fractional, as they are the product of quantity times probability. Let $i$ identify the time step. Given our initial conditions, at time step $i=0$

$p^0_r = 1$

$p^0_w = 2$

$q^0_r = 0$

$q^0_r = 5$

Now let us define a 4D vector, that glue together all these 4 quantities

$\vec{z}_i = \{p^i_r, q^i_r, p^i_w, q^i_w\}$

Note that I changed their order slightly for reasons that will become obvious later. What we will be trying to prove is that the vector $\vec{z}$ evolves linearly following the equation

$\vec{z}_{i+1} = M \vec{z}_{i}$

where $M$ is a fixed matrix. Once we have found this matrix, the problem can be solved by multiplying the initial vector by that matrix $n$ times

$\vec{z}_{n} = M^n \vec{z}_{0}$

and the final probability of the red ball being in the first urn being simply $p^n_r$

But let us now return to the definition of the matrix. Firstly, let us note that the total number of balls in each urn does not change

$n_p = p^i_r + p^i_w = 3$

$n_q = q^i_r + q^i_w = 5$

Let us consider the number of red balls in the first urn. It will decrease by 1 if a red ball is picked from this urn, and increased by 1 if a red ball is picked from another urn. We can write this as following

$p^{i+1}_r = p^{i}_r - \frac{1}{n_p} p^{i}_r + \frac{1}{n_q} q^i_r$

The third term is 1 times the probability of picking a red ball from the first urn, and the 4th term is 1 times the probability of picking a red ball from the second urn. By analogy

$p^{i+1}_r = p^{i}_r - \frac{1}{n_p} p^{i}_r + \frac{1}{n_q} q^i_r$

$p^{i+1}_w = p^{i}_w - \frac{1}{n_p} p^{i}_w + \frac{1}{n_q} q^i_w$

$q^{i+1}_r = q^{i}_r - \frac{1}{n_p} q^{i}_r + \frac{1}{n_q} p^i_r$

$q^{i+1}_w = q^{i}_w - \frac{1}{n_p} q^{i}_w + \frac{1}{n_q} p^i_w$

By reading off coefficients, we can now deduce the form of the matrix M

$M = \begin{bmatrix} 1 - 1/n_p & 1/n_q & 0 & 0 \\ 1/n_p & 1 - 1/n_q & 0 & 0 \\ 0 & 0 & 1 - 1/n_p & 1/n_q \\ 0 & 0 & 1/n_p & 1 - 1/n_q \\ \end{bmatrix}$

As can be seen from the matrix, there is no coupling between red and white balls in terms of expected value evolution (off-diagonal blocks are zero), so the problem can be reduced to only considering red balls. Let us define a smaller 2D vector

$\vec{w}_i = \{p^i_r, q^i_r\}$

Then

$\vec{w}_{i+1} = N \vec{w}_{i}$

and

$N = \begin{bmatrix} 1 - 1/n_p & 1/n_q \\ 1/n_p & 1 - 1/n_q \\ \end{bmatrix}$

Please tell me if you can figure it out from here. I can explain how one can accelerate the calculation of evolution by eigendecomposition of matrix N

Answer 3

You can go back to basics.

To have the red ball in the first urn after five exchanges, that ball must have been swapped 0, 2, or 4 times.

The probability for swapping if the ball is in the first urn is $1/3$.

The probability for swapping back if the ball is in the second urn is $1/5$.

---

The probability for swapping zero times is: $(2/3)^5$.

Since the ways to do this are $\small\sf NNNNN$, where $\small\sf N$ is the event of not swapping from urn 1, $\small\sf S$ the event of swapping from urn 1, $\small\sf M$ the event of not swapping back from urn 2, and $\small\sf B$ the event of swapping back from urn 2.

---

The ways to swap two times are : $\sf\small NNNSB, NNSBN, NSBNN, SBNNN;\\\small NNSMB, NSMBN, SMBNN;\\\small NSMMB, SMMBN;\\\small SMMMB$

---

The ways to swap four times are: $\sf\small NSBSB, SBNSB, SBSBN;\\\small SMBSB, SBSMB$

---

Evaluate the probabilities and put it all together.