How to Calculate Probabilities in a Markov Chain

A Markov chain models a process that moves between states in discrete time. Its defining property is that the distribution of the next state depends on the current state, not on the full history:

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

The phrase “calculate the probability” can mean several things: the probability of a state after a fixed number of steps, the probability of one particular path, the probability of ever reaching a state, or the long-run proportion of time spent in each state. The transition matrix gives the first two directly; the other questions require related equations.

Transition matrices

Suppose the chain has states $1,2,\ldots,k$. Using the common row-vector convention, define the transition matrix $P$ by

$$P_{ij}=\Pr(X_{n+1}=j\mid X_n=i).$$

Thus, row $i$ describes where the chain can go when it is currently in state $i$. Every entry must satisfy $0\le P_{ij}\le 1$, and every row must sum to $1$:

$$\sum_{j=1}^k P_{ij}=1.$$

If the current-state distribution is the row vector

$$\boldsymbol{\pi}_n= \begin{bmatrix} \Pr(X_n=1)&\Pr(X_n=2)&\cdots&\Pr(X_n=k) \end{bmatrix},$$

then the next distribution is

$$\boldsymbol{\pi}_{n+1}=\boldsymbol{\pi}_nP.$$

After $n$ steps,

$$\boldsymbol{\pi}_n=\boldsymbol{\pi}_0P^n.$$

If the chain starts in state $i$ with certainty, $\boldsymbol{\pi}_0$ has a $1$ in position $i$ and zeros elsewhere. The probability of being in state $j$ after $n$ steps is the $j$th component of $\boldsymbol{\pi}_0P^n$.

Worked example: state after three steps

Consider a two-state weather chain with states Sunny ($S$) and Rainy ($R$). Suppose

• after a sunny day, the next day is sunny with probability $0.8$ and rainy with probability $0.2$;
• after a rainy day, the next day is sunny with probability $0.4$ and rainy with probability $0.6$.

With the state order $(S,R)$,

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

Assume today is sunny, so

$$\boldsymbol{\pi}_0=\begin{bmatrix}1&0\end{bmatrix}.$$

The required probability that it rains three days from today is the second component of $\boldsymbol{\pi}_0P^3$.

First calculate the powers of $P$:

$$P^2= \begin{bmatrix} 0.8&0.2\\ 0.4&0.6 \end{bmatrix} \begin{bmatrix} 0.8&0.2\\ 0.4&0.6 \end{bmatrix} = \begin{bmatrix} 0.72&0.28\\ 0.56&0.44 \end{bmatrix},$$

and

$$P^3=P^2P= \begin{bmatrix} 0.688&0.312\\ 0.624&0.376 \end{bmatrix}.$$

Therefore,

$$\boldsymbol{\pi}_3=\boldsymbol{\pi}_0P^3 =\begin{bmatrix}1&0\end{bmatrix} \begin{bmatrix} 0.688&0.312\\ 0.624&0.376 \end{bmatrix} =\begin{bmatrix}0.688&0.312\end{bmatrix}.$$

The probability of rain three days from today is therefore $0.312$, or 31.2%.

The entry $(P^n)_{ij}$ has a useful direct interpretation: it is the probability of being in state $j$ after $n$ steps, given that the chain started in state $i$.

Probability of one particular path

If you want the probability of a specified sequence of states, multiply the transition probabilities along the path. For example, in the weather chain, the path

$$S\to R\to R\to S$$

has probability

$$\Pr(S,R,R,S\mid X_0=S) =P_{SR}P_{RR}P_{RS} =(0.2)(0.6)(0.4)=0.048.$$

So this particular three-transition path has probability $4.8\%$.

Do not confuse this with the probability of being sunny after three steps. Many different paths end in $S$, and their probabilities must be added. Matrix multiplication performs that summation automatically.

If the starting state is uncertain

Suppose the weather is sunny with probability $0.7$ and rainy with probability $0.3$. Then

$$\boldsymbol{\pi}_0=\begin{bmatrix}0.7&0.3\end{bmatrix}.$$

The distribution after three days is

$$\boldsymbol{\pi}_3=\boldsymbol{\pi}_0P^3 =\begin{bmatrix}0.7&0.3\end{bmatrix} \begin{bmatrix}0.688&0.312\\ 0.624&0.376 \end{bmatrix} =\begin{bmatrix}0.6688&0.3312\end{bmatrix}.$$

Thus the probability of rain after three steps is $0.3312$. An uncertain initial state is handled by averaging over the possible starting states through the initial distribution vector.

Hitting or reaching probabilities

“Will the chain ever reach state $A$?” is different from “where is it after $n$ steps?” For a finite chain with absorbing or target states, define

$$h_i=\Pr(\text{eventually reach }A\mid X_0=i).$$

Then set $h_A=1$. If another state $B$ cannot reach $A$, set $h_B=0$. For every other state, use first-step analysis:

$$h_i=\sum_j P_{ij}h_j.$$

These simultaneous linear equations produce the eventual hitting probabilities. A matrix power answers a fixed-time question; it does not by itself answer an “ever” question.

Long-run probabilities

A stationary distribution is a probability vector $\boldsymbol{\pi}$ satisfying

$$\boldsymbol{\pi}P=\boldsymbol{\pi}, \qquad \sum_i\pi_i=1.$$

When a finite chain is irreducible and aperiodic, the distribution often converges to this stationary distribution regardless of the initial state. This describes long-run behavior, not necessarily the probability at a particular finite time.

For the weather example, write $\boldsymbol{\pi}=(p,1-p)$. Solving $\boldsymbol{\pi}P=\boldsymbol{\pi}$ gives

$$p=0.8p+0.4(1-p),$$

so $p=2/3$. The stationary distribution is therefore $(2/3,1/3)$: in the long run, about two-thirds of days are sunny and one-third rainy.

Common mistakes

1. Reversing the matrix convention. With row vectors, use $\boldsymbol{\pi}_{n+1}=\boldsymbol{\pi}_nP$. With column vectors, the formula becomes $\boldsymbol{\pi}_{n+1}=P\boldsymbol{\pi}_n$, but the matrix entries must be arranged consistently.
2. Using a single transition probability for multiple steps. The probability of rain tomorrow is not generally the probability of rain two days from now. Use $P^2$ or sum over the possible intermediate states.
3. Multiplying all possible paths when asking for a final state. Multiply along each path, then add the probabilities of all paths ending in the target state.
4. Confusing stationary and finite-time probabilities. A stationary distribution describes equilibrium behavior; it is not automatically the distribution after one or two steps.
5. Ignoring the initial distribution. The same transition matrix can give different answers depending on where the chain starts.