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).

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.

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.

Math without math

           Suppose you’re a gambler in Renaissance Italy. Well, actually, you haven’t done much gambling at all recently. You’ve been in a bit of a slump since you lost much of your money to your friend Gerolamo Cardano, who boasts that he can predict outcomes of dice games based on mathematics. You yourself don’t care much for mathematics – you’re more of a doer than a thinker – but his success really struck you. Clearly there is more to these games than lucky numbers and divine intervention. Might there be some way for you to make predictions about the outcomes of dice rolls like Cardano does, but without using any sort of mathematical formula?

            You start thinking, and suddenly you have a brilliant idea. If Cardano is correct and different dice roles occur with a certain frequency, you should be able to figure out that frequency by rolling dice and seeing how often a certain roll appears. You decide to see if you can predict the frequency of rolling a seven with a pair of dice. You toss your pair of dice ten times and get a seven twice. Does this mean that, out of every ten times you roll a pair of dice, two of those times their values must sum to seven? You try it again, but this time you only get a seven once. In frustration, you repeat this process hundreds of times over, but the number of sevens you get for every ten rolls is always variable. Still, you realize that getting five sevens out of ten rolls happens a lot let frequently than getting one seven out of ten rolls. Perhaps there is still some deeper pattern at play. You decide to combine all of your results, and you notice that the number of times you rolled a seven divided by the total number of rolls is very close to 1/6. You continue tossing your dice some more, and you realize the more tosses you perform, the closer the ratio of seven-rolls to the total number of rolls is to 1/6.

            The formal name for this very familiar principle is the Law of Large Numbers, which states that the frequency of an event occurring over a large number of trials is close to the expected frequency of that event occurring. For example, if you were to flip a coin ten times, it wouldn’t be out of the usual to get 60% heads, but getting 60% heads out of a thousand coin flips would probably cause you to doubt the fairness of that coin.

            This allows us to deduce the probability of an event by “working backwards”. One issue, however, is with the definition of “large”. Does large mean ten thousand or ten billion? The answer is that it really depends on the system being considered, but the number of trials is probably “large enough” if there is very little fluctuation in the results if that same number of trials is repeated again.

            For complicated systems like Chutes and Ladders, computing the probability first in this “empirical” fashion is a good way to confirm that the probability determined later with mathematics is correct. One of the tasks I had in mind at the start of this project was finding out the expected probability for completing a game of Chutes and Ladders in a certain number of moves. I discovered that “large” for Chutes and Ladders is in the millions, so computing this probability by playing the game over and over again is out of the question. Instead, in this past week I wrote a program that can simulate games of Chutes and Ladders very rapidly and report on the number of times a game was completed in a certain number of moves. Here are the results represented by an Excel graph:

            

The average number of moves required to finish a game obtained was 39.879.

Of course, obtaining the probabilities in this fashion doesn’t reveal why the results are what they are, which I think is the more interesting part.

So?

After “what?”, I suppose the next nagging question to address is “why?”. Why am I doing all of this mathematics on a board game like Chutes and Ladders? Can any of this be applied to other scenarios?

            

Well, in truth, the results of this investigation will be mostly self-contained. The rather specific configuration of the Chutes and Ladders game board makes its “mathematical model” unique and largely inapplicable to other events. While the results are very specific, the process used to obtain these results can be more easily generalized. Part of my task this week was to explore some other Markov processes which might be “modeled” in a similar fashion to Chutes and Ladders. Specifically, I was looking for a class of Markov Chains called “absorbing Markov Chains”. An absorbing Markov Chain consists of one or more states from which you cannot transfer into another state; such a state is called an “absorbing state”. Chutes and Ladders has one absorbing state – the very last square – and may therefore be classified as an absorbing Markov Chain.

            

One of the more interesting examples of a “real-life” absorbing Markov Chain I could find (courtesy of Mrs. Bailey) was the process of a fire spreading about in a forest. In this somewhat simplified model, a fire on one tree has a certain probability of leaping onto a neighboring tree based on their proximity. This process continues until all of the trees in the forest are consumed or the fire goes out on its own. We may consider this an absorbing Markov Chain, as all the states that can exist after the fire has gone out represent the absorbing states (clearly if there is no fire, no trees can burn).

A "forest" in the process of being burned. See citation for more information on this applet.

My hope is that some of the techniques used to model Chutes and Ladders can be helpful for modeling other   Markov Chains. I'm going to be trying as much as possible to consider the "bigger picture" when working on this project and will focus more on approaches that can be broadly applied to other other Markov Chains. Perhaps if I exhaust Chutes and Ladders, I can work on other models by recycling some of the techniques I already used.

* Wilensky, U. (1997). NetLogo Fire model.http://ccl.northwestern.edu/netlogo/models/Fire. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.
* Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

Chains and ladders

In the last post, I mentioned that the process of advancing along from square to square in Chutes and Ladders was really a Markov Chain. So what exactly does that mean? A Markov Chain is defined to be (bear with me) a process consisting of a finite number of states where the probability of moving from one state to another depends only on the current state. Like most concepts in math, this is probably best understood with an example. We can consider a very simplified model of the weather to be a Markov Chain. Suppose that the weather can only be sunny or rainy, and if it's sunny one day, there's a 90 percent chance it will be sunny the next day, and if it's rainy one day, there's a 40 percent chance it will be rainy the next day. We have two different states ("rainy" and "sunny"), and the probability of switching between these two states only depends on the current state (if the weather was rainy-sunny-rainy, the chance of it being rainy on the fourth day only depends on the weather on the third day, not on the first or second day's weather). For Chutes and Ladders, we can think of each square as a different state, and the spinner as a "transitioner" between states. Since the outcome of the spinner does not depend on what square you're on (there are always 6 options with a 1/6th chance of landing on each option), Chutes and Ladders seems to pass the Markov chain test.

It may seem cruel to reduce a children's game down to a "Markov chain", but this is actually very useful. Let's momentarily return back to the weather example to see why. Suppose it is sunny today, and we want to find the probability that it is sunny two days from now. For this to happen, the weather can either be sunny-sunny or rainy-sunny over the next two days. The probability of the first one occurring is (0.9)*(0.9)*100 = 81% and the probability of the second one occurring is (0.1)(0.6)*100 = 6%, so the total chance is 81% + 6% = 87%. A few observant mathematicians noticed that these sorts of calculations looked a lot like matrix multiplication. In fact, if we have a Markov chain with n different states, we can construct what is known as a "transition matrix" where the (i,j)th entry in the matrix corresponds with the probability of transitioning from state i to state j. For the weather example, the transition matrix would look like this:

The entry in the top left corresponds with the chance of transitioning from "sunny" to "sunny", the entry in the top right corresponds with the chance of transitioning from "sunny" to "rainy". If we square this matrix, we get:

Notice that in the top left corner, we have the probability 0.87, which is the value we found previously. In our transition matrix, the value in the top left corner was the probability of going from "sunny to sunny" in one change of state. When we square the transition matrix, the value in the top left corner is the probability of going from "sunny to sunny" in two changes of state. In general, if M is the transition matrix of a Markov chain, then the (i,j)th entry in the matrix M^n corresponds with the probability of transitioning from state i to state j in n changes of state.

In Chutes and Ladders, we can use this to find the probability of going from "state 1" (the first square) to "state 100" (the last square) in a certain number of moves. Of course, since there are 100 spaces in Chutes and Ladders, the transition matrix is going to be 100 by 100, so it is no simple task to construct it. More to come on this later.

A "random" post

Before I get into the meat of this post, I suppose I should explain how exactly the game of Chutes and Ladders is played for anyone who is unfamiliar with it. Players begin by choosing one game piece each and placing it on the first square of the one hundred square game board. When it is a player's turn, he or she spins a spinner containing the numbers one through six and moves his or her piece forward the number of spaces that the spinner lands on. If a player lands on the bottom of a ladder or the top of a chute, he or she will then move his or her piece to the space corresponding with the top of the ladder or the bottom of the chute, respectively. A game is won when a player reaches the hundredth square. If a player spins a number that would require him or her to move beyond the hundredth square (for example, spinning a six while on square 98), the player does not move.

At the heart of making predictions about the outcome of Chutes and Ladders games is the assumption that the process is random. While in theory it may be possible for someone, with enough practice, to be able to control the outcome of a spin, I will be assuming that the outcome of the game does not depend on the experience of the players. Under this assumption, all players have an equal chance of winning when the game begins, and the winner is selected purely by chance.

Understanding how this chance works on a small scale is fairly simple. There are six possible outcomes on the spinner and each one is equally likely, so there is a one-sixth chance that a player will spin a one, a one-sixth chance that a player will spin a two, etc. on each turn, and the chance of a player landing on a certain square in that turn can be calculated accordingly based on the player's position on the board. However, computing chance becomes much more complicated when it is done across multiple turns. For instance, it's not nearly as easy to determine the probability of a player landing, say, exactly twenty squares away in six moves, especially when taking into account the influence of the chutes and ladders. Well, it turns out that the process of progressing along the games board is really a "Markov Chain", and this allows us to pull a few tricks that greatly simplify these sorts of calculations. However, as the margins of this blog are too small to contain such a discussion (ok, I'm really just near the word limit for this entry), I'm going to push that explanation off into the next post. Stay tuned.