Markov Chains and the Memoryless Assumption
Given the current state, earlier states add no information about the next state. For finitely many states, transitions form a matrix. When transition probabilities stay fixed over time, matrix powers give multi-step probabilities.
What a learner can do afterwards
- Write a finite-state transition matrix using a stated row and column order
- Compute an n-step transition probability, distinguishing fixed transitions from time-dependent transitions
- Give a process whose next-state law depends on older history and explain how a sufficient finite-memory state makes it Markov
1 · Read
You have conditioned forecasts on known information. A Markov chain says that, given the current state, earlier states add no information about the next-state probabilities. Equivalently, the conditional mean of each next-state indicator given the full past equals its conditional mean given the current state. Successive states can still be dependent. We use finitely many states here.
Fix the same state order for rows and columns. In a transition matrix P, row i, column j gives the chance of moving from state i to state j. Entries are nonnegative. Each row sums to 1 because the next states are exhaustive and mutually exclusive. In order (Sunny, Cloudy), consider rows (0.7, 0.3) and (0.2, 0.8). From Cloudy, the next state is Sunny with probability 0.2.
Use these weather transitions at both steps and start in Sunny. To be Sunny two steps later, the middle state can be Sunny or Cloudy. The path Sunny, Sunny, Sunny has probability 0.7 × 0.7 = 0.49. The path Sunny, Cloudy, Sunny has probability 0.3 × 0.2 = 0.06. These paths are disjoint, so add them: 0.49 + 0.06 = 0.55.
For a time-homogeneous chain, one matrix P applies at every step. P^n is the product of n copies of P. Its (i,j) entry gives the n-step chance from i to j. Compute P^2(i,j) by adding P(i,k) × P(k,j) over middle states k. For one specified path, multiply its transitions without adding alternatives. To update a state distribution, weight each transition to the target by its current-state probability and add. Repeat for further steps.
A machine may use one transition table in daytime and another at night. This can be Markov if, at each time, earlier states add no information once the current state is known. If consecutive tables are P then Q, the two-step table is PQ, not generally P^2. Its (i,j) entry adds P(i,k) × Q(k,j) over middle states k.
To disprove the Markov property, find two possible histories with the same current state but different next-state probabilities. If a rule depends only on the last two states, store the pair (a,b), with a older and b current. Its next pair is (b,c), where c is the new state. This pair process is Markov. Mentioning two days does not prove failure: the older day must change the conditional probabilities.
For a reflecting random walk on consecutive integer states, specify the end rule. Here an end sends the walker to its only neighbour with probability 1; an interior state chooses either neighbour with probability 0.5. Some models allow a stay at an end, so 'reflecting' alone is not enough. For a two-step chance, list possible intermediate states and destinations. If no path reaches the target, its probability is 0.
Given the present, older states add no next-state information. Fixed transition matrices give powers; changing matrices give ordered products. Store sufficient memory in the state.
The lesson, practice questions and flashcards were written for this dataset.
The three readings, five extra questions and six flashcards were written for this dataset. Video links: Origin of Markov chains and Conditional probability tree diagram example. Video reuse terms have not been verified.
More to read
A path is different from a destination
A machine has states On and Off. Use that order for rows and columns. Its fixed transition rows are (0.4,0.6) and (0.8,0.2). Each row tells how the next state is chosen after the current state is known. Assume the machine is Markov, so earlier states add no information to this choice.
Start in Off. The particular path Off,On,Off has probability 0.8 × 0.6 = 0.48. Ending in Off after two steps also permits Off,Off,Off, whose probability is 0.2 × 0.2 = 0.04.
Those paths have different middle states and cannot both occur. Their probabilities add to 0.52. Thus the specified path has probability 0.48, while the two-step destination event has probability 0.52. Before calculating, decide which event the question asks for.
When one symbol leaves out needed memory
Choose an initial pair uniformly from (A,A), (A,B), (B,A) and (B,B). Each later symbol repeats the symbol two places earlier.
Compare the possible histories (A,B) and (B,B). Both have current symbol B. After (A,B), the next symbol is A with probability 1. After (B,B), it is A with probability 0. The current symbol alone does not determine the next-symbol law, so this symbol process is not Markov.
Now make the state the ordered pair of most recent symbols. From (A,B), the next pair is (B,A). From (B,B), it is (B,B). In general, (a,b) becomes (b,a). The current pair determines the next pair without needing older symbols, so the pair process is Markov.
The larger state works because it contains all memory the rule needs. A pair would not cover a rule that genuinely needs an additional older symbol.
Following the order of transition tables
A Markov chain may change its transition probabilities with time. The Markov property compares information from earlier states with information from the current state at a fixed time. Time homogeneity is the separate condition that the transition table stays fixed.
Use state order (A,B). Suppose the first-step table P has rows (0.4,0.6), (0.3,0.7). The next-step table Q has rows (0.8,0.2), (0.1,0.9). Starting in A, the path through middle state A contributes 0.4 × 0.2 to reaching B. The path through middle state B contributes 0.6 × 0.9. Adding gives 0.08 + 0.54 = 0.62.
This is the A-to-B entry of PQ. Use P first and Q second, matching the order of transitions. If the same table P applies at every step, the n-step table is P^n. When tables change, use their ordered product instead.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
Optional connections
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
13 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.