Training Systems Engineering Markov Chains & State Modeling
4 / 5

Markov Chains & State Modeling

24 min Systems Engineering

Markov Chains & State Modeling

A Markov chain models a system that transitions between states, where the probability of the next state depends only on the current state.

Transition Matrix

$$P = \begin{bmatrix} p_{11} & p_{12} & \cdots \\ p_{21} & p_{22} & \cdots \\ \vdots & \vdots & \ddots \end{bmatrix}$$

where $p_{ij}$ = probability of transitioning from state $i$ to state $j$. Each row sums to 1.

$n$-Step Transition

$$P^{(n)} = P^n$$

The probability of being in state $j$ after $n$ steps starting from state $i$ is the $(i,j)$ entry of $P^n$.

Steady-State Distribution

The vector $\pi$ satisfying $\pi P = \pi$ and $\sum \pi_i = 1$.

In the long run, the system spends a fraction $\pi_i$ of time in state $i$.

Example 1

A machine is either Working (W) or Broken (B). $P(W \to W) = 0.9$, $P(W \to B) = 0.1$, $P(B \to W) = 0.5$, $P(B \to B) = 0.5$. Find the steady-state availability.

$P = \begin{bmatrix}0.9 & 0.1 \\ 0.5 & 0.5\end{bmatrix}$

Steady state: $\pi_W = 0.9\pi_W + 0.5\pi_B$ and $\pi_W + \pi_B = 1$.

$\pi_W - 0.9\pi_W = 0.5\pi_B \implies 0.1\pi_W = 0.5(1-\pi_W)$

$0.1\pi_W = 0.5 - 0.5\pi_W \implies 0.6\pi_W = 0.5$

$$\pi_W = 5/6 \approx 0.833$$

The machine is available 83.3% of the time.

Example 2

Starting in state W, find the probability of being in state B after 2 steps.

$P^2 = P \cdot P = \begin{bmatrix}0.81+0.05 & 0.09+0.05 \\ 0.45+0.25 & 0.05+0.25\end{bmatrix} = \begin{bmatrix}0.86 & 0.14 \\ 0.70 & 0.30\end{bmatrix}$

$P(B \text{ after 2 steps} | \text{start W}) = 0.14$

Example 3

A 3-state system (Good, Degraded, Failed). From Good: stay 0.8, degrade 0.15, fail 0.05. From Degraded: repair to Good 0.3, stay 0.4, fail 0.3. From Failed: repair to Good 0.6, stay 0.4. Find the steady-state probability of failure.

Setting up $\pi P = \pi$:

$\pi_G = 0.8\pi_G + 0.3\pi_D + 0.6\pi_F$

$\pi_D = 0.15\pi_G + 0.4\pi_D$

$\pi_F = 0.05\pi_G + 0.3\pi_D + 0.4\pi_F$

From equation 2: $0.6\pi_D = 0.15\pi_G \implies \pi_D = 0.25\pi_G$

From equation 3: $0.6\pi_F = 0.05\pi_G + 0.075\pi_G = 0.125\pi_G \implies \pi_F = 0.2083\pi_G$

$\pi_G(1 + 0.25 + 0.2083) = 1 \implies \pi_G = 0.686$, $\pi_D = 0.171$, $\pi_F = 0.143$

Practice Problems

1. A weather model: Sunny → Sunny (0.7), Sunny → Rainy (0.3). Rainy → Sunny (0.4), Rainy → Rainy (0.6). Find steady-state probabilities.
2. For #1, if today is Sunny, find the probability it's Rainy in 2 days.
3. Verify that each row of the transition matrix sums to 1 for the machine example.
4. A system has states: Operational (O), Maintenance (M). $P(O→O) = 0.95$, $P(O→M) = 0.05$, $P(M→O) = 0.6$, $P(M→M) = 0.4$. Find steady-state availability.
5. What makes a Markov chain "memoryless"?
6. Define an absorbing state. Give an example.
7. A brand loyalty model: users of Brand A switch to B with P = 0.2; users of B switch to A with P = 0.3. Find the long-term market shares.
8. Compute $P^3$ for the 2×2 matrix in #1 (or describe the approach).
9. An IT system has 3 states: Up, Degraded, Down. Model it with a transition matrix of your choice and find the steady state.
10. Expected number of steps to go from state B back to state B in the machine example: $E[T_{BB}] = 1/\pi_B$.
11. If a transition matrix is doubly stochastic (rows and columns sum to 1), what is the steady state for $n$ states?
12. Ergodicity: what conditions must a Markov chain satisfy to have a unique steady-state distribution?
Show Answer Key

1. $0.3\pi_S = 0.4\pi_R$; $\pi_S + \pi_R = 1$. $\pi_S = 4/7 \approx 0.571$, $\pi_R = 3/7 \approx 0.429$

2. $P^2_{SR}$: compute $P^2$ and read the (S,R) entry ≈ 0.39

3. Row 1: $0.9+0.1=1$ ✓; Row 2: $0.5+0.5=1$ ✓

4. $0.05\pi_O = 0.6\pi_M$; $\pi_O = 12\pi_M$; $13\pi_M = 1$; $\pi_O = 12/13 = 0.923 = 92.3\%$

5. The future state depends only on the present state, not on the history of how the system reached it.

6. A state that, once entered, is never left ($p_{ii} = 1$). Example: a "permanently failed" state.

7. $0.2\pi_A = 0.3\pi_B$; $\pi_A = 0.6$, $\pi_B = 0.4$ (Brand A gets 60%)

8. $P^3 = P^2 \cdot P$; compute $P^2$ first, then multiply by $P$ again.

9. Example transition matrix and solving the steady-state equations.

10. $\pi_B = 1/6$; $E[T_{BB}] = 6$ steps

11. Uniform: $\pi_i = 1/n$ for all $i$

12. The chain must be irreducible (can reach any state from any other) and aperiodic (no cyclical patterns).

Decision Analysis & Trade Studies Placement Test Practice — Systems Engineering