Cover times for Markov-generated binary sequences of length two (Q2192250)

The authors consider binary sequences that are generated by Markov chains and, in particular, the expected waiting time until all binary patterns of any given length \(k\) have been realised. The Markov chain under consideration is fairly simple: 0 jumps to 1 with probability \(\alpha\) (or stays at 0 with probability \(1-\alpha\)) and 1 jumps to 0 with probability \(\beta\) (or stays at 1 with probability \(1-\beta\)). The authors give an exact expression for the expected waiting time until all four patterns of length 2 have been observed. This is called the cover time for this set of patterns. Furthermore, they give an exact expression for the probability distribution of the random variable of the waiting time. They also consider cover times for sequences of given length \(n\geq 2\) which end with a specific pattern of length 2.