Markov Chains are a commonly applied mathematical tool that helps predict future events based on current evidence. They are used in domains as diverse as forecasting the weather or determining the importance of web pages displayed as results in Google’s search engine. This post demystifies how Markov Chains work and explores its main applications, showcasing their practical uses with some small code-based examples in Python.

What is a Markov Chain?

A Markov Chain is a mathematical model of probabilistic nature, with the following basic elements:

• A set of states, for instance: sunny, cloudy, rainy, etc., for weather status
• Transitions between states, quantifying the likelihood of moving from one state to another

Basic Markov chains are memory-less, meaning that only information about the current state is considered to make decisions.

A simplified Markov chain for weather prediction with three states and likelihood transitions between them

Markov Chains in Everyday Life

Markov Chains are often used in relatable domains like weather forecasting. Here’s how forecasts like “sunny,” “cloudy,” and “rainy,” along with the transitions between them are modeled. Suppose the scenario of predicting tomorrow’s weather based on today’s conditions. If today is sunny, a Markov Chain like the one depicted above can estimate the chances of tomorrow being sunny, cloudy, or rainy using transition probabilities derived from historical data.

Probabilities indicate the likelihood of transitioning from one weather state to another, reflecting the natural patterns observed over time. Historical observations are normally used to estimate these likelihoods. For example, a sunny day might have very highly likely to stay sunny, moderate chances of becoming cloudy, and lower chances of becoming rainy. In essence, a sequence of states and transitions are the foundations of the Markov Chain, allowing for probabilistic predictions that, through simplicity combined with accuracy, help meteorologists make informed forecasts.

Google also uses Markov chains in the algorithm behind their search engine: PageRank. In this case, the Markov chain has a much larger dimensionality. The web is modeled as a graph where each webpage is a state, and links between pages represent transitions. Likelihoods in transitions are determined by the number and quality of links pointing to each page, reflecting the probability that a user who randomly clicks links will land on a particular page. This is how the PageRank algorithm leverages the Markov Chain to rank webpages by importance, prioritizing pages with more valuable inbound links, which ultimately helps provide more relevant search results to users.

Markov Chains Implementation in Python

To wrap up this introduction to Markov chains, we illustrate how to define a simple chain in Python.

The following code defines a Markov chain based on a transition matrix, where rows represent current states, and columns represent the next states concerning the current one. Thus, we have a square matrix with a size equal to the number of states. For a simple scenario with two possible states (sunny and rainy), we have:

import numpy as np

# Transition matrix with probabilities of transitioning between weather states: [Sunny, Rainy]
# Example: 0.7 means 70% chance of staying Sunny, 0.3 means 30% chance of turning rainy
transition_matrix = np.array([
    [0.7, 0.3],  # Probabilities from Sunny: [Stay Sunny, Become Rainy]
    [0.4, 0.6]   # Probabilities from Rainy: [Become Sunny, Stay Rainy]
])

# Initial state: Starting with Sunny (1 represents Sunny, 0 represents Rainy)
initial_state = np.array([1, 0])  # [Sunny, Rainy]

# Calculate the next state probabilities to predict tomorrow weather
next_day_probabilities = initial_state @ transition_matrix

# Display the probabilities
print(f"Probability of being Sunny tomorrow: {next_day_probabilities[0]:.2f}")
print(f"Probability of being Rainy tomorrow: {next_day_probabilities[1]:.2f}")

Note the ‘@’ operator is used for matrix multiplication, namely multiplying the initial state array by the transition matrix to obtain the next state probabilities.

Wrappoing Up

Markov chains are an intuitive but commonly used likelihood tool in applications where there exist states and transitions between them that can be modeled probabilistically. This article introduced and demystified Markov chains, describing two of their salient applications in weather forecasting and web search, and briefly outlining their use in Python code.