TheIBAxolotl
States and transitions
A Markov chain describes a system that moves between a fixed set of states (gym A or gym B, sunny or rainy, brand X, Y or Z) in steps. The key assumption is that the probability of moving to the next state depends only on the current state, not on the history.
The transition matrix
Collect the probabilities in a square matrix \(T\). In the convention used in this course, each column represents where you come from and each row where you go to, so every column adds to 1.
A state diagram shows the same information: circles for states and arrows labelled with probabilities.
Predicting the future
Write the current distribution as a column vector \(s_0\) (proportions or numbers in each state). Then
\[s_1 = T s_0, \qquad s_n = T^{n} s_0\]
The entry in row \(i\), column \(j\) of \(T^n\) is the probability of being in state \(i\) after \(n\) steps, having started in state \(j\).
Worked example
Each month, 80% of gym A members stay and 20% switch to B; 70% of B members stay and 30% switch to A.
\[T = \begin{pmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{pmatrix}\]
(columns: from A, from B). If members start evenly split, \(s_0 = \begin{pmatrix} 0.5 \\ 0.5 \end{pmatrix}\) and
\[s_1 = \begin{pmatrix} 0.8(0.5) + 0.3(0.5) \\ 0.2(0.5) + 0.7(0.5) \end{pmatrix} = \begin{pmatrix} 0.55 \\ 0.45 \end{pmatrix}\]
Steady state. Look for \(s\) with \(Ts = s\) and entries adding to 1. With \(s = \begin{pmatrix} a \\ b \end{pmatrix}\): \(0.8a + 0.3b = a\), so \(0.3b = 0.2a\), and \(a + b = 1\). Hence \(a = 0.6\), \(b = 0.4\). In the long run 60% of members use gym A. Check: \(T\begin{pmatrix}0.6\\0.4\end{pmatrix} = \begin{pmatrix}0.48 + 0.12 \\ 0.12 + 0.28\end{pmatrix} = \begin{pmatrix}0.6\\0.4\end{pmatrix}\).
Three ways to find the steady state
- Equations: solve \(Ts = s\) together with "entries sum to 1".
- Eigenvector: the steady state is the eigenvector for eigenvalue 1, scaled so its entries add to 1. Here \(\begin{pmatrix} 3 \\ 2 \end{pmatrix}\) scales to \(\begin{pmatrix} 0.6 \\ 0.4 \end{pmatrix}\).
- High power: compute \(T^{50}\) on the GDC; every column becomes the steady-state vector.
Regular chains
A chain is regular if some power of \(T\) has all entries strictly positive. Regular chains have a single steady state that is reached whatever the starting vector, so the long-term answer does not depend on how the system starts.
Common mistakes
- Building \(T\) with rows summing to 1 and then multiplying \(T s_0\); check which convention the question uses and stay consistent.
- Multiplying \(s_0 T\) instead of \(T s_0\) for column vectors.
- Forgetting the condition that the probabilities in the steady state add to 1.
- Using \(n - 1\) instead of \(n\) in \(T^n\) when "after 3 months" means three steps.
Exam tips
- Label rows and columns of \(T\) with the state names.
- When using a high power, write it down (for example "\(T^{50}\)") as your method.
- If asked to "interpret" the steady state, give the long-term percentages in context, and multiply by the total population if it is fixed.