Markov chains
The conceptWhy today's weather is enough to guess tomorrow's
A Markov chain is a process that hops between states at random, where the odds of the next hop depend only on the current state, not on how you got there. This rule is called the Markov property, or memorylessness.
Take a toy weather model. If today is sunny, tomorrow is sunny with probability 0.9 and rainy with 0.1; if rainy, it's 0.5 each way. Last week's weather plays no part: the model only looks at today.
Drawn as a graph, like in BFS and Dijkstra, each edge carries a probability instead of a distance. They go in a table, the transition matrix P: row i gives the odds of moving from state i to each state, so it sums to 1.
What it’s forTurns today's odds for each state into tomorrow's odds.
pₜ₊₁(j) = Σᵢ pₜ(i) · Pᵢⱼ
- pₜ(i)
- the probability of being in state i at step t
- Pᵢⱼ
- the chance of hopping from state i to state j in one step, e.g. sunny→rainy = 0.1
- Σᵢ
- add up over every state i you could be coming from
What it givesThe probability of being in each state one step later.
- Today sunny for sure: tomorrow sunny = 0.9
- Day after: 0.9 × 0.9 + 0.1 × 0.5 = 0.81 + 0.05 = 0.86
- In the long run sunny settles at 5/6 ≈ 0.83, wherever you start