Nonuniform infinite random monkeys and Hamlet

Question

I have a rudimentary grasp of the second Borel-Cantelli lemma and vaguely understand how finite patterns can repeat infinitely often. The one proof I am familiar with that verifies this unfortunately relies on a stochastic process of uniform probability distributions over some finite discrete random variable.

What happens if I change this process so that it is no longer i.i.d and no longer uniform? To make it more concrete, let's impose the following conditions on the infinite monkey experiment (the first two aren't really mathematically relevant but the experiment wouldn't work without it):

1. The typewriter is infinitely durable with an infinite tape
2. The monkey is immortal and is infinitely entertained by punching on the typewriter
3. It is a qwerty keyboard but all keys except the alphabetic keys, the period, the comma and the space key have been removed.
4. The monkey really likes to jab at the k and d keys.
5. It's also a monkey, so it has a much higher probability of hitting several keys simultaneously when it's aiming for a particular key. (so it's a Markov chain)

I have already seen this thread, and one of the links to an article that made the experiment non-uniform. The math was beyond me, but it seems the article only made a non-uniform assumption between the space key and everything else. Every other key split probabilities equally among themselves.

Can the monkey still write Hamlet an infinite number of times?

Mathematically, my question would just be:

Does the second Borel-Cantelli lemma hold for all finite patterns for $n$-th order Markov processes over non-uniform finite distributions?

Answer 1

This is not anymore a question about the second Borel-Cantelli lemma since, as the OP notes, the independence assumption is lost. Nevertheless, yes every Markov chain on a finite state space will realize every possible pattern, infinitely often and almost surely. I wrote every possible pattern because one could imagine that after S, T and O there is a mechanism that prevents you to type P, then of course the pattern STOP will never appear. Barring that, everything happens, just like in the classical monkey setting.

The relevant mathematical result is called the law of large numbers for ergodic Markov chains. See page 35 of the chapter on Markov chains in Introduction to Probability by Charles Grinstead and J. Laurie Snell (this book is freely available on the web).