Blog

Summary

Magazine article on the origin of Markov Chains.

Notes

  • Invented by the Russian mathematician A. A. Markov, in 1913. Different from previous probability studies of independent events such as dice rolling, Markov studied chains of events. If is also raining today, the chances of raining tomorrow are higher.
  • A diagram, made of arrows and dots, describes a Markov chain. Dots represent states, arrows indicate transitions. Each transition has an associated probability, and all transitions originating from a state must to 1, or 100%.
  • To find out if it will rain tomorrow, one can use the diagram to check the probability of transition between today's weather and rain. Probability of rain in two days given that today's sunny can also be calculated. Sum all the transitions, starting with today's weather, going to any weather tomorrow, and ending with rain. For this type of calculation, it's much easier to use the matrix representation of the chain.
  • Multiplying the matrix by itself (PxP) gives the probability of each state in two days, given today's state. If someone does this multiple times, it converges to give the weather in any day.
  • Markov analyzed Russian poems to understand the probability of consonants and vowels, given previous letters.
  • In a k-th order Markov chain, the states are sequences of k characters and transitions are characters following these sequences.

Thoughts

  • Simple explanation of the topic with lots of history around it.