Introduction to Markov Chains
Markov Chain is a stochastic process where the probability of transitioning from the current state to the next state is only dependent on the current state.
Let us consider a stochastic process X_n, where n = 0, 1, 2,….. can take a finite number of possible values (known as states), usually denoted by a set of non-negative integers (i.e., 0, 1, 2…k). At any time n, if X_n = i, the process is said to be in state i. In the next time instance (n+1), the process can transition from state i to another state j. Note that the process may continue to remain in state i at time (n+1) as well, in which case we say that the transition happened from state i to state i.
Let P_ij denote the probability of the process transitioning from state i to state j. P_ij is called the transition probability. We assume that when the process is in state i, this probability P_ij is fixed and its value is only dependent on the current state i and not on any previous state. Mathematically, this means the following.
P[X_(n+1) = j|X_n = i, X_(n-1) = i_(n-1), … X_0 = i_0] = P[X_(n+1) = j|X_n = i]
where i_(n-1), i_(n-2)….. i_0 are the states the process is in at times (n-1), (n-2), …… 0.
Figure 1 above represents a simple 3-state Markov Chain (denoted by states 1, 2 and 3). Let M denote the transition matrix of the Markov chain. For example, in this transition matrix, P₁₁ = 0.5, which means that the probability of staying in state 1 in the next time step (or transitioning from state 1 to state 1) is 0.5. Similarly, P₂₁ = 0.1 ,which means that the probability of transitioning from state 2 to state 1 in the next time step is 0.1. Note that the probabilities in each row add up to 1 because the process has to transition from one state to some other state including itself.
Modeling the Weather of a City
Figure 1 could be used to model the weather in a city (Sunny, Cloudy or Rainy) where Sunny, Cloudy and Rainy correspond to states 1, 2 and 3 respectively. The transition probabilities capture the probability of transitioning from one state (e.g., Cloudy) to another state (e.g., Rainy). Note that by modeling the weather in this manner, we assume that the weather in the next day is only dependent on the current day.
Let us assume that today (i.e., Monday), you want use the Markov Model to determine the weather on Thursday. You know that the weather today is Cloudy. We use this knowledge and encode today’s weather in the form of a vector I = [0, 1, 0]. We then multiply I with M (i.e., I*M) to find the distribution of the weather tomorrow (i.e., Tuesday) given that it is Cloudy today. By multiplying with the transition matrix M thrice (I*M³), we will be able to obtain the distribution of what the weather is likely to be on Thursday.
Steady State Distribution
Based on the above discussion, a natural question that arises is — what if we want to determine the probability distribution of the weather 1 month (30 days) or 1 year (365 days) in advance? To obtain these distributions, we will have first obtain M³⁰ and M³⁶⁵, respectively. When we perform this multiplication, we observe that all rows of the transition matrix M of the Markov Chain have the same probabilities, specifically [0.294, 0.324, 0.382]. It means that after a large number of transitions the probability of being in a particular state j is independent of the initial state I and is a constant. This is referred to as the steady state distribution.
For our weather model, this result matches with our intuition because the weather on a particular day 1 year later is not dependent on today’s weather and our assessment will only be dependent on the limiting probabilities (i.e., the steady state distribution).