Markov chains model systems that move between states with fixed probabilities at each step. This reference helps students organize transition diagrams, matrices, state vectors, and long-run predictions. It is useful for probability, statistics, discrete math, and applied modeling problems.
The main idea is that the next state depends only on the current state, not the full past history.
A discrete-time Markov chain uses a transition matrix and a state vector to describe probabilities after steps. Matrix powers such as predict long-run behavior, while steady states satisfy . Absorbing chains use canonical form to find absorption probabilities and expected time to absorption.
The most important skills are setting up , multiplying in the correct order, and interpreting each probability carefully.
Key Facts
- A Markov chain has the memoryless property .
- A transition matrix is stochastic, so every entry satisfies and each row sum is .
- If is a row state vector, then the next state vector is .
- The state vector after steps is when using row vectors.
- A steady-state distribution satisfies and .
- For many regular chains, the rows of approach the same steady-state vector as .
- In an absorbing chain written as , the fundamental matrix is .
- For an absorbing chain, absorption probabilities are given by and expected steps to absorption are given by .
Vocabulary
- State
- A state is one possible condition or category that the system can occupy at a given step.
- Transition Probability
- A transition probability is the probability of moving from state to state in one step.
- Transition Matrix
- A transition matrix stores all one-step transition probabilities for a Markov chain.
- State Vector
- A state vector lists the probabilities of being in each state after steps.
- Steady-State Distribution
- A steady-state distribution is a probability vector that does not change after multiplying by .
- Absorbing State
- An absorbing state is a state that cannot be left once entered, so its self-transition probability is .
Common Mistakes to Avoid
- Using columns when the problem uses row vectors is wrong because the update rule changes from to . Match the vector convention before multiplying.
- Forgetting that each row of must sum to is wrong because transition probabilities from one current state must cover all possible next states.
- Treating as multiplying every entry of by is wrong because means repeated matrix multiplication, not scalar multiplication.
- Solving only without is incomplete because a steady-state distribution must be normalized as a probability vector.
- Using for an absorbing chain is wrong because the fundamental matrix uses only the transient-to-transient block, so .
Practice Questions
- 1 A two-state chain has and . Find and .
- 2 Find the steady-state distribution for using and .
- 3 For an absorbing chain with and , compute and .
- 4 Explain why a transition matrix with a row sum of cannot represent a valid Markov chain, even if all entries are positive.
Understanding Markov Chains Reference
The hardest part of many Markov chain problems is not calculation. It is choosing states that capture the information needed for a useful prediction. For a weather model, states such as sunny, cloudy, and rainy may be enough.
For a customer model, states might be browsing, buying, or leaving. A state should describe the system at one time step without being too detailed.
If important information is missing, the probabilities can change in ways the model cannot represent. For example, a weather model based only on today may work poorly if seasonal changes strongly affect tomorrow.
Matrix layout matters more than students often expect. With the row vector convention, a row describes where the system is now and a column describes where it may go next. The entry in the row for state A and the column for state B is the chance of moving from A to B in one step.
A row with a large diagonal entry means the system often stays where it is. Before doing any multiplication, label every row and column in the same state order.
Then check that each row totals one. This simple check catches missing probabilities, reversed entries, and arithmetic errors.
A result after several steps is built from all possible routes, not just the most obvious route. To find the chance of reaching a destination in two steps, include every intermediate state that could lead there. Each route contributes a product of its step probabilities.
Those route contributions are then added. Matrix multiplication performs this bookkeeping quickly. Powers of a matrix are therefore useful when the number of steps is large, but a calculator result still needs interpretation.
A probability near zero means an outcome is unlikely, not impossible. A probability near one means it is very likely under the assumptions of the model.
Long-run behavior needs careful thought. Some chains settle into stable proportions because movement keeps mixing the states. In that case, starting from different initial distributions eventually gives nearly the same overall pattern.
Other chains do not settle in this way. A chain can alternate between states forever, or it can split into separate groups that never communicate. An absorbing state is a special case where, once entered, there is no way out.
These models appear in games where a player is eliminated, medical models with recovery or discharge, and reliability studies where a device has failed. The fundamental matrix records the average number of visits to temporary states before absorption.
Its row totals give average waiting times. Absorption probabilities show which final outcome is most likely, which is often more informative than the average time alone.