Linear Algebra › Section D · Vector spaces › Topic D.9

Markov chains

A Markov chain follows a system that moves at random between states, where only the present state affects the next step. Its long-run behaviour is found by solving one homogeneous linear system.

Random moves, linear algebra

Customers switch brands, web surfers click from page to page, and the weather changes from day to day. In each case the system is in one of a few states, and at each step it moves to another state, or stays put, with fixed probabilities that depend only on where it is now. A model of this kind is a Markov chain, named after the Russian mathematician Andrey Markov, who studied such chains in the early 1900s. Although the moves are random, the probabilities of being in each state change by matrix multiplication, so the tools of this section apply directly.

Probability vectors and stochastic matrices

A probability vector is a vector with non-negative entries that add up to 1, such as \((0.4, 0.6)\). Entry \(i\) is the probability of being in state \(i\). A stochastic matrix is a square matrix whose columns are all probability vectors. In a Markov chain, entry \(p_{ij}\) is the probability of moving to state \(i\) at the next step, given that the system is in state \(j\) now. So column \(j\) lists where state \(j\) can go, and it must add up to 1. Many statistics and probability books write the transpose instead, with rows that add up to 1; the ideas are the same.

The chain as a recurrence

A Markov chain is a sequence of probability vectors \(\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \ldots\) together with a stochastic matrix \(P\) such that

\mathbf{x}_{k+1} = P\mathbf{x}_k \quad \text{for } k = 0, 1, 2, \ldots

The vector \(\mathbf{x}_k\) is the state vector at step \(k\). The equation says that the probability of being in state \(i\) next is the sum, over every current state \(j\), of the probability of being in \(j\) times the probability of moving from \(j\) to \(i\). It is a first-order recurrence like those in "Difference equations", and it gives \(\mathbf{x}_k = P^k\mathbf{x}_0\). Each \(\mathbf{x}_k\) is again a probability vector.

Worked example: two coffee shops

In a model town with two coffee shops, A and B, 80% of A's customers return to A the next week and 20% switch to B, while 70% of B's customers stay and 30% switch to A. This week 40% of customers use A. 1. Put each shop's outcomes in its column:

P = \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix}, \qquad \mathbf{x}_0 = \begin{bmatrix} 0.4 \\ 0.6 \end{bmatrix}

2. Next week:

\mathbf{x}_1 = P\mathbf{x}_0 = (0.32 + 0.18, \; 0.08 + 0.42) = (0.5, 0.5)

3. The week after:

\mathbf{x}_2 = P\mathbf{x}_1 = (0.4 + 0.15, \; 0.1 + 0.35) = (0.55, 0.45)

4. Each state vector adds up to 1, as it must. A's share is rising, though more slowly each week.

Steady-state vectors

If the chain settles down, it settles at a probability vector \(\mathbf{q}\) that the matrix leaves unchanged:

P\mathbf{q} = \mathbf{q}

Such a \(\mathbf{q}\) is called a steady-state vector, or equilibrium vector. Rewriting the equation as \((P - I)\mathbf{q} = \mathbf{0}\) shows that steady states lie in \(\operatorname{Nul}(P - I)\). That null space is never just \(\{\mathbf{0}\}\): the columns of \(P\) add up to 1, so the columns of \(P - I\) add up to 0, which means the rows of \(P - I\) add up to the zero row. Dependent rows make \(P - I\) singular. In fact every stochastic matrix has at least one steady-state vector.

Worked example: the coffee shops in the long run

Find the steady state for the coffee-shop matrix. 1. \(P - I\) has rows \((-0.2, 0.3)\) and \((0.2, -0.3)\). The second row is the negative of the first, as the last card predicted. 2. So \((P - I)\mathbf{q} = \mathbf{0}\) reduces to \(-0.2q_1 + 0.3q_2 = 0\), giving \(q_1 = 1.5q_2\). 3. A probability vector also needs \(q_1 + q_2 = 1\), so \(2.5q_2 = 1\), \(q_2 = 0.4\) and \(q_1 = 0.6\). 4. Check:

P\mathbf{q} = (0.48 + 0.12, \; 0.12 + 0.28) = (0.6, 0.4)

In the long run, A has 60% of customers. The weekly figures 40%, 50%, 55% were heading towards it; after 10 weeks A's share is already about 59.98%.

Regular matrices and convergence

A stochastic matrix \(P\) is regular if some power \(P^k\) has every entry strictly positive. The coffee-shop matrix is regular already at \(k = 1\). The key theorem: if \(P\) is a regular stochastic matrix, then \(P\) has a unique steady-state vector \(\mathbf{q}\), and for any initial probability vector \(\mathbf{x}_0\), the state vectors \(\mathbf{x}_k = P^k\mathbf{x}_0\) converge to \(\mathbf{q}\). So the long run does not depend on the starting point at all. A regular chain forgets where it began, and \(\mathbf{q}\) gives the long-run fraction of time spent in each state.

Worked example: three weather states

A simplified weather model has states sunny, cloudy and rainy, in that order. Its columns are sunny \((0.5, 0.3, 0.2)\), cloudy \((0.2, 0.6, 0.2)\) and rainy \((0.1, 0.3, 0.6)\). 1. Each column adds up to 1, and every entry is positive, so \(P\) is regular. 2. Row reduce \(P - I\), whose rows are \((-0.5, 0.2, 0.1)\), \((0.3, -0.4, 0.3)\) and \((0.2, 0.2, -0.4)\). The reduced form gives \(q_1 = \frac{5}{7}q_3\) and \(q_2 = \frac{9}{7}q_3\). 3. Take \(q_3 = 7\) to get \((5, 9, 7)\), then divide by the sum 21. 4. So \(\mathbf{q} = (\frac{5}{21}, \frac{9}{21}, \frac{7}{21})\), about \((0.238, 0.429, 0.333)\): in the long run about 43% of days are cloudy. 5. Check the first entry: \(0.5 \cdot 5 + 0.2 \cdot 9 + 0.1 \cdot 7 = 5\).

When there is no convergence

Regularity matters. The matrix with rows \((0, 1)\) and \((1, 0)\) is stochastic: it moves state 1 to state 2 and back every step. Its steady state is \((0.5, 0.5)\), but starting from \((1, 0)\) the chain alternates \((1, 0), (0, 1), (1, 0), \ldots\) forever and never converges. Every power of this matrix still contains zeros, so it is not regular. Markov chains appear widely: the original PageRank method behind Google's search ranking, developed in the late 1990s, modelled a surfer clicking randomly between pages and ranked pages by the steady-state vector. Genetics, queues and credit ratings use them too.

Common mistakes to avoid

Putting the probabilities in rows instead of columns is the commonest slip; with \(\mathbf{x}_{k+1} = P\mathbf{x}_k\), each column must add up to 1. Stopping at a non-zero solution of \((P - I)\mathbf{q} = \mathbf{0}\) without scaling it so its entries add up to 1 gives a vector that is not a probability vector. Solving \(P\mathbf{q} = \mathbf{0}\) instead of \((P - I)\mathbf{q} = \mathbf{0}\) is another. And a steady state existing does not mean the chain reaches it; convergence from every start is guaranteed only for regular matrices.

Key takeaways

A probability vector has non-negative entries adding up to 1, and a stochastic matrix has probability vectors as columns, with \(p_{ij}\) the chance of moving from state \(j\) to state \(i\). A Markov chain follows \(\mathbf{x}_{k+1} = P\mathbf{x}_k\), so \(\mathbf{x}_k = P^k\mathbf{x}_0\). A steady state satisfies \(P\mathbf{q} = \mathbf{q}\): solve \((P - I)\mathbf{q} = \mathbf{0}\) and scale the solution to add up to 1. If some power of \(P\) is strictly positive, \(P\) is regular, the steady state is unique, and every chain converges to it.

Flashcards

Flashcard

Probability vector

Non-negative entries that add up to 1

Entry i is the chance of state i.

Test your understanding

Question 1 of 5

Which matrix is stochastic in the column convention used here?

Question 2 of 5

P has columns (0.9, 0.1) and (0.4, 0.6), and x₀ = (0.5, 0.5). What is x₁?

Question 3 of 5

What is the steady-state vector of the stochastic matrix with columns (0.9, 0.1) and (0.4, 0.6)?

Question 4 of 5

What does it mean for a stochastic matrix P to be regular?

Question 5 of 5

Why does the chain with P = swap matrix, columns (0, 1) and (1, 0), fail to converge from x₀ = (1, 0)?

← Previous topicNext topic →