This week Occupy Math is going to open a Pandora’s box called a Markov Chain. Occupy Math used a Markov Chain to win lunch money during a part of his university career with a game called Hexer. He also does not advise imitating this behavior. Occupy Math is a trained, professional mathematician.
A Markov Chain is the next step up from a simple probability distribution, like 50% heads for a coin.
The game of Hexer is played with 4 six-sided dice. It is a solitaire dice game and not a bad way of keeping yourself amused for five minutes. Here are the rules.
- Roll all four dice to start.
- If you get no sixes, you lose.
- If you get sixes, put them aside (these are reserve sixes) and roll the remaining dice.
- If, when you roll less than four dice, you get no sixes, you have to pick up one of your reserve sixes and put it back in play.
- You continue until you have four reserve sixes (WIN!) or roll all four dice and get no sixes (LOSE!).
Occupy Math has talked in the past about the fact that people are not, in general, good at estimating probabilities. They seem to be very bad at estimating the probability of winning Hexer. The Markov Chain in this post is a tool for figuring out the odds of winning Hexer. DON’T WORRY about the complicated diagram, below. Occupy Math has solved it with an animation (I bet you never learned that technique in math class).
There are six places or states you can be in while playing Hexer. These are losing, winning, or having 0, 1, 2, or 3 reserve sixes. When you roll the dice you make a transition from one of these states to another. A Markov Chain is made up of a list of the states you can be in and the probability, for each state, of transitioning to each other state. Occupy Math got out the binomial distribution and computed the transition probabilities for Hexer. They appear in the diagram below. The binomial distribution is used for experiments that can come out two ways. For Hexer these two outcomes (for each die) are “I rolled a six” and “I did not roll a six”. This means that the dice are being used like very biased coins that give us a success (head) only one time in six. The states are Start, Lose, Win and 1, 2, or 3 reserve sixes. Start is also no reserve sixes.
The diagram is a bit much – the blue fractions are probabilities of things getting worse, the green fractions are the probabilities of things getting better. When there is no arrow, you cannot get there from here and the win and lose states keep all the probability that gets to them. That’s why they have looped arrows labelled “1”.
We can now use the diagram to play all possible games of Hexer simultaneously! Animation of this appears below.
Occupy Math uses a technique he calls the sand pile
algorithm to solve diagrams like the one above. Its actually
pretty simple (except for having to type in all those probabilities).
Put a pile of sand on “Start”. Over and over, for each state with sand on it, divide the sand on each state according to the probabilities on the outgoing arrows and move the sand. The animation below shows this process.
- The big blue block at the start of the animation is all the sand (probability) on “Start”.
- The lose (red) and win (green) states just accumulate sand (probability).
- Since the sand follows the probability, the flow of sand simultaneously includes every way the game could go, in the exact proportions they go that way.
- The animation lets you see the probability (or sand) flow through
the states. The animation is looped so a copy of the first and last
frame are broken out.
- From left to right these states are Lose, Start (0), A(1), B(2), C(3), and Win. The numbers are the number of reserve sixes.
Even though this is a simple analogy-based method of solving, it is actually quite accurate.
The sandpile model was invented by Occupy Math when he was trying to use simultaneous linear equation solvers and crashed his computer (not enough memory). Other people have also spontaneously invented the sandpile method. For the sandpile algorithm you only need to store the sand level on each state and the transitions with positive probability. The computer was crashing, in part, because it was storing all the connections, not just the necessary ones. Anyhow, the final sand level (in numbers) for Hexer is 89.02% lose, 10.98% win so the odds of winning are just under 11%.
Hexer is a solitaire game – but Occupy Math made it a betting game as follows. The other person actually rolls the dice. If they lose, they pay one dollar. If they win, they are paid five dollars. Quite a few people thought those were good odds, especially after they were told that the odds of losing on the first throw are less than one-half (which is true). The payout scheme “one if you lose, five if you win” would be fair if the odds of winning were 20% – but they are not.
Occupy Math will finish with some observations:
- You could play Hexer with any number of dice – but four dice give you the very worst odds of winning.
- Another way to compute the odds is to program a computer with a reliable random number generator to play the game and then have it save win-and-loss statistics for 1,000,000 games. This is a pretty good elementary programming assignment.
- Another thing that is interesting to investigate is the number of rolls needed to (i) win, (ii) lose, or (iii) resolve a game. If you increase the number of dice this can get really long.
Now that he is older Occupy Math feels a little bad about taking away the other students’ lunch money. People noticed Occupy Math was ahead pretty reliably, but their explanations were usually some version of “he has psychic powers” or “he has incredible luck” (remember I never touched the dice). The truth was, all I had was math.
There are a number of classroom activities, for a probability, statistics, or data management class, that can be done with Hexer. Use chips, not dollars. Do you have a similar game with interesting odds or game mechanics that you would like to share? If so, comment or tweet! Occupy Math is always hungry for good ideas.
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics