Markov Chains (DP IB Applications & Interpretation (AI)): Revision Note

Markov chains

What is meant by a “state”?

• States refer to mutually exclusive events with the current event able to change over time

• Examples of states include:

  • Daily weather conditions

    • The states could be: “sunny” and “not sunny”

  • Countries visited by an inspector each day

    • The states could be: “France”, “Spain” and “Germany”

  • Store chosen for weekly grocery shop:

    • The states could be: “Foods-U-Like”, “Smiley Shoppers” and “Better Buys”

What is a Markov chain?

• A Markov chain is a model that describes a sequence of states over a period of time

  • Time is measured in discrete steps

    • Such as days, months, years, etc

• The conditions for a Markov chain are:

  • The probability of a state being the next state in the sequence only depends on the current state

    • For example
      The 11^th state only depends on the 10^th state
      The first 9 states do not affect the 11^th state

    • This probability is called a transition probability

  • The transition probabilities do not change over time

    • For example
      The probability that the 11^th state is A given that the 10^th state is B is equal to the probability that the 12^th state is A given that the 11^th state is B

• A Markov chain is said to be regular if there is a value k such that in exactly k steps it is possible to reach any state regardless of the initial state

  • The chain where A can only go to B, B can only go to C and C can only go to A, is not regular

    • After any particular number of changes, A can only go either to B or C, or back to A

      • It can't go to any one of those three states for the same value of k

    • After 100 changes, A can end up at B but not at C or A

    • After 500 changes, A can end up at C but not at B or A

    • After 900 changes, A can only end up back at A

What is a transition state diagram?

• A transition diagram is a directed graph

  • The vertices are the states

  • The edges represent the transition probabilities between the states

• The graph can contain

  • Loops

    • These will be the transition probabilities of the next state being the same as the current state

  • Two edges between each pair of vertices

    • The edges will be in opposite directions

    • Each edge will show the transition probability of the state changing in the given direction

• The probabilities on the edges coming out of a vertex add up to 1