Markov Chains: Mathematical Formulation, Intuitive Explanation & Applications

Markov chains are one of the most powerful and widely used mathematical tools in the fields of artificial intelligence, machine learning, and data science. They provide a principled way to model and reason about systems that evolve over time according to probabilistic rules. Markov chains have found applications in domains as diverse as natural language processing, computer vision, recommender systems, robotics, computational biology, and quantitative finance.

In this post, we‘ll take a deep dive into the mathematical foundations of Markov chains, starting from the formal definitions and then building up an intuitive understanding through visualizations and examples. We‘ll cover several key properties and theorems about Markov chains that are essential for analyzing their long-term behavior. Finally, we‘ll survey some of the most important and exciting applications of Markov chains in AI and machine learning.

Mathematical Formulation

Before we can properly define a Markov chain, we need to introduce a few mathematical concepts. The first is the notion of a stochastic process, which is a collection of random variables {X_t} indexed by time t. In other words, a stochastic process is a system where the state at each point in time is a random variable.

A Markov process is a stochastic process that satisfies the Markov property, which states that the probability distribution of the future states depends only on the current state, and not on the past states. Formally, for any sequence of times t₁ < t₂ < … < t_n and any sequence of states x₁, x₂, …, x_n, a Markov process satisfies:

P(X_tn = x_n | X_tn-1 = x_n-1, …, X_t1 = x₁) = P(X_tn = x_n | X_tn-1 = x_n-1)

In plain English, this means that to predict the next state of the system, all you need to know is the current state – the history of past states provides no additional information.

A Markov chain is a type of Markov process where the state space (the set of possible values for X_t) is discrete. The dynamics of the system are determined by transition probabilities between states. We can package up all the transition probabilities into a matrix P, where the entry P_ij represents the probability of moving from state i to state j in one time step:

P_ij = P(X_t+1 = j | X_t = i)

The transition matrix P satisfies the following properties:

1. 0 ≤ P_ij ≤ 1 for all i,j (all entries are valid probabilities)
2. ∑_j P_ij = 1 for all i (transition probabilities out of each state sum to 1)

To fully specify a Markov chain, we also need to provide an initial state distribution π, which gives the probabilities of the system starting in each state. The vector π satisfies:

1. 0 ≤ π_i ≤ 1 for all i
2. ∑_i π_i = 1

Example: Weather Model

Let‘s make these abstract definitions concrete with an example. Suppose we want to model the day-to-day weather in a particular location as a Markov chain. We‘ll use three states: Sunny (S), Cloudy (C), and Rainy (R).

The transition probabilities between weather states might look like this:

	S	C	R
S	0.7	0.2	0.1
C	0.4	0.4	0.2
R	0.3	0.5	0.2

In this model, if today is sunny, there‘s a 70% chance that tomorrow will also be sunny, a 20% chance it will be cloudy, and a 10% chance it will rain. The probabilities in each row sum to 1.

Let‘s also assume that the weather on the first day of our model is equally likely to be sunny, cloudy or rainy. So our initial state distribution is:

π = [1/3, 1/3, 1/3]

With the states, transition matrix P, and initial distribution π, we have completely specified a Markov chain model for the weather. Now let‘s see what we can do with it!

Long-term Behavior and Stationary Distributions

One of the key things we want to understand about any Markov chain model is its long-term behavior. Suppose we run the Markov chain for a very long time – where will it spend most of its time? What proportion of the time will it spend in each state?

It turns out that under certain conditions on the transition matrix P, the state distribution of the Markov chain will converge to a stationary distribution π^* as the number of steps t goes to infinity, regardless of the initial state distribution π.

The stationary distribution π^* is defined as a vector that satisfies:

π P = π

In other words, the stationary distribution is an eigenvector of the transition matrix P with eigenvalue 1. Once the Markov chain reaches its stationary distribution, the state probabilities no longer change over time.

Not all Markov chains have a unique stationary distribution, but most well-behaved ones do. Specifically, if the Markov chain is irreducible (it‘s possible to get from any state to any other state in a finite number of steps) and aperiodic (the gcd of return times to any state is 1), then the Perron-Frobenius theorem guarantees that a unique stationary distribution exists.

For our weather model example, we can calculate the stationary distribution by solving the matrix equation π P = π using standard linear algebra techniques. Doing so gives:

π^* ≈ [0.526, 0.333, 0.141]

So in the long run, the weather will be sunny about 52.6% of the time, cloudy 33.3% of the time, and rainy 14.1% of the time, on average.

Hitting Times and Absorption

Another important property of Markov chains is the hitting time between states – the expected number of steps it takes to go from state i to state j for the first time. We can calculate hitting times using the following system of linear equations:

h_ij = 1 + ∑_k≠j P_ik h_kj

where h_ij is the hitting time from state i to state j. The intuition is that to get from i to j, we have to first take one step to some intermediate state k (which takes 1 unit of time), and then go from k to j, which takes on average h_kj more steps.

Some Markov chains have special states called absorbing states that, once entered, cannot be left. A classic example is the Gambler‘s Ruin problem, where a gambler repeatedly plays a game with some probability p of winning \$1 and probability q=1-p of losing \$1. The gambler stops playing if their balance hits \$0 (they go broke) or reaches some target amount \$N. The states 0 and N are absorbing states.

We can set up a Markov chain for the Gambler‘s Ruin problem, with states {0, 1, 2, …, N} representing the gambler‘s balance in dollars. The transition probabilities are:

P_i,i+1 = p for 0 < i < N (probability of winning \$1)
P_i,i-1 = q for 0 < i < N (probability of losing \$1)
P₀₀ = P_NN = 1 (absorption at 0 and N)

Using hitting times, we can calculate the probability that the gambler reaches the target balance \$N before going broke, as a function of the initial balance i and the game probabilities p and q. This is a fun and instructive example to work through!

Discrete vs Continuous Time

So far we‘ve been talking about discrete-time Markov chains, where the state transitions happen at regular clock ticks. But there is also a continuous-time analogue, aptly named continuous-time Markov chains (CTMCs).

In a CTMC, the system spends a random amount of time in each state before transitioning, rather than taking transitions at fixed time steps. The transition rates between states are specified by a rate matrix Q, where the entry q_ij represents the instantaneous rate of going from state i to state j.

CTMCs are often used to model things like chemical reaction networks, queueing systems, and population processes. The added flexibility of allowing arbitrary transition times can make CTMCs more realistic models for many applications.

Another important extension of Markov chains are Markov decision processes (MDPs), which add a notion of agency and optimization. In an MDP, the system transitions between states like a Markov chain, but there is also a decision maker who can choose an action at each state. The actions influence the transition probabilities and also provide rewards to the decision maker.

The goal in an MDP is to find a policy – a mapping from states to actions – that maximizes the expected total reward over some time horizon. MDPs are a foundation of reinforcement learning, a branch of machine learning where agents learn to make good decisions by interacting with an environment.

Applications in AI and ML

Markov chains and their extensions are workhorses of artificial intelligence and machine learning. Let‘s survey some of their most important applications.

Hidden Markov Models for Sequence Modeling

One of the most widely used Markov chain variants are Hidden Markov Models (HMMs). In an HMM, the states of the Markov chain are not directly observed; instead, each state emits an observable symbol according to some probability distribution. The goal is to infer the most likely sequence of hidden states given the observed data.

HMMs have been used for decades in speech recognition, where the hidden states represent phonemes or words and the observations are acoustic signals. More recently, HMMs have been applied to many other sequence modeling tasks in NLP, such as part-of-speech tagging, named entity recognition, and information extraction.

The workhorse algorithms for HMMs are the forward-backward algorithm for computing posterior state probabilities, the Viterbi algorithm for finding the most likely state path, and the Baum-Welch algorithm for learning the HMM parameters from data.

Markov Chain Monte Carlo for Bayesian Inference

Another major application of Markov chains in AI/ML is in Markov Chain Monte Carlo (MCMC) methods for Bayesian inference and learning. The basic idea of MCMC is to construct a Markov chain whose stationary distribution is the posterior distribution over parameters or latent variables that we want to infer.

By running the Markov chain for a long time, we can generate samples from the posterior distribution, which can then be used to approximate expectations, quantiles, and other summaries. Some popular MCMC algorithms are Metropolis-Hastings, Gibbs sampling, and Hamiltonian Monte Carlo.

MCMC has been a mainstay of Bayesian statistics and machine learning for decades, and underlies many state-of-the-art methods for probabilistic modeling, like Bayesian neural networks and Gaussian processes.

Markov Decision Processes and Reinforcement Learning

As mentioned earlier, Markov Decision Processes provide a principled framework for sequential decision making under uncertainty, and are the foundation of modern reinforcement learning. The goal in an MDP is to learn a policy that maximizes long-term cumulative reward.

There are two main families of algorithms for solving MDPs: value-based methods like Q-learning that estimate the expected future reward of each state or state-action pair, and policy-based methods that directly learn a parametrized policy function. In recent years, deep reinforcement learning methods that use neural networks for value or policy functions have achieved remarkable successes on complex tasks like playing video games, controlling robots, and optimizing chemical reactions.

Some of the core concepts in RL that relate to Markov chains are the Bellman equations that recursively define optimal value functions, the exploration-exploitation tradeoff, and the use of dynamic programming methods like value iteration and policy iteration.

Markov Random Fields and Graphical Models

Markov Random Fields (MRFs) are a generalization of Markov chains to higher-dimensional grid-like structures, and are commonly used in computer vision and image processing. The Markov property for MRFs says that each node is conditionally independent of all others given its immediate neighbors.

MRFs are a type of probabilistic graphical model, a powerful framework for representing and reasoning with high-dimensional probability distributions using graph structures. Another major type of graphical model are Bayesian Networks, which use directed acyclic graphs to represent conditional dependencies.

The key tasks in graphical models are inference (computing posterior probabilities of latent variables given observed evidence) and learning (estimating the graph structure and parameters from data). Some of the main algorithms are belief propagation, variational inference, and constraint-based and score-based structure learning.

Graphical models provide a unified language and toolkit for probabilistic reasoning, and have been successfully applied to a wide variety of problems in AI/ML, from natural language processing to computational biology to robot perception and control.

Conclusion

Markov chains are a simple yet exceptionally powerful tool for modeling and understanding systems that evolve probabilistically over time. The key properties of Markov chains – the memorylessness of state transitions, the convergence to stationary distributions, and the connections to linear algebra – make them both theoretically elegant and practically useful.

As we‘ve seen, Markov chains and their many extensions and generalizations – including Hidden Markov Models, Markov Decision Processes, and Markov Random Fields – are foundational ideas in artificial intelligence and machine learning. They provide a unified framework for reasoning about uncertainty, sequential data, and decision making that has been applied to a stunning variety of problems and domains.

While Markov chains are not a silver bullet, and there are certainly many situations where their assumptions don‘t hold, they remain an indispensable part of the toolkit for anyone working in AI/ML. There is still much to be discovered and invented at the intersection of Markov chains and machine learning – from scaling up MCMC and RL algorithms to massive datasets, to inventing new graphical model architectures and inference algorithms, to tackling ever more ambitious problems in science and technology with the tools of probabilistic modeling and reasoning.

I hope this post has given you a solid understanding of the key concepts and applications of Markov chains in AI/ML. The mathematical theory is elegant and insightful, but the best way to truly appreciate the power of Markov chains is to use them to solve real problems! I encourage you to try implementing some of the classic algorithms like PageRank, forward-backward, or policy iteration, and to think creatively about how Markov chains could be applied to problems you care about. Good luck, and have fun exploring the fascinating world of Markov chains!