Markov chain

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a Markov chain, named after Andrey Markov, is a discrete random process with the Markov property. A discrete random process means a system which can be in various states. The system also changes randomly in discrete steps. It can be helpful to think of the system as evolving through discrete steps in time, although strictly speaking the "step" may have nothing to do with time.

An example of a Markov chain is the dietary habits of a creature who only eats grapes, cheese or lettuce, and whose dietary habits conform to the following (artificial) rules:

  • It eats exactly once a day.
  • If it ate cheese yesterday, it will eat lettuce or grapes today with equal probability for each, and zero chance of eating cheese.
  • If it ate grapes yesterday, it will eat grapes today with probability 1/10, cheese with probability 4/10 and lettuce with probability 5/10.
  • Finally, if it ate lettuce yesterday, it won't eat it again today, but will eat grapes with probability 4/10 or cheese with probability 6/10.

This creature's eating habits can be modeled with a Markov chain since its choice depends on what it ate yesterday, not additionally on what it ate 2 or 3 (or 4, etc...) days ago. One statistical property one could calculate is the expected percentage of the time the creature will eat cheese over a long period.