Markov Chain with dice rolling board game

249 Views Asked by At

Simple board game.

S---1---2---3---4---5---H

You start at S. Each turn, your roll a standard six-sided die, and move forward that number of spaces. Your goal is to reach H. You can only get to H on an exact roll; if you roll a number that would take you past H, you do not move. For example, suppose you are sitting at 4. If you roll a 1, you move to 5. If you roll a 2, you move to H. If you roll anything else, you do not move. Once you reach H, you remain there forever.

What is the transition matrix?

1

There are 1 best solutions below

4
On BEST ANSWER

The transition matrix is straightfoward; enumerate the states as $S,1,2,3,4,5,H$, then we have $$ P= \begin{pmatrix} 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\ 0 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6 & 1/6\\ 0 & 0 & 1/3 & 1/6 & 1/6 & 1/6 & 1/6\\ 0 & 0 & 0 & 1/2 & 1/6 & 1/6 & 1/6\\ 0 & 0 & 0 & 0 & 2/3 & 1/6 & 1/6\\ 0 & 0 & 0 & 0 & 0 & 5/6 & 1/6\\ 0 & 0 & 0 & 0 & 0 &0 & 1 \end{pmatrix}. $$ Note that the states $S$, $1$, $2$, $3$, $4$, and $5$ are transient and $H$ is absorbing, so $P$ is in the canonical form $$ P = \begin{pmatrix}Q&R\\0&I\end{pmatrix} $$ where $Q$ is the substochastic matrix corresponding to transitions between transient states, $R$ is the substochastic matrix corresponding to transitions from a transient state to the absorbing state, and $I$ the identity matrix. The probability of transitioning from a transient state $i$ to a transient state $j$ in exactly $k$ steps is simply $Q^k$; summing this for all $k$ yields the fundamental matrix $N=\sum_{k=0}^\infty Q^k$. Now, since $Q$ has norm strictly less than one, it can be shown that $\sum_{k=0}^\infty Q^k = (I-Q)^{-1}$ (recall the formula for a geometric series), and hence $$ N = \left( \begin{array}{cccccc} 1 & \frac{1}{5} & \frac{3}{10} & \frac{1}{2} & 1 & 3 \\ 0 & \frac{6}{5} & \frac{3}{10} & \frac{1}{2} & 1 & 3 \\ 0 & 0 & \frac{3}{2} & \frac{1}{2} & 1 & 3 \\ 0 & 0 & 0 & 2 & 1 & 3 \\ 0 & 0 & 0 & 0 & 3 & 3 \\ 0 & 0 & 0 & 0 & 0 & 6 \\ \end{array} \right). $$ Here the $(i,j)$ entry of $N$ is the expected number of visits to state $j$, given that the chain started in state $i$. Moreover, the expected number of steps before being absorbed is given by $$ N\cdot\mathbf 1 = \left( \begin{array}{cccccc} 1 & \frac{1}{5} & \frac{3}{10} & \frac{1}{2} & 1 & 3 \\ 0 & \frac{6}{5} & \frac{3}{10} & \frac{1}{2} & 1 & 3 \\ 0 & 0 & \frac{3}{2} & \frac{1}{2} & 1 & 3 \\ 0 & 0 & 0 & 2 & 1 & 3 \\ 0 & 0 & 0 & 0 & 3 & 3 \\ 0 & 0 & 0 & 0 & 0 & 6 \\ \end{array} \right)\begin{pmatrix}1\\1\\1\\1\\1\\1\\1\end{pmatrix} = \begin{pmatrix}6\\6\\6\\6\\6\\6\end{pmatrix}, $$ which is the same $6$ regardless of the starting state. (An interesting result, in my opinion.)