Data-crunching and (kinda) pretty graphs

Phew. As mentioned at the end of my last blog, this week I combined the two programs I wrote last week -- the program that generates the transition matrix for Chutes and Ladders and the program that computes the powers of an inputted square matrix -- and found the probability of a player computing a game of Chutes and Ladders in various numbers of moves. Without further adieu, here are the results:

This graph represents the cumulative probability of completing a game of Chutes and Ladders by a certain move (represented on the horizontal axis) up to the hundredth move. The probability of finishing a game tends towards 1 as the number of moves increases. This must be true since the last square is an absorbing state, but it also makes intuitive sense. A game of Chutes and Ladders must end at some time!

The next graph represents the probability of completing a game of Chutes and Ladders in exactly a certain number of moves. This can be easily obtained from the data used to make the last graph. For instance, if we looked at the value of the probability when the number of moves equals 3, we would get the probability of finishing the game in 1 moves plus the probability of finishing in 2 moves plus the probability of finishing in 3 moves. The value of the probability when the number of moves equals 2 would be finishing in 1 move plus the probability of finishing in 2 moves. If you subtract the two, you are left with the probability of completing a game in exactly 3 moves. This can be generalized: to find the probability of completing the game in exactly n moves, subtract the probability that the game will be finished by the end of the (n-1)th move from the probability that the game will be finished by the end of the nth move. Anyways, here is the graph:

Look familiar? This graph really resembles the graph generated from running the Chutes and Ladders simulation (with a million trials), which is shown below.

It's important to realize that while these graphs are similar, they are not the same. The first graph gives the "absolute" probabilities of completing a game of Chutes and Ladders in certain numbers of moves while the second one merely estimates these values. The law of large numbers discussed in a previous post tells us that the second graph should resemble the first graph more and more as additional trials are performed (for example, we would expect the graphs to be more similar for a million trial simulation than for a ten-thousand trial simulation). A million being a fairly large number gives us a pretty close estimation.

Although it might be hard to see from the graphs, the minimum number of moves required to win is seven. A person is most likely to complete the game on the twenty-second move, which has about a 2.49% chance of occurring (this represents the peaks of the last two graphs and the point where the slope is increasing most rapidly in the first graph).