Matrices big and small

One my goals this week was to finally construct the hundred-by-hundred transition matrix for the full game of Chutes and Ladders, but since I wanted to be sure that I was doing it correctly (specifically that my “Markov treatment” of the chutes and ladders was correct), I started out with a simpler version of Chutes and Ladders, pictured below.

Taking the leftmost square to be the start and the rightmost square to be the end, the arrow represents a chute.

Here is the transition matrix that was obtained:

The entry of interest here is the number in the bottom-left corner, which represents the probability of getting from the first square to the last square in n moves, where n is the power that the transition matrix is raised to. I was able to trim down the program I wrote last week to instead model this simplified game, and I verified that the transition matrix was valid.

One of the important things I got out of this is that the transition matrix should reflect the probability of landing on a square at the end of a move, not at the end of a roll. As you can see, the fifth row down is filled with 0s, which is expected since it is impossible to be on the top of a ladder at the end of a move. While the fifth column is also filled with 0s, these can be replaced with any other numbers and the other entries won’t be affected as we raise the matrix to various powers since, after all, it’s impossible to be on the fifth square at the beginning of a move in the first place. In fact, we can cut out the fifth row and fifth column entirely without altering the other entries as the matrix is raised to different powers.

Another thing to point out is that the very last column consists of only one non-zero entry, and that entry is a 1. This is the indication that that state is an absorbing state.

Since the transition matrix for the full Chutes and Ladders game is a hundred-by-hundred matrix, I figured it wouldn’t be practical to input it into a calculator, so I instead wrote a program that raises an inputted square matrix to various powers (not that this helps a whole lot, sheesh that thing is big). Unfortunately I found that this program works only for a select number of cases, so I’m in the process of hammering out some bugs and will update this as soon as that is fixed.