Markov chains
Systems that move from one state to another at random: probability graph, transition matrix, distribution after several steps, absorbing states, stationary distribution and the idea behind PageRank.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Markov property: what is it?
Show the answer
The property of a process whose next state depends only on the present state, not on the path that led to it.
This is what lets a single transition matrix summarise the whole behaviour: the past no longer needs to be remembered.
A server is "up" or "down" each hour. For a Markov chain, what do you need to know to predict its state in the next hour?
- Its current state and the transition matrix
- All its states since commissioning
- Its last two states only
- The total time spent down
Show the answer
Its current state and the transition matrix
The Markov property makes the past irrelevant once the present state is known. If the time since the last failure mattered, the state alone would not suffice and this would not be a Markov chain on these two states.
If π₀ is the starting distribution, the distribution after n steps is π₀ × …, where P is the … matrix.
Show the answer
If π₀ is the starting distribution, the distribution after n steps is π₀ × Pⁿ, where P is the transition matrix.
The row vector is multiplied by the matrix at each step, so n times for n steps.
Transition matrix: what is it?
Show the answer
A square table whose row i gives the probabilities of moving from state i to each state.
Each row is a probability distribution: its coefficients are non-negative and sum to 1. A column has no reason to sum to 1.