2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ You can set up a recurrence. Let $p(n)$ be the probability the red ball is in the first urn after $n$ swaps. We have $p(0)=1$. What is $p(n)$ in terms of $p(n-1)?$. As $n \to \infty$ the limit must be $\frac 38$. Why? $\endgroup$ – Ross Millikan Nov 11 '17 at 22:14
  • $\begingroup$ As a similar suggestion, I think a double recurrence may be simpler. Let $\psi_n$ be the probability you seek, and let $\phi_n$ be the probability that it is in the first urn after $n$ turns assuming it starts in the second urn. Then it is easy to write $\psi_n,\phi_n$ as linear combinations of $\psi_{n-1},\phi_{n-1}$ $\endgroup$ – lulu Nov 11 '17 at 22:30
  • $\begingroup$ Thank you so much! I decided to use the hint of Ross Millikan. Through the recurrence I found out, that p(n) has to be (7/15)^n * 5/8 + 3/8. That means, that the limit has to be 3/8. :) $\endgroup$ – RukiaKuchiki Nov 12 '17 at 2:57
0
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Thanks to you and Ross Millikan I was able to solve this problem. Thank you for your help! By the way: I think that p(1) = 2/3 and not 1/3. :) $\endgroup$ – RukiaKuchiki Nov 12 '17 at 3:01
  • $\begingroup$ Yes, perhaps it's best to think of $p(1)=1$ and $p(2)=\frac{2}{3}$. $\endgroup$ – Aritro Pathak Nov 12 '17 at 3:10
  • $\begingroup$ Sorry to disturb you again, but you mean p(0)=1 not p(1)=1, right? $\endgroup$ – RukiaKuchiki Nov 12 '17 at 3:16
  • $\begingroup$ Yes, sorry, you are right. Ross Millikan syas the same in his first comment on the question, above. $\endgroup$ – Aritro Pathak Nov 12 '17 at 3:17
0
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Such an interesting approach! I have to admit, that I don't understand every single step, but I will try again to understand your solution. Thank you so much for your time and your help. By the way: Thanks to Aritro Pathak and Ross Millikan I was able to solved this exercise with another solution. :) $\endgroup$ – RukiaKuchiki Nov 12 '17 at 3:11
  • $\begingroup$ They should arrive at the same answer in the end. This is a more general formalism of solving this kind of problems $\endgroup$ – Aleksejs Fomins Nov 12 '17 at 10:51
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I get it. Thank you for your reply. :) $\endgroup$ – RukiaKuchiki Nov 12 '17 at 3:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.