Introduction to Markov Processes

WHAT IS A MARKOV PROCESS?

Many natural systems can have their behavior described nicely as a series of states. For example: Insects are born in an ‘inside an egg’ state. Eventually most will transition to a ‘gross mucus-y larvae’ state, followed by an ‘annoying flying thing’ state, and ending in a ‘dead’ state. If we know the series of states and the order they occur in, we can represent the process as a chain of states, called a Markov chain:

The numbers on each transition represent the probability of an insect in the previous state going to the next state at the next time step. We know there’s random variation between insects in a species, so we can represent the variations by having different transitions an insect might make with different probabilities. The time step will be some discrete unit that you choose based on the context. For an insect with a short life span, a useful time step might be about an hour. So if we have 200 eggs of insects whose life cycles are represented by the above chain, 100 of them will hatch within an hour, and 50 will hatch in the second hour.

The crucial thing about this process is that the only thing we need to know to predict the likelihood of an insect transitioning into a particular next state is the current state. This property of a process is called the Markov property, and any random process that adheres to it is a Markov process.

When I first started looking into Markov processes, I was confused about why Markov models limited themselves to the Markov property. Why not just say that we can take other factors into account than the current state, such as previous states or external variables (like, for the insects, an external variable could be seasons; they aren’t expressed in the insect’s state, but they affect their life cycles)? Couldn't we then describe many more processes with Markov-like models, and much more accurately? Well, we could. But the beauty of a Markov model is its ability to describe many different things that occur in nature even though it’s very simple. This simplicity makes data from Markov processes much easier to manipulate. A good example of cool things you can do when you assume the Markov property is use of the Viterbi algorithm, which I will post about later.

Markov models can't account for wasps' likelihood of death increasing as they get closer to me and my vaccuum cleaner.

YAY, ANOTHER EXAMPLE

The above chain is very simple, because we know that insects basically always go from the first to the last state in order. But what if they didn’t? What if there were a species of insect that could sometimes go back into their eggs, or sometimes hatched already in the flying stage? I would find that deeply alarming, but we can still represent it with a Markov chain by adding in arrows for the new transition possibilities:

            

Here are a couple of things that can be inferred from the above Markov chain:

•         Half of the insects hatch out of their eggs into larvae, while the other half go directly to the flying state. If we have one of the eggs, there is a 50% chance it will hatch into a larva.
•      Eighty percent of the larvae will turn into flying things, and ten percent (presumably the losers) will go back into their egg for a while instead of getting on with their lives.
•      After the insects die five percent of them rise again, returning to the flying state as zombies.

It’s also good to note that the time period expressed by the Markov chain doesn’t really ‘end’. So, it’s not that  5% of the above insects return to the flying state and then after that they definitely die; any insect in the dead state has a 5% chance of zombification at the next state, no matter how many  times they have been dead before. Since there’s no alternative dead state whose only outgoing arrow loops with itself (as in the previous example) these insects can’t be truly killed. I hope you can now appreciate the seriousness of Markov processes.

Having understood his species' Markov chain, he rejoices in his immortality.

Bonus links!

• Some good Markov questions on Mathematics Stack Exchange.
• A much better but more mathier description of Markov processes.
• The very not awful program I used to make the chain diagrams.

Next Post: (probability 0.85 of being about) Markov Assumptions (0.15 of being about my sordid personal life - based on the current post only!)