Great expectations (part 2)

            Picking right up from last time, remember that Chutes and Ladders is what we call an absorbing Markov Chain, which means that there is at least one state from which it is impossible to escape. Those states are referred to as absorbing states. In the case of Chutes and Ladders, the only absorbing state is the state corresponding with the last square on the game board, since the game ends once a player reaches that square. What we want to do is rearrange the transition matrix's rows and columns so that all of the non-absorbing come first in the matrix. Then we want to create a new matrix called Q that represents a transition matrix from all the non-absorbing states to all the non-absorbing states (the first step makes this easier to do). That probably won't make much sense without a picture:

 

                Once Q is found, the next step is to subtract it from the identity matrix, I, (the identity matrix is a square matrix with 1's going diagonally from the top-left corner to the bottom-right corner. It is called the "identity" matrix because when you multiply any matrix by the identity matrix, you always get the same number back, just like how whenever you multiply a number by 1 you get the same number back. The identity matrix always has the same dimensions of the matrix that you're adding or multiplying it to.) giving you the matrix (I - Q). The next step is to take the inverse of (I - Q) (the inverse, M^-1, of some matrix M, is the matrix such that (M)*(M^-1) = I), which will give us a new matrix which we'll call N. If we take the sum of the values in the n'th row of N, we get the expected number of iterations that occur before an absorbing state is entered (in Chutes and Ladders, an "iteration" is a spin of the spinner). 

              Why does that work? Unless you're Euler or Gauss, it shouldn't be obvious at all. There is a proof of this that uses a bit of linear algebra and probability theory available here --> http://www.dartmouth.edu/~chance/teaching_aids/books_articles/probability_book/Chapter11.pdf if you want to see why, but I won't explain it here (partially because the notation would be a pain to do in Microsoft Paint).

            Getting back into Chutes and Ladders, since the only absorbing state is the one-hundredth square which is already located at the bottom-right corner of the matrix, we don't have to rearrange it at all to find Q. Q is just the matrix formed by the first hundred rows and hundred columns of the transition matrix. I quickly modified the program to produce the transition matrix for Chutes and Ladders to get Q. To get from Q to I - Q,  all you have to do is take all the values along the diagonal, subtract them from one, and take the negative of all other values.

            Now comes the tricky part. Taking the inverse of a matrix is not trivial. Rather than stumble around trying to program a "matrix inverter" on my own, I decided to search the web for some Java code that could help me out. What I found was a package called "JAMA" (http://math.nist.gov/javanumerics/jama/) that contained a ton of tools for performing operations on matrices, among them being a tool for inverting matrices. Using this program, I found (I - Q)^-1 and added together all the values in the first row (representing the expected number of moves required to reach the absorbing state from the first square).

            The value obtained, perhaps very, very slightly off due to Java floating-point inaccuracies, is:

            39.225122308234

            Ahh, now that's better.