Markov chains and coin tosses
after the first loss or when the game stops (in which case he keeps the money). Players behave independently of each other and all follow the same strategy.
player 1
player 2
player 3
player 4
player 5
player 6 toss
£1 for H
T
lost
£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
The chart above demonstrates an example course of the game when A = HTHT. In this case, the casino earned £6 (£1 from each player) and paid £16 + £4 = £20 to the winners (players 3 and 5).
The game is fair for each of the players, so the average net gain of the casino must be 0. 3 Hence the expected number of tosses (which is always equal to the total number of £1 collected from the players) must equate to the average sum of winnings. It is easy to see that the latter is always the same and depends entirely on the pattern. Indeed, let N be the number of the player who put in his first bet when the pattern started showing. He wins £2 n . The player N + n − k wins 2 k if and only if the last k letters match up with the last k letters from A . We thus proved that
Eτ A = A : A where τ A is the moment when A shows up and A : B is defined by
min{ n,m }
A : B = X δ
k ( A,B )
k =1
k , if the last k characters from A match the first k characters from B and 0, otherwise. n
where δ k ( A,B ) = 2
and m are the lengths of A and B , respectively. The notation is adapted from [3].
3 This is not obvious. If ( X n ) is a martingale and τ is a stopping time, it might not be the case that EX τ = EX 1 . A good example is the Casanova betting system described in [3]. A player starts by betting £1, then £2, £4, etc. He doubles the bet after each loss, hoping that the final win will cover the total loss. He stops playing after the first win, keeping the £1 surplus. Denote by X n his net gain after the n -th turn. Because the game is fair, ( X n ) is a martingale. Let τ be the first moment when 0 as n →∞ so ’ X n = 1’ is almost sure to happen sometime. Observe that X τ ≡ 1, even though EX n = EX 1 = 0, for every n . In the problem presented in this essay, however, Doob’s theorem applies as in [1] and the equality holds.
223
Made with FlippingBook - Online catalogs