Markov Chains and Transition Matrices, introduction to probability lesson

A machine runs in one of two modes, A or B, and is inspected once an hour. If it is in mode A at this inspection, how likely is mode A at the next one, and would it help to know its mode at every earlier inspection? A Markov chain is a model in which the earlier modes add nothing once the current mode is known, although the next mode may still depend strongly on the current one. This lesson defines states and the Markov property, collects the one-step probabilities in a transition matrix, and shows how a starting distribution moves forward one step at a time.

Key terms

State

Definition A discrete-time random process $X_0, X_1, X_2, \dots$ describes a system at the steps $n = 0, 1, 2, \dots$ , and the random variable $X_n$ is its state at step $n$ . The state space $S$ is the set of possible states, which in this course is finite or countable. Choosing the states is part of building the model. A Markov chain, defined in the next card, is a sensible model only when the state at step $n$ records everything about the history up to step $n$ that affects the probabilities of the next state.

In plain words A state is the label the model gives the system at one step, such as a mode, a location or a category. The labels have to be detailed enough that two histories ending in the same state predict the next step in the same way.

Example The machine in the opening has state space $S = \{A, B\}$ , and $X_3 = B$ means that it runs in mode B at step $3$ . For a case where coarse labels fail, consider a constructed machine that is either ready or busy at each step. A ready machine starts a job at the next step with probability $0.5$ , whatever happened before. Every job lasts exactly two steps, after which the machine is ready again. A machine that is busy now and was ready one step earlier is busy at the next step with probability $1$ , while one that has been busy for two steps is ready at the next step with probability $1$ . So the two labels ready and busy do not say enough. Splitting busy into “first step of a job” and “second step of a job” gives three states whose next-step probabilities depend on the current state alone.

Markov chain

Definition A sequence $X_0, X_1, X_2, \dots$ of random variables with values in a finite or countable state space $S$ is a Markov chain if it has the Markov property. Take any $n \ge 0$ , any states $i$ and $j$ , and any event $H = \{X_0 = i_0, \dots, X_{n-1} = i_{n-1}\}$ that fixes the earlier states, where $H = \Omega$ when $n = 0$ . Whenever $P(X_n = i, H) > 0$ ,

\begin{aligned} &P(X_{n+1} = j \mid X_n = i, H) \\[0.4em] &= P(X_{n+1} = j \mid X_n = i). \end{aligned}

The positivity condition makes both conditional probabilities well defined.

In plain words Once the current state is known, the earlier states add nothing to the prediction of the next state. This is not independence. The next state can depend strongly on the current one, and through the current one on the past. The property only says that the past matters for the next step through the current state alone.

Example In a constructed model, the two-mode machine moves from A to A with probability $0.8$ and from A to B with probability $0.2$ , and from B to A with probability $0.3$ and from B to B with probability $0.7$ , whatever its earlier modes were. This is a Markov chain. If the machine is in A now, the chance of A next is $0.8$ whether it was in A or in B one step earlier. Yet consecutive modes are dependent whenever both modes have positive probability at the earlier step. If $P(X_0 = A) = 0.4$ and $P(X_0 = B) = 0.6$ , then

\begin{aligned} &P(X_1 = A) \\[0.4em] &\quad = 0.4 \cdot 0.8 + 0.6 \cdot 0.3 \\[0.4em] &\quad = 0.5, \end{aligned}

while $P(X_1 = A \mid X_0 = A) = 0.8$ . The ready and busy machine of the previous card is not a Markov chain with its two coarse states, but it is one with the three refined states.

Time-homogeneous chain

Definition A Markov chain is time-homogeneous if its one-step transition probabilities do not depend on the step number. That is, there are numbers $P_{ij}$ with

\begin{aligned} &P(X_{n+1} = j \mid X_n = i) \\[0.4em] &\quad = P_{ij} \end{aligned}

for every $n \ge 0$ and all states $i, j$ with $P(X_n = i) > 0$ . The Markov property and time homogeneity are separate assumptions. A chain can have the Markov property while its transition probabilities change from one step to the next.

In plain words The same rule moves the chain at every step. Which part of the rule applies depends on the current state, but not on the clock.

Example The two-mode machine, which moves with the same probabilities $0.8$ , $0.2$ , $0.3$ and $0.7$ at every inspection, is time-homogeneous. A machine that stays in A with probability $0.8$ at daytime inspections but with probability $0.6$ at nighttime inspections, with no other dependence on the past, is still a Markov chain but is not time-homogeneous. The length of a step belongs to the rule as well. Probabilities for one-hour steps cannot be used as if each step were a day.

Transition matrix

Definition For a time-homogeneous chain on a finite state space whose states are listed in a fixed order, the transition matrix is $P = (P_{ij})$ with $P_{ij} = P(X_{n+1} = j \mid X_n = i)$ . This course uses the row-stochastic convention, so row $i$ belongs to the current state $i$ and column $j$ to the next state $j$ . Every entry is nonnegative, and for each state $i$ the row sums to $1$ ,

\sum_{j \in S} P_{ij} = 1,

because from state $i$ the chain moves to exactly one state. The columns need not sum to $1$ . Some books use the transposed, column-stochastic convention. Either one works on its own, but mixing them in one calculation can give wrong answers.

In plain words Read row $i$ as the answer to the question “if the chain is in $i$ now, where does it go next?” A diagonal entry is the chance of staying in the same state for one step, and an off-diagonal entry is the chance of switching.

Example For the two-mode machine, with the states in the order A, B,

P = \begin{pmatrix} 0.8 & 0.2 \\ 0.3 & 0.7 \end{pmatrix}.

Current state	Next A	Next B	Row sum
A	0.8	0.2	1
B	0.3	0.7	1

The rows sum to $1$ , while the columns sum to $1.1$ and $0.9$ . The entry $0.8$ is not a timetable of four steps in A followed by a switch. A run in A of any length is possible, and at each step the run continues with probability $0.8$ . The row for B stays part of the model even if the machine starts in A for certain, because B can be reached later.

Initial distribution

Definition The initial distribution of a chain is the law of its starting state, written as the row vector $\pi_0$ whose entries are the probabilities $P(X_0 = i)$ for $i \in S$ , in the same order as the rows of $P$ . Its entries are nonnegative and add to $1$ , and the transition matrix does not determine it. Together, $\pi_0$ and $P$ determine the probability of every path. By the multiplication rule for conditional probabilities, the Markov property and time homogeneity,

\begin{aligned} &P(X_0 = i_0, \dots, X_n = i_n) \\[0.4em] &\quad = P(X_0 = i_0) \\[0.4em] &\qquad \times P_{i_0 i_1} P_{i_1 i_2} \cdots P_{i_{n-1} i_n}. \end{aligned}

In plain words The matrix says how the chain moves, and the initial distribution says where it starts. A path probability multiplies the chance of the starting state by the chance of each move along the path. These factors are conditional probabilities, so the product is not a claim that the states are independent.

Example If the machine starts in A for certain, then $\pi_0 = (1, 0)$ and the path A, B, A has probability $1 \cdot 0.2 \cdot 0.3 = 0.06$ . If instead $\pi_0 = (0.4, 0.6)$ , the same path has probability $0.4 \cdot 0.2 \cdot 0.3 = 0.024$ . With the matrix alone, the probability of mode A at step $1$ is not determined. A start in A with probability $a$ , where $0 \le a \le 1$ , gives $0.8a + 0.3(1 - a) = 0.3 + 0.5a$ , which can be any number from $0.3$ to $0.8$ .

One-step update

Definition Let $\pi_n$ be the row vector of the probabilities $P(X_n = i)$ for $i \in S$ . For a time-homogeneous chain with transition matrix $P$ ,

\pi_{n+1} = \pi_n P.

Coordinate by coordinate, this is the law of total probability over the current state,

\begin{aligned} &P(X_{n+1} = j) \\[0.4em] &\quad = \sum_{i \in S} P(X_n = i)\, P_{ij}. \end{aligned}

The new vector again has nonnegative entries that add to $1$ , because each row of $P$ sums to $1$ .

In plain words To find the chance of each next state, send the probability of every current state along its arrows and add what arrives at each state. The update averages the rows of $P$ , with the current probabilities as weights.

Example From $\pi_0 = (0.4, 0.6)$ , the A coordinate of $\pi_1$ is $0.4 \cdot 0.8 + 0.6 \cdot 0.3 = 0.32 + 0.18 = 0.5$ , and the B coordinate is $0.4 \cdot 0.2 + 0.6 \cdot 0.7 = 0.08 + 0.42 = 0.5$ , so

\begin{aligned} \pi_1 &= (0.4,\ 0.6)\, P \\[0.4em] &= (0.5,\ 0.5). \end{aligned}

Starting in A for certain, two updates give $\pi_1 = (0.8, 0.2)$ and $\pi_2 = (0.7, 0.3)$ . The A coordinate of $\pi_2$ is $0.8 \cdot 0.8 + 0.2 \cdot 0.3 = 0.64 + 0.06 = 0.70$ , which adds the paths A, A, A and A, B, A. Repeating the update $n$ times amounts to multiplying by the matrix power $P^n$ , and splitting a run of steps at an intermediate time gives the Chapman-Kolmogorov relation. Both are developed in Multi-Step Markov Probabilities.

Check yourself

The two-mode machine starts in B for certain. Find the distribution of $X_1$ and the probability of the path B, A, B.

Show the answer

The initial distribution is $\pi_0 = (0, 1)$ , so $\pi_1 = \pi_0 P$ is the B row of $P$ , which is $(0.3, 0.7)$ . The path B, A, B multiplies the chance $0.3$ of moving from B to A by the chance $0.2$ of moving from A to B, so its probability is $0.3 \cdot 0.2 = 0.06$ . The second factor comes from the A row, because the chain is in A at step $1$ , and by the Markov property the earlier state B does not change it.

With the same start in B, find the probability that the machine is in A at step $2$ . A classmate says that by the Markov property the state at step $2$ does not depend on the starting state, so the answer must equal the value $0.70$ found for a start in A. Explain the mistake.

Show the answer

Two disjoint paths end in A. The path B, A, A has probability $0.3 \cdot 0.8 = 0.24$ , and the path B, B, A has probability $0.7 \cdot 0.3 = 0.21$ , so

\begin{aligned} &P(X_2 = A \mid X_0 = B) \\[0.4em] &\quad = 0.24 + 0.21 = 0.45. \end{aligned}

This differs from $0.70$ , so the starting state does matter. The Markov property says that earlier states add nothing once the current state is known. Here the state at step $1$ is not given, and the start influences step $2$ through it.

Someone writes the machine’s rule as the matrix

Q = \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix}

and multiplies the row vector $(0.4, 0.6)$ by it. What do they get, and which check exposes the mistake?

Show the answer

The product is $(0.4 \cdot 0.8 + 0.6 \cdot 0.2,\ 0.4 \cdot 0.3 + 0.6 \cdot 0.7) = (0.44, 0.54)$ , whose entries add to $0.98$ , so it is not a probability distribution. The rows of $Q$ sum to $1.1$ and $0.9$ , so $Q$ is not row-stochastic. It is the transpose of $P$ , with the current state in the columns, and using it with a row vector mixes the two conventions. The correct update is $(0.4, 0.6)P = (0.5, 0.5)$ .

Markov Chains and Transition Matrices

Key terms

State

Markov chain

Time-homogeneous chain

Transition matrix

Initial distribution

One-step update

Check yourself

How this lesson connects

Builds on

Used later in