Three fair coins are tossed, and we let $X_1$, denote the number of
heads that appear. Those coins that were heads on the first trial (there were
$X_1$, of them) we pick up and toss again, and now we let $X_2$, be the total number of tails, including those left from the first toss. We toss again all coins
showing tails, and let $X_3$ be the resulting total number of heads, including
those left from the previous toss. We continue the process. The pattern is,
Count heads, toss heads, count tails, toss tails, count heads, toss heads,
etc., and $X_0 = 3$. Then $\{X_n\}$ is a Markov chain. What is the transition probability matrix?
I have read the answer from
Transition Probability Matrix of Tossing Three coins
But I don't know yet why the states are 8, and how to construct the transition probability matrix. Can anyone help me?
Best Answer
Your first thought here would have been that if $X_n$ is to be shown as a Markov chain, the $X_n$ depends on $X_{n-1}$ only, so we have four states since $X_{j}$ can be any one of $\{0,1,2,3\}$. However, the problem here is that we don't quite have this situation : $X_n$ does not depend only on $X_{n-1}$, but also on $\mathit n$, since if $n$ is odd we are taking $X_n$ as the number of heads, and otherwise as the number of tails.
Therefore, $X_n$ depends only on $X_{n-1}$, but the manner of dependence (i.e. the probabilities $P(X_n = j | X_{n-1} = i)$ for $i,j \in \{0,1,2,3\}$) is non-homogenous, since it depends on whether $n$ is odd or even, right?
We want our Markov chain to be homogenous (i.e. the transition matrix needs to be $n$-independent, which we saw is not the case), which is why we need to add further states. Further, we know what needs to happen : if we just specify whether or not $X_n$ is to count heads or tails, then we know the distribution of $X_n$ given $X_{n-1}$. Since this information is not evident from $X_{n-1}$ itself, we need to create states which reflect whether $n$ is odd or even, so that then , while finding $X_n$, $X_{n-1}$ will also contain the information about whether $n$ is odd or even, based on which we can find $X_n$ after the $n$th round of tossing.
Therefore, the idea is to create states so that each state should contain information about two things :
The number of heads/tails that was obtained in the current round of tossing coins.
Whether we are to count heads or tails in the next round.
The first has four possibilities, $0,1,2,3$. The second is just "count heads next round" or "count tails next round". This gives rise to $8$ states.
Here are examples of states :
($3$, "count heads next round")
($1$, "count tails next round")
($2$, "count heads next round")
Now, for the transition matrix. Unfortunately, there are plenty of possible transitions. Let me take you through a few examples, so that you can work out the rest on your own.
Compute the transition from ($0$,"Count tails next round") to ($3$, "count tails next round") : I claim this is zero. Why? Note that I am counting tails and heads alternately, so if I count tails in one round, in the next round I have to count the heads. Therefore, from here, you conclude that this transition probability is zero, since you cannot be counting tails in consecutive rounds.
The transition from ($2$, "Count heads next round") to ($1$, "Count heads next round") is also zero for similar reasons to above.
The transition from ($1$, "Count tails next round") to ($3$, "Count heads next round") : By the description of the experiment, if we are counting tails in the next round, then we counted heads in this round. So, this time while tossing the coins, we got $1$ head and two tails. Now, the two tails get counted for the next round, since we are counting tails, and we have to flip the coin which came heads, according to the experiment. The probability of getting $3$ tails, is then the probability that this coin comes tails, which is just $\frac 12$. So the transition probability is just $\frac 12$.
The transition from ($2$, "Count heads next round") to ($0$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got $2$ tails and one head. Now, the one head get counted for the next round, according to the experiment. But then, we already have more than $0$ heads from counting the previous head, so it is not possible to get $0$ heads after the next round! So the probability is zero.
The transition from ($2$, "Count heads next round") to ($2$, "Count tails next round") : By the description of the experiment, if we are counting heads in the next round, then we counted tails in this round. So, this time while tossing the coins, we got two tails and one head. Now, the one head get counted for the next round, since we are counting heads, and we have to flip the two coins which came tails, according to the experiment. The probability of getting $2$ heads, is then the probability that exactly one of the two coins comes heads, which is just $\frac 12$. So the transition probability is just $\frac 12$.
Try to compute the following and get back :
Transition from ($0$,"count heads next round") to ($2$,"count heads next round")
Transition from ($1$, "count tails next round") to ($3$, "count heads next round")
Transition from ($3$, "count heads next round") to ($1$, "count tails next round")
If it is right, then I will say you have got the grasp.