Markov chains and coin tosses
Jan Chelmecki
Introduction
Consider the following game. Two players, A and B, each choose a pattern: A’s is HTH and B’s is HHT (H - Heads, T - Tails). They then keep tossing a symmetric coin and writing down the results of each toss in a sequence. The player whose pattern shows up (in a run) first wins. What is the probability of A winning? What are the chances in the general case, with arbitrary patterns? 1 First, observe that the state of the game can be fully described by the last three letters in the sequence. We can focus only on how much of either pattern is visible at the end. The possibilities are T (or no pattern), H, HH, HHT, HT, and HTH. Every toss adds to the ending and changes it. With states defined in such a way, we can regard the process as a Markov chain – the future depends entirely on the present and is independent of the past. At each moment, the process forgets the past and starts fresh from the current state. We can now visualize the game as a board game, 2 where each arrow indicates a probability of transition equal to .
T
HT
H
HH
HHT
HHT
It is now clear that the game is biased towards B, even though it might have seemed that the game is fair (since both patterns are of the same length). The game keeps going around the T-H-HT-T loop until it jumps
1 The topic was inspired by an exercise in [3]. This essay tries to provide some intuition to the abstract martingale approach presented in [1]. 2 The idea of those diagrams is taken from [2] and [3].
221
Made with FlippingBook - Online catalogs