Transition Matrices and Markov Chains
Understanding Transition Matrices
- A transition matrix represents the probabilities of moving from one state to another in a system.
- Each element $(p_{ij})$ in the matrix represents the probability of moving from state $i$ to state $j$.
All probabilities in a row must sum to 1, as they represent all possible outcomes from that state.
For example, if we have three states (A, B, C), a transition matrix P would look like:
$$P = \begin{pmatrix} p_{11} & p_{12} & p_{13} \\ p_{21} & p_{22} & p_{23} \\ p_{31} & p_{32} & p_{33} \end{pmatrix}$$
ExampleConsider the weather forecast:
- If it's sunny today, there's a 70% chance it'll be sunny tomorrow, and 30% chance of rain
- If it's rainy today, there's a 60% chance it'll be rainy tomorrow, and 40% chance of sunny
The transition matrix would be:
$$P = \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix}$$
Markov Chains
- A Markov chain is a sequence of events where the probability of each event depends only on the state of the previous event.
- This is called the Markov property.
The key characteristic of a Markov chain is that it's "memoryless" - only the current state matters for predicting the next state.
State Vectors
- The state vector represents the probability distribution across all states at a particular time.
- For $n$ states, it's a $1×n$ matrix: $$s = \begin{pmatrix} s_1 & s_2 & ... & s_n \end{pmatrix}$$
Finding Future States
To find the state vector after n steps:
- Multiply the initial state vector by the transition matrix $n$ times
- Or: $s_n = s_0P^n$
Using our weather example:
Initial state: Sunny (100%)
\[ s_0 = \begin{pmatrix} 1 & 0 \end{pmatrix} \]
After one day:
\[ s_1 = s_0 P = \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = \begin{pmatrix} 0.7 & 0.3 \end{pmatrix} \]
Steady State
- A steady state (or equilibrium) occurs when further transitions don't change the state probabilities.
- Relating to the Markov chain, it describes a system where the next state depends only on the current state.
- Over time, many Markov chains converge to a steady state, meaning the probabilities of being in each state remain constant across transitions.
Mathematically, the steady-state vector $s$ satisfies:
$$sP = s$$
where $P$ is the transition matrix.
HintThis means that once the system reaches the steady state, multiplying by the transition matrix does not change the state probabilities.
TipTo find the steady state:
- Let $π$ be the steady state vector
- Solve $πP=π$
- Use the fact that probabilities sum to 1
Don't forget that steady states only exist for regular Markov chains - chains that are irreducible and aperiodic.
Properties of Steady States
- All regular Markov chains have a unique steady state.
- The steady state is independent of the initial state.
- As $n$ approaches infinity, $P^n$ approaches a matrix with identical rows equal to the steady state.
For our weather example, solving \[\pi P = \pi\begin{pmatrix} x & y \end{pmatrix} \begin{pmatrix} 0.7 & 0.3 \\ 0.4 & 0.6 \end{pmatrix} = \begin{pmatrix} x & y \end{pmatrix} \] With \( x + y = 1 \), we get: \( x = 0.57, y = 0.43 \) So the steady state is \[\pi = \begin{pmatrix} 0.57 & 0.43 \end{pmatrix} \]
Markov Chains and Long-Term Behavior
- In the long run, a regular Markov chain always converges to a steady-state distribution, regardless of the starting conditions.
- This is particularly useful for predicting stable outcomes in systems such as weather patterns, economics, and population models.
In a customer loyalty model, even if customers start with different preferences, over time their probability of choosing different brands stabilizes, forming a steady-state distribution.
