Introduction and Context

Markov chains represent a fascinating intersection of probability and dynamic systems. They offer a framework for modeling processes where the future state depends solely on the current state—a concept known as the Markov property. This memoryless nature simplifies complex systems, making them valuable across diverse domains from weather forecasting to financial modeling and text generation.

Historical Development

The origins of Markov chains trace back to Andrei A. Markov, a Russian mathematician (1856-1922). His seminal work in 1906, “Rasprostranenie zakona bol’shih chisel na velichiny, zavisyaschie drug ot druga,” published in the Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, marked their formal introduction. This work extended probability theorems to sequences of dependent random variables—a significant advance beyond independent events. A 1971 reprint in R. Howard’s Dynamic Probabilistic Systems, volume 1: Markov Chains (Extension of the limit theorems of probability theory to a sum of variables connected in a chain) demonstrates its lasting importance. Markov first applied his theory to analyze letter sequences in Pushkin’s “Eugene Onegin,” as documented in a 2006 translation in Science in Context (An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains), showcasing an early application to literary analysis.

Definition and Core Concepts

Markov chains are Probabilistic Graphical Models (PGMs) that capture dynamic processes through state transitions over time. They are systems where the state at time $t+1$ depends only on the state at time $t$, independent of all prior states. Their formal definition includes:

  • A set of states, $Q = {q_1, q_2, \dots, q_n}$, representing possible conditions (e.g., Sunny, Cloudy, Rainy).
  • A vector of prior probabilities, $\Pi = {\pi_1, \pi_2, \dots, \pi_n}$, where $\pi_i = P(S_0 = q_i)$, indicating initial state likelihoods.
  • A transition matrix, $T = {p_{ij}}$, where $a_{ij} = P(S_t = q_j | S_{t-1} = q_i)$, capturing the probability of moving from state $i$ to state $j$.

This structure ensures the Markov property, $P(S_t = q_j | S_{t-1} = q_i, S_{t-2} = q_k, \dots) = P(S_t = q_j | S_{t-1} = q_i)$, emphasizing memorylessness. In the transition matrix, rows sum to 1 and entries range from 0 to 1. The state vector shows distribution at a point in time, with entries summing to 1. After $m$ transitions, the state vector evolves as $V_m = V_0T^m$, and some chains reach a steady-state, or equilibrium vector $E$, where $ET = E$.

Illustrative Example

Consider a weather model with states Sunny ($q_1$), Cloudy ($q_2$), and Rainy ($q_3$). The transition probabilities are:

  • From Sunny: 70% chance of staying Sunny, 20% Cloudy, 10% Rainy.
  • From Cloudy: 30% Sunny, 50% Cloudy, 20% Rainy.
  • From Rainy: 20% Sunny, 30% Cloudy, 50% Rainy.

This system is represented by a transition matrix $T$ and visualized through a state transition diagram, with nodes as states and arcs as transitions. Starting with an initial state vector—say, 100% Sunny—we can compute future distributions, demonstrating how the system evolves over discrete time steps while maintaining the Markov property.

    graph LR;
    A["Sunny"] --> |0.2| B["Cloudy"];
    A --> |0.7| A;
    A --> |0.1| C["Rainy"];
    B --> |0.3| A;
    B --> |0.5| B;
    B --> |0.2| C;
    C --> |0.2| A;
    C --> |0.3| B;
    C --> |0.5| C;

%% State transition probabilities for weather model
%% Self-loops show probability of staying in same state
%% Arrows between states show transition probabilities

The diagram above illustrates the state transitions and their associated probabilities for our weather model. Each node represents a state (Sunny, Cloudy, or Rainy), and the directed edges show the probability of transitioning from one state to another. Self-loops indicate the probability of remaining in the same state.