Randomly swapping two balls in two urns with 3 balls each. In total $3$ are black and 3 are white. Is this process a Markov chain?

Question

Three white and three black balls are distributed in two urns in such a way that each contains three balls. We say that the system is in state i, i = 0, 1, 2, 3, if the first urn contains i white balls. At each step, we draw one ball from each urn and place the ball drawn from the first urn into the second, and conversely with the ball from the second urn.

Let $X_n$ denote the state of the system after nth step. Now how to prove that $(X_n=0,1,2,...)$is a markov chain and how to calculate its transition probability matrix.

Solution:If at the initial stage both the urns have three balls each and we draw one ball from each urn and place them into urn different from the urn from which it is drawn. So after nth step state of the system will be 3 and it will remain it forever. So this is not a markov chain. I also want to understand the meaning of bold line.

If I am wrong, explain me why and how I am wrong and what is the transition matrix of this markov chain. Would any one answer this question?

Answer 1

Yes, this is a Markov chain

The state of the system is defined by the number of white balls in the first box.

There are four states:

The figure above depicts both boxes the left one being the one in which we count the white balls.

Based on the description of the experiment we can declare that this is a discrete time Markov chain. Obviously, if we are in a state it does not matter how we got there; the probability of the next state depends on the actual state.

Now, here are the state transition probabilities:

$$ p_{ij}: \begin{bmatrix} &\mathbf j&\mathbf0&\mathbf1&\mathbf2&\mathbf3\\ \mathbf i&\\ \mathbf0&&0&1&0&0\\ \mathbf1&&\frac19&\frac49&\frac49&0\\ \mathbf2&&0&\frac49&\frac49&\frac19\\ \mathbf3&&0&0&1&0 \end{bmatrix}.$$

$\mathbf i$ stands for the state the system actually is at, and $\mathbf j$ stands for the state the system is to jump to.

For example

$$p_{22}=\frac49$$

because we need to randomly select either of the white balls ($\frac23$) in the left box and the white ball in the right box ($\frac13$) or either of the black balls in the right box ($\frac23$) and the black ball in the left box ($\frac13$); the events are independent. The following figure shows the four equally likely pairs of choices resulting in $2\to 2$.

Note that the system does not remain in state $\mathbf3$ rather it jumps to state $\mathbf 2$ with probability one.

---

Let $[P_0 P_1 P_2 P_3]^T$ denote the stationary probabilities. These probabilities are the solutions of the following system of linear equations:

$$[P_0 \ P_1 \ P_2\ \ P_3] \begin{bmatrix} 0&1&0&0\\ \frac19&\frac49&\frac49&0\\ 0&\frac49&\frac49&\frac19\\ 0&0&1&0 \end{bmatrix}=[P_0\ P_1 \ P_2\ P_3]. $$

It is easy to check that

$$[P_0 \ P_1 \ P_2\ P_3]^T=\left[\frac1{20} \ \frac{9}{20}\ \frac{9}{20}\ \frac1{20}\right]^T.$$

Answer 2

Define $F_n$ to be the indicator random variable which has value 1 if at $n^{th}$ step white ball Chosen from the first ball and else 0.

Similarly Define Indicator random variable $S_n$ for second urn

Now,To check Markov property we need to check

P($X_n$= j|($X_{n-1}$,$X_{n-2}$,..$X_0$)=($i_{n-1}$,$i_{n-2}$,...$i_0$))=P($X_n$= j|$X_{n-1}$=$i_{n-1}$)

First Observe the conditional Range of $X_n$ given $X_{n-1}$,$X_{n-2}$...,$X_0$ is

$\space$ {$X_{n-1}-1$, $X_{n-1}$, $X_{n-1}+1$}

Hence enough to check for these cases below.

if j = $i_{n-1}+1$

Then rewrite this prob as P($F_n$=0,$S_n$=1|($X_{n-1}$,$X_{n-2}$,..$X_0$)=($i_{n-1}$,$i_{n-2}$,...$i_0$))

if j= $i_{n-1} -1$

Then rewrite this prob as P($F_n$=1,$S_n$=0|($X_{n-1}$,$X_{n-2}$,..$X_0$)=($i_{n-1}$,$i_{n-2}$,...$i_0$))

if j = $i_{n-1}$

Then rewrite this prob as

P($F_n$=1,$S_n$=1|($X_{n-1}$,$X_{n-2}$,..$X_0$)=($i_{n-1}$,$i_{n-2}$,...$i_0$))+ P($F_n$=0,$S_n$=0|($X_{n-1}$,$X_{n-2}$,..$X_0$)=($i_{n-1}$,$i_{n-2}$,...$i_0$))

Now,Observe that $F_n$ and $S_n$ only depends on $X_{n-1}$ and not on $X_{n-2}$,$X_{n-3}$,...$X_0$

So,from here you can conclude

P($X_n$= j|($X_{n-1}$,$X_{n-2}$,..$X_0$)=($i_{n-1}$,$i_{n-2}$,...$i_0$))= P($X_n$= j|$X_{n-1}$=$i_{n-1}$)

$\textbf{NOTE:}$ This is a long hand mathematical approach to argue markov property of $X_n$.If one wants to keep life simple one can argue in one line that the $n^th$ draw depends only on the $X_{n-1}$ by giving appropriate arguments.