USING GAMES TO TEACH MARKOV CHAINS

Primus: Problems, Resources, and Issues in Mathematics Undergraduate Studies, Dec 2003 by Johnson, Roger W

ABSTRACT: Games are promoted as examples for classroom discussion of stationary Markov chains. In a game context Markov chain terminology and results are made concrete, interesting, and entertaining. Game length for several-player games such as Hi Ho! Cherry-O and Chutes mid Ladders is investigated and new, simple formulas are given. Slight modifications to Monopoly rules are discussed to fit it into a Markov chain model with the ultimate goal of determining the long-run frequencies for visiting the various game properties.

KEYWORDS: Markov chains, matrix algebra, pedagogy, probability, teaching.

INTRODUCTION

I introduce the section on Markov chains in my Stochastic Models course using games. In particular, I especially enjoy bringing in the games Hi Ho! Cherry-O and Chutes and Ladders to class to illustrate Markov chain terminology - and have students play these games a bit, before going on to develop the theory to answer some interesting questions about these games. In addition to being a good learning device, I believe the use of games promotes the idea that this material can actually be fun to study. For many it certainly brings feelings of nostalgia!

In this article Hi Ho! Cherry-O and Chutes and Ladders are presented as games which can be modeled as stationary Markov chains with a single absorbing state. For such games simple formulas for the probability mass function, the expected value, and the standard deviation of the number of turns it takes for the winner to finish are given. As far as I know, these formulas, while elementary, do not appear elsewhere in the mathematical literature. Monopoly is also presented as an example where students will see the value of determining steady-state probabilities. My focus here, however, is providing instructors with an example of a stationary Markov chain that allows students to see the utility of probabilistic models.

For further games not mentioned in this article which make use of Markov chain techniques the reader may wish to examine the papers [3,5,11, 17,21] listed in the References.

SOME MARKOV CHAIN GAMES

In this section I present some examples of stationary Markov chain games with a single absorbing state that an instructor may wish to discuss with his or her students. For those instructors who are about to teach this material for the first time a few Markov chain fundamentals are briefly reviewed to keep the article as self-contained as possible. A number of sources, including [8], may be consulted for further details on Markov chains.

The goal of the game Hi Ho! Cherry-O is to pick all 10 cherries from your tree, filling your bucket, before any of your opponents do so. The game board allows for up to four players. On a particular turn of this game a player spins a spinner which will point to one of seven equally likely regions when it comes to rest. The possible outcomes of a spin are

One Cherry Pick one cherry from your tree and put it into your bucket

Two Cherries Pick two cherries from your tree and put them into your bucket

Three Cherries Pick three cherries from your tree and put them into your bucket

Four Cherries Pick four cherries from your tree and put them into your bucket

Bird Take two cherries from your bucket and place them back on your tree (if you have only one cherry in your bucket, put that one back; if you have no cherries in your bucket, do nothing)

Dog Same rules as for landing on Bird

Spilled Bucket Dump all the cherries out of your bucket and place them back on your tree

It is understood that an "exact count" is not necessary to win the game. If, for instance, a player has 7 cherries in her bucket, she would win on her next turn by landing on either 'Three Cherries' or 'Four Cherries'. The possible states for an individual playing this game are 0, 1, 2, . . ., 9, 10 corresponding to the number of cherries the individual has in their bucket.

Once again, it is clear that this game may be modeled as a Markov chain. Where we land next only depends on our current position (along with our next roll of the die) and not our previous history of positions. As one does not remain at the base of a ladder or at the top of a chute, there are 101-(9 10) = 82 states in this Markov chain which can be labeled 0 (for off the board), 1, 2, ..., 81 (note that board numbers are relabeled here). If you would like to give your students a Chutes and Ladders type of problem but don't wish them to deal with the complications that go along with an 82 by 82 probability transition matrix, you may wish to have your students deal with a version having a smaller game board as in [14].

With both Hi Ho! Cherry-O and Chutes and Ladders natural questions include '"What's the chance the game is won in a certain number of moves?" and "What's the expected game length?" These questions will be answered in the next Section and rely on the fact that (P^sup m^)^sub i,j^ gives the chance of going from state i to state j in m turns.

A more immediate application of this fact concerns the dice game Ship, Captain, Crew (with rules as stated by [18], for variations see [12]). The player rolls five dice, trying to produce a 6 ('Ship'), a 5 ('Captain'), and a 4 ('Crew') in that order. Any one die may be tossed up to three times. As a Ship, a Captain, or a Crew are obtained these dice are put aside and not thrown again. If Ship, Captain, and Crew are obtained, then the remaining two dice are added to determine the score or 'cargo' (a value 2 through 12, here) and can be rolled again subject to the three toss limitation. If a player fails to get a Ship, and a Captain, and a Crew then they gain no cargo (i.e. score 0). The player with the most cargo wins. Here is a sample play by one player: