More seconds?

In the last blog post, in our attempt to find the probability that a player going second finishes second in a game with four players, we found that the probability that the player going first finishes first and the player going second finishes second (in a game with four players) is equal to the probability that a player going first finishes first in a game with four players times the probability that a player going first finishes first in a game with three players. Of course, it's also possible for the players going third or fourth to finish in first and the player going second to finish second. Since the player going in first is still in the game if this happens, the second condition then changes to F(2,3,1), since the player then has the second position.

The total probability that the player going second finishes the game in second place is therefore:

F(1,4,1)*F(1,3,1) + F(3,4,1)*F(2,3,1) + F(4,4,1)*F(2,3,1)

Now we can take a step closer towards a generalization. The probability that a player going in position n gets second place in a game with p players is:

F(1,p,1)*F(n-1,p-1,1) + F(2,p,1)*F(n-1,p-1,1) + ... + F(n-1,p,1)*F(n-1,p-1,1) +   F(n+1,p,1)*F(n,p-1,1) + ... + F(p,p,1)*F(n,p-1,1)

Let's actually try this out. I wrote a computer program that performs this calculation for a given n and p. Letting p be equal to four and varying n between the integers between 1 and 4 (inclusive), we get:

When n = 1: 0.2537844586561435
When n = 2: 0.2513862054039849
When n = 3: 0.24879532739096866
When n = 4: 0.24603400854886412

These values, when added, sum to 1, which is at least a somewhat decent verification that they are correct (more precisely, it is a necessary but not sufficient condition to it being correct). Interestingly the first player still has an edge over the other players.

More to come on this later, but this seems like a good place to stop for now.

Seconds, please?

A few posts ago I showed how we could find the probability of a player in position n in a game with p players finishing in first place. Now we can try and make that more general: what is the probability of a player in position n in a game with p players finishing in mth place?

Before we generalize it that far, however, let's first think about it for the case of the player getting second place. Let's suppose we want to find the probability that the player who goes second (in position two) in a game with four players finishes in second. What conditions have to be met for this to happen? Clearly, if the player is getting second, someone else is getting first, so one of the things that must happen is that someone besides that player wins the game. Let's consider what happens if the player going first gets first place. If we already know the player going first is going to win, then the chance that the player going second finishes in second in a game with four people is the same as the probability that a player going first in a game with three moves finishes in first place. Thus, the player going first gets first place and the player going second gets second place is equal to:

(Probability that player going first wins in a game with 4 players) * (Probability that a player going first wins in a game with three players)

This is getting pretty wordy, so let's invent some notation. Let's call F(n,p,m) the probability that a player in position n in a game with p players finishes in m place. The above expression can then be condensed to:

F(1,4,1)*F(1,3,1)

(Remember that we already found an algorithm that gives the probability of a player in position n in a game with p players finishing in first.)

         This has been pretty dense so far, so I think I'll stop here and continue on in the next post.

Chutes and Ladders, the real deal (part 2)

    Continuing on with the quest to find real-life applications for Chutes and Ladders, we take a look again at the directed graph mentioned in the previous past. As the directed graph for the real game of Chutes and Ladders is essentially no more than a larger version of this one, we should be good to stop here. Now that we have a rigorous basis to comparing other processes to Chutes and Ladders, the next step requires some creativity: we have to think of a real situation that is analogous to Chutes and Ladders based on a comparison of directed graphs. Of course reality is far more complex than Chutes and Ladders is, so finding a perfect analogy is next to impossible, but something close is better than nothing. Back in one of the first posts bringing up applications of graph theory, the process of a forest fire spreading was discussed. Let's see what we can do with that.
   
    Just as Chutes and Ladders progressed along randomly based on dice throws, a forest fire progresses randomly with time. Thus, while a dice throw represented one "iteration" in the Chutes and Ladders Markov Chain, some unit of time, say, a minute, represents an iteration in the forest fire Markov Chain. How might we define our states in this Markov Chain? With Chutes and Ladders, we defined the states based on what square a player was positioned on -- a player on the thirty-fifth square was said to be in the thirty fifth state. However, since a fire can be on multiple trees at once (while a Chutes and Ladders player can only be on one square at a time), it is more sensible to define the states based on the number of trees that have been set ablaze -- if thirty trees are on fire, the Markov Chain will be in state thirty. Moreover, the last state, just like in Chutes and Ladders, is an absorbing state. We do, however, have to assume that the fire travels in a fixed path and that the number of trees than can burn in the time interval is fixed (just like how you always spin between a 1 and a 6 in Chutes and Ladders), but so far this seems to have some potential. Now for the deal breaker: what is the analogy to chutes and ladders? Chutes are a bit difficult, since forest fires don't normally just fizz out when a certain number of trees are burned. However, a "ladder" might be possible if a group of trees are clustered so tightly together that when one burns, the others immediately burn too. The Markov Chain is instantly carried from one state to a higher state, just as what happens when a player lands on a ladder in Chutes and Ladders.
   
    The beginning of the directed graph, assuming that the maximum number of trees that can be burned in one time interval is three and the minimum is one, might look something like this...

   
       

    ...If the "forest" looked something like this:

    (Note that under this model, "red lines" are impossible. Yellow lines will appear if we decrease the number of trees that can be burned in one time interval down to zero).

    Although this forest fire example still seems a bit contrived, I think the similarities it does share with Chutes and Ladders are quite remarkable. With only a very small amount of tweaking, we can get a lot of information about this process with the tools already developed for analyzing Chutes and Ladders.

Chutes and Ladders, the real deal

    Now that the project is nearing an end, I thought it would be a good time to branch out from the Chutes and Ladders world and start looking in-depth at possible applications for the results I've obtained. Markov Chains are used all over the place to model real-world processes, but finding situations which are analagous to moving along a Chutes and Ladders board is a bit more tricky, especially because chutes and ladders make the movement a lot more irregular.

    One useful first step is to remove all of the "fluff" in the game and break it down to its simplest mathematical form. For processes that are Markov Chains, this can be done by representing them as "directed graphs". A graph, in this context, refers to a series of points connected by a series of edges. You can draw two points on a piece of paper, connect them with a line, and bam, you have a graph. Straightforward, right? Perhaps you can already see why graphs are so useful for simplifying complicated processes. In a directed graph, each of these points corresponds with a state in a Markov Chain, and an edge connecting two points signifies that there is a non-zero probability of going between the corresponding states. However, since the probability of going to state B from state A isn't necessarily the same as the probability of going to state A from state B, it is also necessary to specify which state is the "start" state and which state is the "end" state, and this is conventionally done by placing an arrow on the edge that points in the direction of the end state. Thus, there may be two edges between two vertices A and B: one that starts on A and ends on B and one that starts on B and ends on A.

    Here's an example of a directed graph for the "simplified" game of Chutes and Ladders introduced a few months ago:

    The simplified game (the arrow represents a chute)

     

    A rather crude directed graph. Putting in arrows made the image too cluttered, so here a green line signifies that it starts on the square furthest to the left between the two, a yellow line signifies that it starts and ends on the same square, and a red line signifies that it starts on the square furthest to the right between the two.

    Note that here the square on which the top of the chute is located is not represented by a vertex in the directed graph. It is what we might call a "pseudo-state" rather than a real state, since it is never possible for a player to be located on that state at the end of his or her turn. This square instead influences the graph by increasing the probability that a player lands on the square on which the end of the chute is located.
   
    More juicy details to come in the next post. Stay tuned.

More on order

In the last post, I listed the chance that the player going first wins in a game with 2 players. What happens, however, when the number of players in the game blows up, say to a million? The probability comes out to be close to 0.0015, which is just about equal to the probability of one player finishing the game in exactly 7 moves. This actually makes sense since if the player going first in a game with a very large number of players doesn't win in the shortest number of moves possible, chances are that someone else will. Thus, the chance that the first player wins is very close to the probability that he or she finishes in the shortest number of moves possible.

Let's switch gears for a moment and now consider the unlucky fellow who has to go last in the game. How does this change the math? This player, in order to win, cannot tie with anyone else, so all other players must finish in more than y moves. The probability of the player in last winning in y moves thus translates mathematically to:

Py * (1 - (P7 + P8 + P8 + ... + P(y-1) + Py)^(p-1)

Note that the only difference between this and the case with the first player is that this time, there is an additional term, Py, enclosed in the parenthetical expression.

Testing this out for the case when there are two players, we get that the probability of the second player winning is equal to 49.2, which is expected based on the probability we found of the first player winning (50.8). As the number of players gets larger and larger, the probability of the last player winning gets closer and closer to 0. When there are a million players, the probability of the last player winning is smaller than 1.0 * 10^-500. It is more likely that someone wins the Mega Million jackpot fifty times in a row than this happens.

Now that we have these two extreme cases down (first and last), let's try to be a bit more general: what is the probability of a player in order k in game with p players winning? We know that there are (p - k) players who this player trumps and ( k - 1) players who trump this player. Thus, this player can finish in the same number of moves as (p - k) players, but he or she must finish in a fewer number of moves than (k - 1) of the players. Thus, the probability of the player with order k winning is equal to:

        Py * (1 - (P7 + P8 + P8 + ... + P(y-1) + Py)^(k-1) * (1 - (P7 + P8 + P8 + ... + P(y-1))^(p-k)

Note that when k = 1 (player goes first) or k = p (player goes last), this turns into one of the two expressions discussed before.

In a game with four players, the probabilities of winning, in order from the player going first to the player going last, are as follows:

0.26007883
0.25322465
0.24657453
        0.24012197

        These add up almost exactly to 1, so our math is probably good.

Follow the leader...

        "First is the worst, second is the best,...". Order is clearly important to children. I'm sure we can all remember that tingly feeling of smug satisfaction we got when we were the line leaders for the day. However, does order really matter in a game of Chutes and Ladders? What statistical advantage does the first player have over the last?

In trying to break this down mathematically, let's first try to imagine a game of Chutes and Ladders where the game doesn't stop as soon as one player reaches the finish but continues until all players arrive there, and each player takes note of how many moves it took him or her to reach the end. Let's also imagine that, for now, we have three players playing the game: Alec, Betty, and Carl.

Suppose Alec finishes in 34 moves, Betty finishes in 42 moves, and Carl finishes in 57 moves. If this had been a "normal" game of Chutes and Ladders, order wouldn't have mattered, as Alec would have been the winner no matter what order the players made their moves in. Now suppose instead that Alec finishes in 45 moves, Betty finishes in 41 moves, and Carl finishes in 41 moves. This time, order clearly matters: if Carl had started before Betty, he would be the winner, but if Betty went before Carl, she would be the winner. From this we can see that order is really a way of "resolving ties": the first position trumps all other position, the second position trumps all positions but the first position, and this continues on and on until the last position, which is trumped by all other positions.

So how can we define this probability mathematically? Let's start with considering the probability that the player going first wins in a game with p players. Well, the best way to begin is to "partition" this probabilistic event (that the player going first wins) into a bunch of smaller events. The most natural way to do this is to break it up as follows: add the probability that the first player finishes in 7 moves (since it is impossible to finish in any fewer) to the probability that the first player finishes in 8 moves to the probability that the first player finishes in 9 moves, etc. Since there is no upper limit to how many moves a game of Chutes and Ladders must be finished in as there is a lower limit (7), we would have to go all the way to infinity to get a full partition, but since this is a practical impossibility, we will instead settle for a close approximation (as we have done before).

Understanding this partition business might be best done with the analogy of a cake. If the entire cake represents the probability that the first player wins the game, then a slice might represent the probability that first player wins in, say, 20 moves. The idea behind the "approximation" method can be similarly understood if we imagine that the cake is cut and served to a large number of guests so that each guests receives exactly one-half of the remaining cake. The first guest receives one-half of the total cake, the second guest receives one-fourth of the total cake, the third guests receives one-eighth, and so on. If we put the pieces given to the first twenty guests together, we would nearly, but not exactly, have the whole thing (bear in mind though that the probabilities we're dealing with aren't distributed in this fashion).

Thus, we can represent the probability as follows:

Approximate probability that the first player wins: P(1,7) + P(1,8) + P(1,9) + ... + P(1,n), where P(x,y) is the probability that a player in position x finishes in y moves and where n is some large number (in this case I'm using 266).

Let's think about what has to happen for P(1,y), 1<=y<=n, to be satisfied. Clearly, one of the conditions is that the first player has to finish in y moves. Remember those variables we defined in the last two posts? Those are probably going to be useful again. We call this condition Py, and, if y is between 1 and 266 (which we assume must be true), we can find Py from the information we obtained using the transition matrix of the Chutes and Ladders Markov Chain. Good. What about the other conditions? Clearly the other players can't win in fewer than y moves for the first player to win, but what happens if they finish in the same number of moves? As we already discussed, the first player's position trumps all the other positions, so even if one of the other players finishes in y moves, the first player still wins. Thus, we can represent the probability that one of the other (p-1) players finishes in y or more moves as follows:

        (1 - (P7 + P8 + P9 + ... + P(y-1))^(p-1)

        (A very similar expression was used in the previous post, so you can see that for a proper explanation of why this works, but the essence is that  we take the compliment of the probability that one player wins in (y-1) moves or fewer and raise that to the (p-1) power since this must happen (p-1) times independently).

Since these two conditions are the two conditions that must be met for the first player to win in y moves, this probability is given by their product:

Py * (1 - (P7 + P8 + P9 + ... + P(y-1))^(p-1)

        Summing hundreds of "P(1,y)"s together is, of course, most suited for a computer. The result, when we let the number of players be equal to 2, is approximately equal to 50.8, giving this player a total edge of about 1.6% over the second player. This is not a trivial advantage (it is higher than the typical edge that a card counter has over a dealer in Blackjack), but it is probably not worth fighting over either.

Much more multiplayer madness

So, in the last post we found the probability of at least one player out of p players finishing the game in exactly n moves, which we called Pa~n, to be 1 - (1 - Pn)^p, where Pn is the probability of one player finishing the game in n moves. However, to determine the probability of a game with p players finishing in n moves, we must still find the probability that nobody finishes the game in fewer than n moves.

We know that the probability that one player finishes in fewer than n moves is given by: P1 + P2 + ... + P(n-1). The probability that one player does not finish in fewer than n moves is therefore (1 - P1 + P2 + ... + P(n-1)). Let us suppose that only one player wins (under the definition of "number of moves" I'm using, it is possible for more than one player to "win"), meaning that one and only one player finishes the game in exactly n moves. This makes it impossible for that one player to win in fewer than n moves, but it's still fair game for the remaining p-1 players. That means the probability that nobody finishes the game in fewer than n moves is: (1 - P1 + P2 + ... + P(n-1))^(p-1)

Pa~n * Pb~n, or the probability that a game with p players finishes with exactly n moves, is therefore given by the expression:

(1 - (1 - (Pn)^p) * ((1 - P1 + P2 + ... + P(n-1))^(p-1)

Knowing this, we can estimate the expected number of moves as follows:

Expected number of moves ~= (1)*(Pa~1 * Pa~1) + (2)*(Pa~2 * Pa~2) + ... + (n)*(Pa~n * Pa~n)

Where n is some large number.

(See the post "Great Expectations" for an explanation of why this works).

I already found Pn with a program for n up to about 250 (which is sufficiently large for our purposes), so here's the estimated expected number of moves for the first few values of p:


p = 1 --> 39.2
p = 2 --> 26.5
p = 3 --> 21.9
p = 4 --> 19.5


Just to make sure I didn't make a mistake (not a rare occurrence), I decided to instead modify the simulation program I wrote to allow for more than one player and calculated the expected number of moves based on the average of a large number of games. Here are the fist few results from that:

p = 1 --> 39.2
p = 2 -- > 26.3
p = 3 --> 21.7
p = 4 --> 19.3

They're close, but there's still clearly a slight error. I'll look into this more, but I suspect it has something to do with the assumption that only one player wins.

Here's an Excl graph showing the results (number of players on the horizontal axis, expected of number of moves on the vertical axis):

As more and more players are added, the expected number of moves of the winner gets closer and closer to 7, since 7 is the smallest possible number of moves.

Now that this approach was done, is the Markov strategy worth considering again? I think the only way that could be done would be to build a transition matrix around the moves of the winning player (for example, the winning player is probably more likely to spin larger numbers and land on big ladders), but this seems to be more trouble than it's really worth.

Lads and ladders

Everything posted so far has pertained to a game played with only one person, but since Chutes and Ladders is a multiplayer game, we should also consider how the data changes when there are 2 players, 3 players, or some number n of our choosing players. I want to focus this post specifically on how the expected number of moves for a game changes as the number of players vary.

Actually, that could use a bit more clarification. When dealing with one player, the number of moves was equal to the total number of times the spinner is spun. While that is a perfectly acceptable definition for games involving more than one player, the generalized definition of "number of moves" I want to use is the number of times the winner of the game spins the spinner. This removes any complications about what order the players make their moves in.

Well, why should there be any change? After all, unlike in Sorry or a similar game, players' game pieces do not interact with each other. The best way to think about it is that the more players there are in the mix, the more likely one of them is to get "lucky" and finish the game in fewer than the expected number of moves for an individual player (39.2). An analogous situation is that if one person were rolling a die, it would take her, on average, six throws to get a 6, but if she and ten other people were all rolling dice at the same time, a 6 would be expected to come up much sooner.

There are two ways to find the expected number of moves: by using probabilities of completing the game in 1 though n moves, where n is a large number, (the "approximation" method) and by doing some magic math on the canonical form ("Q matrix") of a transition matrix for a Markov Chain (the "exact" method). I have no idea where to begin with the second option, so I'll start with the first.

How might we find the probability that a game with p players finishes with n moves? This is probably easier to think about if we pretend that, instead of the game stopping as soon as one player reaches the final square, it continues until all players reach the finish. The number of "moves" in a game, however, will still be the number of moves the winner of the game makes.  Let's think about what has to happen: we need to have at least one of the p players finish the game in n moves (the "at least one" is crucial here. With the way I've defined "moves" for games with more than one player, it is possible for there to be more than one winner) and we need to have no players finish the game in fewer than n moves. So, if Pa~n is the probability that at least one player finishes the game in n moves and Pb~n is the probability that no player finishes the game in fewer than n moves, the probability that both of them happen together is Pa~n times Pb~n  since they are both independent events.

Hmm. Pa~n would probably be fairly straight forward to find if we wanted to know the probability of exactly one player finishing in n moves, but finding the "at least one" complicates it immensely, since we now have to sum the individual probabilities of one, two, three, all the way up to p players winning the game in n moves, which could be rather tedious for large p. If you ever get a complicated event like this, sometimes it's easier to consider the complement of that event, that is, the chance that event does not happen. The complement of Pa~n is the probability that no players win the game in n moves, and this is something that we can work with. The probability that one player wins in 7 moves is 0.0015, so the probability that one player does not win in 7 moves is 1 - 0.0015. The probability that all p players don't win in 7 moves is therefore (1 - 0.0015)^p since these are all independent events. This is the complement of Pa~n, so to find Pa~n, all we have to do is subtract this from 1, or 1 - (1 - 0.0015)^p. Why is this true? Remember that the sum of the probabilities of all events must total to 1. Since any event and its complement make up all events and there is no overlap between the two, their probabilities must sum to 1.

Since I'm about 300 words past the word limit already, I'm going to finish this out in the next post.

Playground construction

            Keeping up with the spirit of tweaking the conditions of the game and observing how the length of the game is effected, this week I also wanted to mess around with the placement of chutes and ladders. Normally we think of chutes as harmful and ladders as helpful, but this, perhaps, mustn't always be the case. For instance, if a short chute puts a player a few squares away from a very long ladder that the player had already passed, that chute may actually be advantageous. Can we find a case on the Chutes and Ladders board for which this is true?

            To find out how a chute or ladder impacts the length of the game, we can remove it (which alters the transition matrix) and see how the expected number of moves changes. I started with what seemed to be the most likely candidates for these "good" chutes and "bad" ladders. The chute from square 47 to square 26 caught my eye since it puts the player in a good position to land on the behemoth ladder on square 28; however, removing this chute still decreased the expected number of moves (from 39.2 to 36.8). My second choice was the chute from square 16 to 6, but removing this also decreased the expected number of moves (from 39.2 to 38.0). After checking the remaining cases, no such chute or ladder could be found.


            So, then, how about we create one ourselves? Let's see what happens if we put a chute from square 29 to square 27. This makes it a bit more likely for the player to land on the ladder at square 28 without setting them back too far, and it decreases the expected number of moves from 39.2 to 38.0. What happens if we instead make the chute go from square 29 to square 26? The expected number of moves drops again to 37.9. Even though this set the player back further, the increased chance that this gives him or her of landing on the big ladder makes up for it. In fact, this chute has the best effect if it goes from square 29 to 23, where the number of moves set back is equal to the size of the spinner (expected number of moves is 37.2).

           I want to generalize this result a bit more and perhaps establish under what conditions a chute or ladder will be "good" or "bad", but for now, that's all folks.

You spin me right round...

    This week I was finally able to indulge my childish tendencies by breaking the rules of Chutes and Ladders.

    In a normal game of Chutes and Ladders, the spinner has a "size" of six: there are six possible moves. This week I decided to figure out what spinner size would produce the lowest expected number of moves to complete the game. While it might seem that increasing the spinner size would allow us to advance along the board faster, and hence, reduce the expected number of moves, increasing the size also makes landing on the final square more difficult. The ideal value is therefore in the middle of two extremes.

    Thankfully, two weeks ago I prepared a program to find the expected number of moves for a standard game with a spinner of size six, and finding this value for other spinner sizes only requires a small tweak in how the transition matrix is constructed. The results were as follows:

Spinner size -- Expected number of moves

1 -- Infinite (the game cannot be completed with a spinner of size one)
2 -- 60.7
3 -- 65.9
4 -- 54.5
5 -- 45.6
6 -- 39.2
7 -- 34.7
8 -- 31.8
9 -- 30.3
10 -- 28.8
11 -- 27.4
12 -- 27.0
13 -- 26.2
14 -- 26.0
15 -- 25.8
16 -- 25.9
17 -- 26.0
...

    The results continue to shoot up after this, so the ideal spinner size is 15.

    As you can see, the ladders and chutes cause some irregularities in the pattern (most noticeably when the spinner has a size of 3). This begs the question: what would be the ideal spinner size for a modified game of Chutes and Ladders with no chutes or ladders? A similar analysis shows that the ideal size is then 13. Thanks to the simplified nature of this version, however, this value can be found without using any complicated Markov chain analysis. The expected number of moves for a game of spinner size n can be approximated by:

         The first fraction is an approximation for the expected number of moves required to be within n moves of the finish. "n" is also the expected number of moves required to reach the final square when you are within n moves of that square (the probability is always 1/n, so the expected number of moves is n).

    Plugging in various values of n, again, reveals that the ideal spinner size is 13.

    Let us take a moment to breathe in and enjoy this brief respite from the pain of Markov Chains.
    

    

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.

Great expectations

            Last week I finally managed to find out the probabilities of completing a game of Chutes and Ladders in various numbers of moves, so can we finally (mathematically) answer the nagging question, what is the expected number of moves required for a player to complete a game of Chutes and Ladders?

            When we determined this value using the computer simulation, we had actual data to work with: the total number of games played and the number of moves each game lasted for. We divided the latter number by the former number and out popped the average. Can we come to the same result with just some theoretical probabilities? 

            Well, we can get pretty close. To reiterate, when we're talking about the average number of moves per game, we mean the total number of moves divided by the total number of games:

            We can then break down the "total number of moves" as follows:

            Note that the numerator continues on infinitely since there is no theoretical limit to the maximum number of moves a game can last for.

            Now separating each term in the numerator into an individual fraction and simplifying...

            This is an expression we can work with, since we found the exact probabilities of completing the game in various numbers of move using the transition matrix. There is still one problem though. As already mentioned, this expression requires us to know the probability of completing the game in every possible number of moves, which is a theoretical impossibility since there are infinitely many. However, we can still make a good approximation based on a large number of moves. As you can see from the previous weeks' graphs, the probability of finishing a game in a triple-digit number of moves or more is very slim, so we aren't hurt too much if we leave a lot of these larger values out. Using the probabilities of completing the game in 1,2,3,...,300 moves, I got an approximate average of about 39.21529. The estimated average of completing the game from the computer simulation was also around 39.2, so not bad!

            While that much precision is probably good enough for Chutes and Ladders, there might be other scenarios where more precision is needed, so it's still important to know whether there's a way to determine the exact number of expected moves. It turns out there is a way to do this using (you guessed it!) matrices.

            This will probably be the most obscure part of this project to date (and everything else hasn't exactly been a skip through the park), and since I'm already nearing the 500 word limit here, I think I'll just push off that explanation into the next entry. Stay tuned.

Closed-form expressions: the "Ladders" of math

            In order to find the probability of completing the game in a certain number of moves, we have to make a 101 by 101 matrix, giving us a total of 101 * 101 = 10201 entries. However, thus far, we have really only cared about one entry: the entry that gives the probability of moving from the first square to the last square. This means that we have 10200 matrix entries that are essentially meaningless. A natural question, therefore, is can we somehow ignore the information that doesn't matter to us and thereby simplify the process of finding out what does matter?

            Unfortunately, we can’t just start cutting away at rows and columns of the transition matrix and expect the entry we care about to remain unchanged. It’s the intermediate steps that ultimately determine how we get from point A to point B. If we want to find a way to simplify it, we have to look for more general shortcuts in matrix multiplication. One solution is to see if there exists a “closed form” expression for the value of an entry in a matrix as that matrix is raised to various powers. What exactly does that mean?

            Consider the following example. Suppose we wanted to find the sum of the first one hundred positive integers, that is, the value of 1 + 2 + 3 + … + 100. We could go about this problem by adding the terms individually (1 plus 2 is 3, 3 plus 3 is 6, 6 plus 4 is ten…), but that would clearly take a while. However, there is a shortcut. It can be shown that the sum of the first n positive integers is equal to [(n)(n+1)]/2. The sum of the first one hundred integers is therefore equal to (100)(101)/2, or 5050. [(n)(n+1)]/2 would be considered a closed form expression for the sum of the first n integers since it allows us to perform an otherwise complicated calculation in one simple step by plugging in a value for one variable.

            So, can we do the same thing for matrices? Well, in some cases, certainly. If we have a matrix filled entirely with 0's, we can determine the value for any given entry in that matrix if it’s raised to a power: it’s always 0. Of course, that trivial case doesn't help too much. Can we do the same for a matrix whose entries change as it’s raised to various powers? Well, here’s one I found. Let’s call it M:

            Now see what happens as we raise M to a few different powers:

            Do you see the pattern? The value in the bottom-left corner is always equal to (1/2) times the power that the matrix is raised to and all the other values remain constant. Thus, we can determine the value of the entries as M is raised to some positive integral power without actually multiplying M by itself over and over again. Of course, this is still a rather simple case and doesn't provide us with some general pattern that can be applied to other, more complicated matrices. I did some extensive Google searching to see what sort of matrices have these convenient closed-form expressions, and unfortunately I couldn't find anything that would be applicable to the behemoth transition matrix for Chutes and Ladders (if Google doesn't have the solution, chances are it’s time to throw in the towel). I will keep this question in the back of my head as I keep going on with this project, but at this point it doesn't look like there is a simple solution (I could see what happens if I replace the numbers with variables in the 101 by 101 matrix, but… chances are that won’t be useful. Try it with a 2 by 2 matrix and you’ll see why!).

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.

Hello World

Hello, and welcome to the blog. I'll be devoting this first post to explaining what I'll be doing for the next three months, besides playing Chutes and Ladders.

The question I am trying to answer is how can the game of Chutes and Ladders be modeled mathematically, and how does the structure of the game influence that model? For instance, how many moves on average should it take to complete a game of Chutes and Ladders, and how might changing the spinner size affect this average? What happens to this average if we add a ladder here or remove a chute there? You get the idea.

I'll be answering these questions using mathematical models, so I'm going to need some way to confirm that my results are valid. Since I would have to play the game thousands of times to get any statistically significant data, my plan is to instead create a simple command-line program that can run a million simulations of the game in a heartbeat and report the results. I suppose I won't be playing the game much after all!

While figuring out how to model the game is the primary goal of my project, it's equally important that I come up with a way to do it efficiently. Even with the convenience of a computer, there may be a lot of computation required. Thus, I'll be trying different approaches to answering my proposed questions and seeing which work most efficiently. At the end of my project, I'll write a short report documenting all of my findings.

More board game and math shenanigans to come.