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.