# Key Questions
Key questions to come out from this example:
- [[What is a Markov Chain?]]
- [[How do I use a Probability Transition Matrix?]]
- [[What is a Markov Chain?#Terminal States|What is a terminal state?]]
- [[What is a Markov Chain?#Episodes|What is an epsiode?]]
# The Setup
Example snakes and ladder board is used from [this Numberphile video](https://www.youtube.com/watch?v=nlm07asSU0c)
Snakes and ladders is a simple board game where you roll a dice and move forward on a board. There are also snakes, that move you backward, and ladders that can move you forward.
In the snakes and ladders game board below (which has squares 0 to 9 on the board, ladder from 4 -> 7 and a snake from 8 -> 2), you start on square 0 and roll an ordinary 6 sided dice each round. If you land on a snake, you instantly move down and if you land on a ladder you instantly move up. If you ever reach square 9 you finish the game (i.e. you stay on square 9 until the start of the next game). Here is a pictorial representation:
| | 7 ➡🪜 | 8 🐍⬇ | 9 |
| :-: | :---: | :---: | :---: |
| | 6 | 5 | 4 🪜⬆ |
| 0 | 1 | 2 🐍⬅ | 3 |
## Terminal State
Note that by the rules of the game, Square 9 has the property that once you are there you stay there forever. This is called a terminal state.
# Example Problem
**Problem**: What is the probability to end on exactly square 7 after exactly 3 rolls? (Note: if you reach square 9 at any point, you will *not* be at square 7)
**Answer:** The probability is $\frac{23}{6^3}$. In other words there are 23 ways the dice can come out so that you end up on square 7.
## Brute Force Solution (Horrible!)
There is a horrible brute force solution to this problem. (The point of this gross solution is to convince you this is horrible and we need a better way)
You can enumerate all the different ways to get there by brute force. You can look at cases like "How can I get there by rolling twice, then hitting the snake, and then rolling again?". We use the shorthand "R" for roll, so this case is labeled as "RR (snake) R". Using this, you get a horrible collection of cases that looks like this:
| Roll Type (R = Roll) | Number of Possible Rolls | **List of Rolls** |
| ------------------------------------------------- | ------------------------ | ------------------------------------------------------------------------------------------------- |
| RRR (ladder 4 → 7) | 3 | $\binom{4-1}{3-1}$ = **3 ways for 3 dice to sum to 4**: 112, 121, 211 |
| RRR (no snakes or ladders!) | 10 | $\binom{7-1}{3-1}$ = **15 ways for 3 dice to sum to 7**, but must ensure 4 → 7 ladder is NOT hit! |
| | | 115, 124, ~~133~~, 142, 151 |
| | | 214, ~~223~~, 232, 241 |
| | | ~~313~~, 322, 331 |
| | | ~~412, 421~~ |
| | | 511 |
| RR (snake 8 → 2) R | 4 | **5 ways for 2 dice to sum to 8**, but must ensure 4 → 7 ladder is NOT hit! |
| | | 265, 355, ~~445~~, 535, 625 |
| RR (snake 8 → 2) R (ladder 4 → 7) | 4 | **5 ways for 2 dice to sum to 8**, but must ensure 4 → 7 ladder is NOT hit! |
| | | 262, 352, ~~442~~, 532, 622 |
| R (ladder 4 → 7) R (snake 8 → 2) R | 1 | 415 |
| R (ladder 4 → 7) R (snake 8 → 2) R (ladder 4 → 7) | 1 | 412 |
| **Total:** | **23** | |
(Note: The number of ways that $k$ dice rolls can sum to $n$ is sometimes given by the stars-and-bars-counting $\binom{n-1}{k-1}$.)
## Markov / Dynamic Programming Solution
The key is to realize that instead of answering the question directly, it is better to answer the more general question:
**New Problem**: What is the probability to end at square $s$ after $t$ rolls?
This problem is actually *easier* to answer than the original, because the previous work at time $t$ helps you calculate future answers at time $t+1$. You end up with a table that looks like this:
### Number of Ways to Be at Each Square
Here we count the number of ways to get to each square (the probabilities are simply the number of ways divided by the appropriate power of 6). We count both "PreSL" (before we slide down the snakes+ladders) and "PostSL" (after we slide up the snakes/ladders). In later rounds, it is also convenient to keep track of each starting location on its own line (so starting from s2 etc)
![[Pasted image 20250108115541.png]]
In each round, we can figure out the number of ways to get to a certain square by looking at the previous round. For every entry on the previous round, we can move forward by the result of a dice roll. To get from the "PreSL" (before the snakes and ladders happen) to the "PostSL" line, we simply move the paths from square 4 to square 7 and paths from square 8 to square 2.
The operation we are doing to go from one round of probabilities to the next is matrix multiplication! This leads us to the idea of thinking in terms of a transition matrices to solve our problem.
## Matrix Multiplication Solution
We can encapsulate the rules for what happens with each roll as a 10x10 matrix which encodes all the start/end points for rolls by the rules:
$P_{s,s^\prime} = \mathbb{P}(\text{Move from }s\text{ to }s^\prime \text{ in one step} )$
This is called the [[How do I use a Probability Transition Matrix?|Probability Transition Matrix]]. Note that the **rows** of this matrix tell you the probability you can **move to a given location**. For example the 0th row of the matrix is:
$P_{0,:} = \frac{1}{6}[0,1,1,1,0,1,1,1,0,0]$
This represents the fact that starting from Square 0, there is a 1/6 chance to move to the Squares 1,2,3,5,6,7 and there is a 0% chance to move to Squares 0,4,8,9. (Note that the effect of the snakes and ladders is already included here) This exactly matches the Round1 PostSL from the table!
The full matrix is created by justing looking at each starting point (and therefore each row) and seeing what the possible locations you can move to are. The right way to see the matrix is to read it row by row. We also used a dot instead of a 0 for the entries that are 0 to make it easier to read.
$P = \frac{1}{6}\begin{pmatrix}
\cdot & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot \\
\cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & 2 & \cdot & \cdot \\
\cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & 2 & \cdot & \cdot \\
\cdot & \cdot & 1 & \cdot & \cdot & 1 & 1 & 2 & \cdot & 1 \\
\cdot & \cdot & 1 & \cdot & \cdot & \cdot & 1 & 1 & \cdot & 2 \\
\cdot & \cdot & 1 & \cdot & \cdot & \cdot & 1 & 1 & \cdot & 3 \\
\cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & 1 & \cdot & 4 \\
\cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 5 \\
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 6 \\
\cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 6 \\
\end{pmatrix}$
$\begin{align}
x &= 2+3\\
&=5
\end{align}$
Note that the sum of each row is 1 (aka 100%), because starting from anywhere there is a 100% chance you end up somewhere.
The probabilities for being at any location can be determined by matrix multiplication using matrix multiplication for the [[How do I use a Probability Transition Matrix?|Probability Transition Matrix]]:
$ \vec{p}_{t+1} = \vec{p}_{t}P $
where $\vec{p}_{t}$ is the vector of probabiliteis for round $t$ , i.e. the entries of $\vec{p}_{t}$ are exactly $\mathbb{P}(\text{At position }x\text{ at time }t)$.
## Python Code
You can generate the transition matrix with a for loop in python in a simple easy to read way that puts the game logic into the entries of the matrix. We use numpy for the matrix in Python
```python
import numpy as np
TransitionMatrix = np.zeros((10,10))
#loop over all possible starting states called "from_ix"
for from_ix in range(10):
for dice_roll in [1,2,3,4,5,6]:
to_ix = from_ix + dice_roll #where you move to when you roll
if to_ix >= 9: #if you go >9 then you end at 9
to_ix = 9
if to_ix == 4: #ladder from 4->7.
to_ix = 7
if to_ix == 8: #snake from 8->2
to_ix = 2
TransitionMatrix[from_ix,to_ix] += 1/6
```
Then you can also easily calculate the probabilies by doing matrix multiplication. The symbol for matrix multiplication in numpy is "@" (you can also do np.matmul)
```python
round0_probs = np.array([1., 0, 0,0,0,0,0,0,0,0])
round1_probs = round0_probs @ TransitionMatrix
round2_probs = round1_probs @ TransitionMatrix
round3_probs = round2_probs @ TransitionMatrix
```
This will output the answers we saw before. To make them nice integers (counting the number of ways), multiply through by the denominator of the probabilities:
```python
6*round1_probs=array([0., 1., 1., 1., 0., 1., 1., 1., 0., 0.])
36*round2_probs=array([ 0., 0., 6., 2., 0., 3., 4., 8., 0., 13.])
216*round3_probs=array([ 0., 0., 23., 6., 0., 8., 11., 23., 0., 145.])
```