4.I.9C

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 / 2$. The outcome determines a score for that turn, which depends also on the cumulative score so far. Write $S_{n}$ for the cumulative score after $n$ turns. In particular $S_{0}=0$. When $S_{n}$ is odd, a head scores 1 but a tail scores 0 . When $S_{n}$ is a multiple of 4 , a head scores 4 and a tail scores 1 . When $S_{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 $S_{n}$ is a multiple of 4 . State clearly any general theorems to which you appeal.

*Typos? Please submit corrections to this page on GitHub.*