More matrix madness

            The first order of business is to make a slight correction. When the game of Chutes and Ladders begins, players start not on square one but outside of the game board next to square one. This means that the transition matrix for the game should be 101x101, not 100x100, since we now have an additional state. There is also a ladder on square 1 which I previously ignored (Hey, what is a ladder doing on the starting square? That doesn't make sense. Oh well, let's just forget about it), so this means that the data I gathered by running the simulation last week is slightly off. Taking into account this ladder, the expected number of moves for a game of Chutes and Ladders comes closer to 39.2 as opposed to 39.6. The general shape of the graph I posted on one of last week's entries remains the same.

           

            The lesson to be learned here is that ignoring something important on a game board generally isn’t a good idea.

           

            I also fixed the program I was writing to raise matrices to a given positive integral power (jargon incoming). The first time I tried to write it using recursion, but a lot of heap space was used for large matrices being raised to large powers, so a StackOverflowError was being thrown for all but the simplest computations. When I tried doing it iteratively, for some reason I thought it would be easier to try an OO approach centered on a “Matrix” object, but somewhere in my algorithm I did an assignment by object reference rather than by value which caused some bugs to appear. After searching for that error in vain, I just decided to strip away the OO and got everything working fine.

           

            Since typing out 101 * 101 = 10201 numbers by hand didn’t sound too appealing, I also wrote a program this week that builds the transition matrix for the game of Chutes and Ladders. Here’s a picture of that matrix reduced to 2.5 font:

            The matrix might not look square, but that's just because I didn't get around to aligning all the rows properly. Some rows will have different numbers of characters based upon what numbers are in those rows. Also, it was more convenient to build this matrix with the rows being “from” and the columns being “to” (the opposite of how I represented transition matrices in past posts), but since it's a square matrix, the math doesn't really change. What was previously the (i,j)th entry is now the (j,i)th entry, but everything else stays the same, even when the matrix is raised to other powers. Next week I'll get to raising this behemoth matrix to different powers and obtaining some exact information on the probability of completing a game of Chutes and Ladders in a certain number of moves.