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.