Understanding Markov Chains: From Basics to Real-World Applications

1 Markov Chain Model

When studying dynamic systems affected by random factors, we often encounter situations where the system's state at each period is random, and the transition to the next state depends only on the current state and a transition probability, not on earlier states. This property is called the Markov property or memorylessness.

Markov chains, introduced by Andrey Markov, are used in economics, sociology, ecology, genetics, and even for deterministic systems' state transitions.

2 Definition of Random Process

A random experiment can have many possible outcomes, described by a random variable or vector. When observations are made repeatedly over time, we study a family of random variables, i.e., a random process, which investigates the probabilistic regularities of the evolving phenomenon.

Definition 1: Let {X_t} be a family of random variables indexed by a set T of real numbers. If for any real t, X_t is a random variable, then {X_t} is called a random process.

The index set T is called the parameter set and can be interpreted as time. Each possible value of the parameter is a state of the random process. The collection of all possible states forms the state space S. When T is the set of non‑negative integers, the random process is also called a random sequence.

Markov chains are a special type of random sequence.

3 Definition of Markov Chain

In many real‑world phenomena, the future state depends only on the present state and not on the past. Such a stochastic model is called a Markov model.

Definition 1: Let {X_n} be a random sequence with a finite or countable state space S. For any positive integer n, if P(X_{n+1}=j \| X_n=i) = p_{ij}, then {X_n} is a Markov chain, and the relation above is the Markov property.

Here p_{ij} denotes the conditional probability of moving from state i to state j.

Markov Chain Example

In a camera‑rental business with several stores, each day a camera is located at one store. The sequence of store locations forms a random sequence with the set of stores as the state space.

The camera’s location tomorrow is completely determined by today’s location; its past history is irrelevant, illustrating the memoryless property of a Markov chain.

4 Transition Probability Matrix

For a Markov chain, the one‑step transition matrix P = [p_{ij}] has two basic properties: (i) each entry p_{ij} ≥ 0; (ii) each row sums to 1.

When a problem can be modeled by a Markov chain, we first determine its state space and then its one‑step transition probabilities, which can be derived from the problem’s intrinsic rules, past experience, or estimated from observed data.

Example of Estimating Transition Probabilities

Given the observed sequence: 4 3 2 1 4 3 1 1 2 3 2 1 2 3 4 4 3 3 1 1 1 3 3 2 1 2 2 2 4 4 2 3 2 3 1 1 2 4 3 1 Estimate the transition probabilities.

The total counts of each transition are obtained from the data, and the estimated probabilities are computed as the ratio of each transition count to the total outgoing count from the originating state.

5 Kolmogorov Theorem

Let P be a Markov chain transition matrix (each row is a probability vector) and π^{(0)} the initial distribution row vector. After n steps, the distribution is π^{(n)} = π^{(0)} P^{n}.

Kolmogorov Theorem Example

If a customer’s purchase behavior is memoryless, and there are three brands of seasoning packets, the purchase process forms a Markov chain. Given the initial purchase probabilities (0.2, 0.4, 0.4) and a transition matrix (shown in the figure), compute the probabilities of the fourth purchase.

By multiplying the initial distribution by the transition matrix three times, we obtain the fourth‑step distribution.

6 Asymptotic Behavior of Transition Probabilities – Limiting Distribution

We examine whether the distribution converges to a fixed vector as the number of steps grows. For a simple example with a given transition matrix, the limiting distribution is the eigenvector associated with eigenvalue 1, also called the stationary distribution. Regular matrices guarantee the existence of such a stationary vector.

Using the transition matrix from the previous example, solving the system π = πP yields the limiting probabilities, showing that regardless of the initial purchase, the market share stabilizes among the brands.

7 Absorbing Chains

An absorbing Markov chain contains at least one absorbing state that, once entered, cannot be left. If every non‑absorbing state can reach an absorbing state, the chain is absorbing.

For a transition matrix whose last row is [0 0 0 1], state 4 is absorbing.

References

ThomsonRen GitHub https://github.com/ThomsonRen/mathmodels