Markov chains and coin tosses
It follows from the formula that one would expect to toss a coin 2 n − 2 times before getting n heads in a row. Also, note that patterns of the type AAA...ABBB...B have the lowest waiting time because they never match their shifts.
Before the next paragraph, we will need to generalize our formula to find the average time Eτ AB of waiting for A , when building on some initial pattern B (which does not contain A ). We will modify the game analogy. Players 1, 2, 3, etc. behave as always but now, there are also players 0, -1, -2, ..., - m +1 ( m is the length of B ) who behave as if they were already in the game when the sequence B started showing. The money they would have won in those fictitious rounds is treated as their initial capital (players who lost have a capital of 0).
Here is an example course of the game, when A = HTHT and B = HHT.
player -2 player -1
player 0
player 1
player 2 toss
£1 for H
H
£2 for T
£1 for H
H
lost
£2 for T
£1 for H
T
£4 for H
lost
£1 for H
H
£8 for T
£2 for T
£1 for H
T
Note that the bets in grey are not part of the game. Player -1 enters the game with a capital of £4 – all others have £0. As in the previous example, the total amount of money lost to the casino equals the number of rounds (£2 earned from players 1 and 2). Because of the players 0, -1, -2, ..., the total winnings are always A : A , as in the previous example. Since each of the players plays a fair game, their average income must be zero. Here, however, the players always start with an initial capital of B : A in total. Hence B : A = A : A − Eτ AB (the initial capital equals the average final capital) and it follows that
Eτ AB = A : A − B : A
Probability of winning
Let A and B be two patterns such that neither of them is contained in the other. Let τ = min{ τ A ,τ B } denote the moment the game ends. The numbers
p A = P ( τ = τ A )
and
p B = P ( τ = τ B )
are the probabilities of A and B winning, respectively.
224
Made with FlippingBook - Online catalogs