1

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?

Stephanie.M
  • 13

1 Answers1

0

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.)

Math1000
  • 36,983
  • Yes! Thank you! This is exactly what I had but when I got the expected number of steps I said, "I must be doing this wrong." I think it is a very interesting result indeed. – Stephanie.M Oct 21 '19 at 21:43
  • I think it is due to the fact that you remain in the same state if you "over-roll." – Math1000 Oct 21 '19 at 21:44
  • now, what would P be if We still start at S. We travel clock-wise around the board, according to the roll of a die,and we still are trying to reach H. Now, however, if a roll would take us past H, we simply continue past H. For example, suppose we are sitting at 4. A roll of 1 takes us to 5, a roll of 2 takes us to H, a roll of 3 takes us to S, a roll of 4 takes us to 1, and so forth. Once you reach H you remain there forever. – Stephanie.M Oct 21 '19 at 22:42
  • I'm afraid that's an entirely different question and you would be better off asking it as a new question than in the comments to this answer. – Math1000 Oct 21 '19 at 22:43