4.I.9C

Markov Chains
Part IB, 2006

A game of chance is played as follows. At each turn the player tosses a coin, which lands heads or tails with equal probability 1/21 / 2. The outcome determines a score for that turn, which depends also on the cumulative score so far. Write SnS_{n} for the cumulative score after nn turns. In particular S0=0S_{0}=0. When SnS_{n} is odd, a head scores 1 but a tail scores 0 . When SnS_{n} is a multiple of 4 , a head scores 4 and a tail scores 1 . When SnS_{n} is even but is not a multiple of 4 , a head scores 2 and a tail scores 1 . By considering a suitable four-state Markov chain, determine the long run proportion of turns for which SnS_{n} is a multiple of 4 . State clearly any general theorems to which you appeal.