Exercise :
Given the transition probability matrix over the space $\mathbb{X} = \{s_1,s_2,s_3,s_4,s_5\}$ $$P = \begin{pmatrix}1 & 0 & 0 & 0 & 0 \\ p & 0 & 1-p & 0 & 0 \\ 0 & 1-p & 0 & p & 0 \\ 0 & 0 & p & 0 & 1-p \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}$$ If you have a coin that flips to head with probability $p\neq 1/2$, can you fix an algorithm model for the flip of a non-biased coin, with the help of the chain given ? Specifically, we want the algorithm to end with probability $1$ in finite time and with probability $1/2$ for each of the two possible outcomes.
Question :
This is part of an exercise which asked first of all to compute the probability $\mathbb{P}[T_1 < T_5 | X_0=s_3]$ which I did by solving a boundary value problem. It finally turns out that this probability is $1/2$.
First of all, my question here is that I do not completely understand the exercise. Why does it mentioned that the coin is actually biased, since $p\neq 1/2$ but then asks to model an algorithm for a non-biased coin ? And I cannot seem how to proceed on using the chain given for modelling the coin flip asked.
Any help will be greatly appreciated.
Reorder the states as $(s_2,s_3,s_4,s_1,s_5)$ to obtain $$ \tilde P = \pmatrix{0&1-p&0&p&0\\ p&0&1-p&0&0\\ 0&p&0&0&1-p\\ 0&0&0&1&0\\0&0&0&0&1}, $$ then $\tilde P = \pmatrix{Q&R\\\mathbf 0&I}$ where $Q$ is the submatrix of $\tilde P$ corresponding to transitions between transient states, $R$ is the submatrix of $\tilde P$ corresponding to transitions from transient states to recurrent states, and $I$ is the submatrix of $\tilde P$ corresponding to transitions between recurrent states (this is the $2\times 2$ identity matrix since there are two absorbing states. Now, for each nonnegative integer $k$, the $(i,j)$-entry of $Q^k$ is the probability of $\{X_k=j\mid X_0=i\}$. It follows that the expected number of visits to each transient state, conditioned on starting in a transient state, is given by the fundamental matrix $$ N = \sum_{k=0}^\infty Q^k. $$ Since the columns of $Q$ each sum to strictly less than $1$, $N=(I-Q)^{-1}$ (much like how $\sum_{k=0}^\infty z^k = (1-z)^{-1}$ for real $z$ with $|z|<1$). We compute \begin{align} N &= (I-Q)^{-1}\\ &= \pmatrix{1&p-1&0\\-p&1&p-1\\0&-p&1}^{-1}\\ &= \frac1{1-2p(1-p)}\pmatrix{1-p(1-p)&1-p&(1-p)^2\\p&1&1-p\\p^2&p&1-p(1-p)} \end{align} The probability of reaching absorbing state $j$ when starting from transient state $i$ is given by the $(i,j)$ entry of \begin{align} NR &= \frac1{1-2p(1-p)}\pmatrix{1-p(1-p)&1-p&(1-p)^2\\p&1&1-p\\p^2&p&1-p(1-p)}\pmatrix{p&0\\0&0\\0&1-p}\\ &= \frac1{1-2p(1-p)}\left( \begin{array}{cc} p(1-p(1-p)) & (1-p)^3\\ p^2 & (1-p)^2 \\ p^3 & (1-p) (1-p(1-p)) \\ \end{array} \right) \end{align} When $p=\frac12$, this simplifies to $$ \pmatrix{3/4&1/4\\1/2&1/2\\1/4&3/4}. $$