Markov Chains Explained with Examples

Will it rain tomorrow? Which website will a user click next? Which brand will a shopper buy next month? Markov chains answer questions like these by modelling systems that jump randomly between states, where the next step depends only on where you are now. They are one of the most useful tools in probability, powering everything from Google's original search ranking to speech recognition and genetics.

The Big Idea: Memorylessness

A Markov chain is a sequence of random states \( X_0, X_1, X_2, \ldots \) with the Markov property: the probability of the next state depends only on the current state, not on the full history.

$$ P(X_{n+1} = j \mid X_n = i, X_{n-1}, \ldots, X_0) = P(X_{n+1} = j \mid X_n = i) $$

In everyday language: "the future depends on the present, not on the past." A board game like Snakes and Ladders is a perfect example. Your next square depends on your current square and the dice, not on how you got there.

A Brief History

The idea is named after the Russian mathematician Andrey Markov (1856–1922) of St Petersburg, who introduced such chains in 1906. He wanted to show that the law of large numbers could hold even for dependent events. In 1913 he famously applied his method to the text of Alexander Pushkin's poem Eugene Onegin, analysing 20,000 letters to measure how often a vowel follows a vowel or a consonant. It was one of the first statistical studies of language.

Transition Matrices

For a chain with finitely many states, we collect the probabilities \( p_{ij} = P(\text{next} = j \mid \text{now} = i) \) into a transition matrix \( P \). Each row lists the probabilities of moving from one state, so every row must add up to 1.

If the current distribution of states is a row vector \( \mathbf{v}_0 \), then after one step

$$ \mathbf{v}_1 = \mathbf{v}_0 P, \qquad \text{and after } n \text{ steps}, \qquad \mathbf{v}_n = \mathbf{v}_0 P^n. $$

Worked Example 1: A Weather Model

Suppose in a certain city:

• If today is Sunny, tomorrow is Sunny with probability 0.8 and Rainy with probability 0.2.
• If today is Rainy, tomorrow is Sunny with probability 0.4 and Rainy with probability 0.6.

With states ordered (Sunny, Rainy):

$$ P = \begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix} $$

(a) Probability of rain in two days, given sun today

Step 1. Compute \( P^2 = P \times P \). Entry by entry:

• Sunny to Sunny: \( 0.8(0.8) + 0.2(0.4) = 0.64 + 0.08 = 0.72 \)
• Sunny to Rainy: \( 0.8(0.2) + 0.2(0.6) = 0.16 + 0.12 = 0.28 \)
• Rainy to Sunny: \( 0.4(0.8) + 0.6(0.4) = 0.32 + 0.24 = 0.56 \)
• Rainy to Rainy: \( 0.4(0.2) + 0.6(0.6) = 0.08 + 0.36 = 0.44 \)

$$ P^2 = \begin{pmatrix} 0.72 & 0.28 \\ 0.56 & 0.44 \end{pmatrix} $$

Step 2. Read the Sunny row, Rainy column: the probability is 0.28.

Step 3 (interpret). Notice this counts both routes: Sunny, Sunny, Rainy (\( 0.8 \times 0.2 = 0.16 \)) and Sunny, Rainy, Rainy (\( 0.2 \times 0.6 = 0.12 \)). Matrix multiplication adds up all the paths automatically.

(b) Three days ahead

Starting from \( \mathbf{v}_0 = (1, 0) \) (definitely sunny today):

$$ \mathbf{v}_2 = (0.72,\ 0.28) $$

$$ \mathbf{v}_3 = \mathbf{v}_2 P = (0.72 \times 0.8 + 0.28 \times 0.4,\ \ 0.72 \times 0.2 + 0.28 \times 0.6) = (0.688,\ 0.312) $$

(c) The long-run proportion of sunny days

A stationary distribution \( \boldsymbol{\pi} = (\pi_S, \pi_R) \) satisfies \( \boldsymbol{\pi} P = \boldsymbol{\pi} \) and \( \pi_S + \pi_R = 1 \).

Step 1. The first column of \( \boldsymbol{\pi} P = \boldsymbol{\pi} \) gives

$$ 0.8\pi_S + 0.4\pi_R = \pi_S \quad\Rightarrow\quad 0.4\pi_R = 0.2\pi_S \quad\Rightarrow\quad \pi_S = 2\pi_R $$

Step 2. Substitute into \( \pi_S + \pi_R = 1 \): \( 3\pi_R = 1 \), so \( \pi_R = \tfrac{1}{3} \) and \( \pi_S = \tfrac{2}{3} \).

Step 3 (check). Look at the sequence 1, 0.8, 0.72, 0.688: the probability of sun is falling towards \( 0.667 \). In the long run, about two-thirds of days are sunny, whatever the weather today.

Worked Example 2: Brand Switching in a Market

Three mobile networks, A, B and C, compete. Each month customers switch according to

$$ Q = \begin{pmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.3 & 0.5 \end{pmatrix} $$

(row A says 70% of A's customers stay, 20% move to B and 10% to C).

(a) Next month's market shares

Current shares are \( (0.5, 0.3, 0.2) \).

• A: \( 0.5(0.7) + 0.3(0.3) + 0.2(0.2) = 0.35 + 0.09 + 0.04 = 0.48 \)
• B: \( 0.5(0.2) + 0.3(0.5) + 0.2(0.3) = 0.10 + 0.15 + 0.06 = 0.31 \)
• C: \( 0.5(0.1) + 0.3(0.2) + 0.2(0.5) = 0.05 + 0.06 + 0.10 = 0.21 \)

The shares sum to \( 1.00 \), a good check.

(b) Long-run market shares

Step 1. Write \( \boldsymbol{\pi} Q = \boldsymbol{\pi} \) as equations:

$$ \pi_A = 0.7\pi_A + 0.3\pi_B + 0.2\pi_C $$

$$ \pi_B = 0.2\pi_A + 0.5\pi_B + 0.3\pi_C $$

Step 2. Rearrange: \( 0.3\pi_A = 0.3\pi_B + 0.2\pi_C \) and \( 0.5\pi_B = 0.2\pi_A + 0.3\pi_C \).

Step 3. From the first, \( \pi_A = \pi_B + \tfrac{2}{3}\pi_C \). Substitute into the second:

$$ 0.5\pi_B = 0.2\pi_B + \tfrac{0.4}{3}\pi_C + 0.3\pi_C \quad\Rightarrow\quad 0.3\pi_B = \tfrac{1.3}{3}\pi_C \quad\Rightarrow\quad \pi_B = \tfrac{13}{9}\pi_C $$

Step 4. Then \( \pi_A = \tfrac{13}{9}\pi_C + \tfrac{6}{9}\pi_C = \tfrac{19}{9}\pi_C \).

Step 5. Use \( \pi_A + \pi_B + \pi_C = 1 \): \( \tfrac{19 + 13 + 9}{9}\pi_C = 1 \), so \( \pi_C = \tfrac{9}{41} \).

$$ \boldsymbol{\pi} = \left(\tfrac{19}{41},\ \tfrac{13}{41},\ \tfrac{9}{41}\right) \approx (0.463,\ 0.317,\ 0.220) $$

Step 6 (check). \( 0.7(19) + 0.3(13) + 0.2(9) = 13.3 + 3.9 + 1.8 = 19 \). Network A settles at about 46% of the market.

Tips for Solving Exam Problems

• Check the rows first. If a row of your transition matrix does not add up to 1, there is an error in the setup.
• Be consistent about rows and columns. In this article rows are "from" and columns are "to", and distributions are row vectors multiplied on the left. Some textbooks use the transposed convention, so read the question carefully.
• Replace one equation. The equations from \( \boldsymbol{\pi} P = \boldsymbol{\pi} \) are always dependent, so drop one of them and use \( \sum \pi_i = 1 \) instead.
• Sanity-check with powers. Rows of \( P^n \) for large \( n \) should approach the stationary distribution in a well-behaved chain.

Where Markov Chains Are Used

• Web search. Google's original PageRank (1998) modelled a "random surfer" clicking links; a page's rank is its stationary probability.
• Text prediction. Phone keyboards and early language models predict the next word from the current one.
• Finance. Credit-rating agencies use transition matrices to model bonds moving between ratings.
• Genetics and queues. DNA sequence analysis, hospital waiting lines and call centres are all modelled with Markov chains.
• MCMC. Markov Chain Monte Carlo methods let statisticians sample from complicated distributions.

Did You Know?

• Not every chain settles down: a chain that alternates strictly between two states never reaches a steady distribution in the usual sense.
• An absorbing state is one you can never leave, such as "game over" in gambling problems.
• Claude Shannon used Markov chains of letters and words in his 1948 paper founding information theory.

Key Takeaways

• A Markov chain moves between states where the next state depends only on the current one.
• The transition matrix \( P \) has rows summing to 1, and \( \mathbf{v}_n = \mathbf{v}_0 P^n \) gives the distribution after \( n \) steps.
• The stationary distribution solves \( \boldsymbol{\pi} P = \boldsymbol{\pi} \) with entries summing to 1.
• Andrey Markov introduced the idea in 1906 and applied it to Pushkin's poetry in 1913.
• Applications range from PageRank and finance to genetics and machine learning.

Need help with probability, matrices or stochastic processes? Amathify's experts and PhD scholars provide step-by-step solutions and assignment help, just WhatsApp us or use the Ask a Question form.