There are two urns, with the first one containing three white balls and the second one containing three black balls. At each step, we draw a ball from each urn, and then put the ball drawn from the first urn into the second and the ball drawn from the second urn into the first. Model this operation by a Markov chain. Let state i be “there are i white balls in the first urn”, i { 0, 1, 2, 3 } The state space is {0, 1, 2, 3}, the initial distribution is [0 0 0 1], and the transition probability matrix is

enter image description here

(a) Find all the classes of your Markov chain. Is there any closed class? Is there any recurrent state? State your reasons briefly.

(b) What is the probability that the first urn will contain 3 white balls again?

(c) Let Xn be the number of white balls in the first urn just after the n-th step, n = 1, 2, ….

enter image description here

(d) Determine the limiting distribution.

(e) Now suppose we will, after the first step, stop drawing balls once all white balls are in an urn. Find the probability that the first urn contains only white balls.

My attempt :

a) class = {0,1,2,3}

No closed class as there is only one class and all states communicate. All states are recurrent state as this Markov Chain is irreducible.

b) probability is 1 as state 3 is recurrent.

c) This is what I've got so far

enter image description here


A preliminary remark is that your suggestion for (c) contains an interesting mistake, which is regularly made about Markov chains. You write that $$ (\ast)=P[X_3=1,X_2\ne3,X_1\ne3\mid X_0=2] $$ is (probably due to the Markov property) also $$ (\ast)=P[X_1\ne3\mid X_0=2]\cdot P[X_2\ne3\mid X_1\ne3]\cdot P[X_3=1\mid X_2\ne3]. $$

This is NOT what the Markov property says.

Recall that, in full generality, Bayes formula says that $(\ast)=(\ast)_3(\ast)_2(\ast)_1$ with $$ (\ast)_3=P[X_3=1\mid X_2\ne3,X_1\ne3,X_0=2], $$ and $$ (\ast)_2=P[X_2\ne3\mid X_1\ne3,X_0=2],\quad (\ast)_1=P[X_1\ne3\mid X_0=2]. $$ Apparently you replace $(\ast)_2$ in this, by $(\circ)_2$ (and likewise for $(\ast)_3$), with $$ (\circ)_2=P[X_2\ne3\mid X_1\ne3]. $$ It is important to realize that:

In general, $(\ast)_2\ne(\circ)_2.$

Note that the suggested identity is odd at the onset since the distribution of $X_1$ is not determined by $(\circ)_2$ but it is fully determined in $(\ast)_2$ hence $(\circ)_2$ and $(\ast)_2$ are not simultaneously well defined.

What the Markov property does say, however, is for example that, to stay in a setting close to $(\ast)_2$, for every event depending only on $(X_k)_{k\leqslant n-1}$, every state $x$ and every set of states $B$, $$ P[X_{n+1}\in B\mid X_n=x,A]=P[X_{n+1}\in B\mid X_n=x]. $$ Note that the part of the conditioning which involves $X_n$ is $[X_n=x]$ for a single state $x$, not $[X_n\in C]$ for any subset $C$.

How to compute $(\ast)$ then? A simple approach is to enumerate the paths corresponding to this event. Assume that $X_0=2$. Then the relevant paths with positive probability from time $0$ to time $3$ are $2(?)(?)1$, that is, $2(1\lor2)(0\lor1\lor2)1$, that is, $$ 2101,\ 2111,\ 2121,\ 2211,\ 2221. $$ The probability of each of these 5 paths is the product of 3 transition probabilities. Write them down, sum up, and you get the value of $(\ast)$.

Questions (d) and (e) are not related to question (c) and can be solved applying standard techniques (hence you should describe the problem you have solving them, if any).


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.