# Key concepts:
- **State** → possible condition of the system
- **Transition probability** → chance of moving between states
- **Transition matrix** → all transition probabilities
- **State distribution** → probabilities of current states
- **Stationary distribution** → long-term equilibrium
# Markov Chain
A **Markov chain** is a mathematical model that describes how a system moves between different **states** over time.
The key idea is the **Markov property**:
> The probability of the future state depends only on the current state, not on the complete history of previous states.
For a **first-order Markov chain**:
$
P(X_{t+1}|X_t,X_{t-1},...,X_0)=P(X_{t+1}|X_t)
$
This means:
- Once we know the current state, the past provides no additional information about the future.
- The current state contains all the information needed to predict the next state.
Example:
If today's weather is rainy, knowing whether yesterday was sunny or rainy does not change the prediction for tomorrow. Only today's weather matters.
# Components of a Markov Chain
A Markov chain consists of:
1. **States** — possible conditions of the system
2. **Transition probabilities** — probabilities of moving between states
3. **Transition matrix** — a table containing all transition probabilities
4. **Initial distribution** — probabilities of starting in each state
# State
A **state** is a possible condition of the system.
Example: Weather model
$
S=\{Sunny,Rainy\}
$
At any given time, the system is in one of the possible states.
# Transition Probability
A **transition probability** describes the probability of moving from one state to another.
Example:
$
P(Sunny \rightarrow Rainy)=0.2
$
Meaning:
> If today is Sunny, there is a 20% chance that tomorrow will be Rainy.
In general:
$
p_{ij}=P(X_{t+1}=j|X_t=i)
$
where:
- $i$ = current state
- $j$ = next state
- $p_{ij}$ = probability of transitioning from state $i$ to state $j$
# Transition Matrix
A **transition matrix** contains all possible transitions between states.
For the weather example:
| Current \ Next | Sunny | Rainy |
|---|---:|---:|
| Sunny | 0.8 | 0.2 |
| Rainy | 0.4 | 0.6 |
The matrix is:
$
P=
\begin{bmatrix}
0.8 & 0.2\\
0.4 & 0.6
\end{bmatrix}
$
The convention used here:
- Rows represent the **current state**
- Columns represent the **next state**
Each row must sum to 1:
$
\sum_j p_{ij}=1
$
because the system must transition to one of the possible states.
# Example: Weather Markov Chain
Assume two possible weather states:
- ☀️ Sunny
- 🌧️ Rainy
Transition probabilities:
If today is Sunny:
- 80% chance tomorrow is Sunny
- 20% chance tomorrow is Rainy
If today is Rainy:
- 40% chance tomorrow is Sunny
- 60% chance tomorrow is Rainy
Transition matrix:
$
P=
\begin{bmatrix}
0.8 & 0.2\\
0.4 & 0.6
\end{bmatrix}
$
# Predicting Future States
A **state distribution** represents the probability of being in each state.
Example:
Today is Sunny:
$
v_0=[1,0]
$
Meaning:
- 100% Sunny
- 0% Rainy
To predict tomorrow:
$
v_1=v_0P
$
Therefore:
$
[1,0]
\begin{bmatrix}
0.8 & 0.2\\
0.4 & 0.6
\end{bmatrix}
=
[0.8,0.2]
$
Tomorrow:
- ☀️ Sunny: 80%
- 🌧️ Rainy: 20%
---
## Two Steps Into the Future
Apply the transition matrix again:
$
v_2=v_1P
$
$
[0.8,0.2]
\begin{bmatrix}
0.8 & 0.2\\
0.4 & 0.6
\end{bmatrix}
=
[0.72,0.28]
$
After two days:
- ☀️ Sunny: 72%
- 🌧️ Rainy: 28%
In general:
$
v_n=v_0P^n
$
where:
- $v_n$ = probability distribution after $n$ steps
- $P^n$ = transition matrix multiplied by itself $n$ times
# Stationary Distribution
A **stationary distribution** is a probability distribution that remains unchanged after applying the transition matrix.
It satisfies:
$
\pi P=\pi
$
where:
- $\pi$ = stationary distribution
- $P$ = transition matrix
For the weather example:
$
\pi=[0.667,0.333]
$
Meaning:
Over a sufficiently long time:
- ☀️ Sunny occurs about 67% of the time
- 🌧️ Rainy occurs about 33% of the time
The system reaches a long-term equilibrium.
> Note: A stationary distribution exists for many Markov chains, but uniqueness and convergence depend on properties of the chain.