The Markov Property

The Markov Property makes a very strong assumption that the output of a random variable in a sequence only depends on the current state. Consider a sequence of state variables q_1, q_2, \cdots, q_i. The Markov assumption states that

    \begin{equation*}P(q_i = a | q_1 q_2 \cdots q_{i-1}) = P(q_i = a | q_{i-1})\end{equation*}

A discrete-time process satisfying this property is called a Markov Chain and a continuous process is called a Markov process.

Markov Chain

A Markov Chain is defined by a state space and the probabilities of transitioning within this state space. Given n states there are n^2 possible transitions. This can be represented as a finite state machine with the symbols above the transition indicating the probability of that transition.

Consider the discrete process of predicting the weather for a given day. The set of values it can take include \{Sunny, Rainy\}. These correspond to the states. Each discrete quanta is one day.

Rendered by

The Markov assumption states that today’s weather depends only on yesterday’s weather. Assume that there is a high chance that today will be Sunny if yesterday was Sunny and a moderate chance that today will be Rainy if yesterday was Rainy. These values are added as probabilities. The outgoing probabilities of a state must add up to 1.

Rendered by

Using this Markov Chain, the weather can be predicted by following the transitions. A test run will result in the following output. S stands for Sunny and R stands for Rainy

    \begin{equation*}\cdots S \, S \, S \, S \, S \, R \, R \, S \, S \, S \, S \, S \, S \cdots\end{equation*}


The Markov property makes the model memoryless. The sequence of states generated are not context-sensitive and do not rely on the information captured in the full chain of prior states. For example, a Markov chain would do a poor job in mimicking the musical structure of a song. Higher order Markov chains use the assumption of the current state relying on multiple prior states.

Mathematical Representation

A Markov Chain can be mathematically represented as transition matrix. Given n possible states, the matrix will have dimensions n \times n, where each entry p_{ij} is the probability of transitioning from i to j. Also, by the law of total probability

    \begin{equation*}\sum_{j=0}^{n} p_{ij} = 1\end{equation*}

The Markov chain also has an initial state vector of dimensions n \times 1, where each entry p_j is the probability of starting at the j-th state.

Leave a Reply

Your email address will not be published. Required fields are marked *