Transition Probability Matrix of Tossing Three coins

Question

Three fair coins are tossed, and we let $X1$ denote the number of heads that appear. Those coins that were heads on the first trial (there were $X1$ of them) we pick up and toss again, and now we let $X2$ be the total number of tails, including those left from the first toss. We toss again all coins showing tails,and let $X3$ 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 $X0 = 3$. Then, $\{ Xn \}$ is a Markov chain. What is the transition probability matrix?

I think that there are 4 states, but not sure how to define them.

For instance if I let state 1 = # of heads on 1st trial and 2= # of tails on 2nd trial and 3= # of heads on 3rd trial, it seems it is zero probability from state 1 to state 3.

Answer 1

Let $H_n\in \{0,1,2,3\}$ be the number of heads after iteration $n$. Obviously, $H_n+T_n=3$ Then $H_n$ would be enough to denote the state (we'd have then 4 states) - but then the Markov Chain would not be stationary (the transitions would depend on time). We want to avoid that, normally, if it's possible. Let's add then an indicator variable $W_n=\{0,1\}$, so that $W_n=0$ iff the next coins to pick are the heads. Then the state $S_n=(H_n,W_n)$ gives a stationary Markov chain with $4\times 2=8$ states.

Answer 2

As I wrote above, there are eight states, which can be represented in this graph:

The numbers in each vertex describe the number of heads, then tails and whether the heads or the tails should be counted for the next transition. (Be sure the transitions away from any vertex sum to 1.0.)

It is a simple matter to label each edge by the probabilities of transition (head counting to tail counting or vice versa).