Perturbation of Markov Chains
Christine Burnley · Mathematics Magazine · 1987
A simple fair game can be played by two people who have an equal number of pennies: each flips one coin, and, if the two flipped coins match each other (heads or tails), Player 1 wins both coins; otherwise, Player 2 wins both. The game ends when one of the two players has all the pennies. Clearly each has an equal chance of winning if both start with the same number of pennies, but what if one player has more to begin with? Or what if one player somehow cheats whenever he has only one penny left? In order to consider these questions, it is useful to model the game with a Markov chain [2]. If the total wealth between the two players is n pennies, one can build an (n + 1) X (n + 1) matrix P where the rows and columns are numbered 0 through n, and the entries Pij of P are defined as follows: Pij= the probability that Player 1, having i pennies, will have j pennies after the next flip. In this case, P (which is called a Markov chain or transition matrix), looks like