A Markov chain is a model for a system that moves between possible states, such as weather changing from sunny to rainy or a website user moving between pages. It is useful because many real situations involve repeated steps with uncertainty. Instead of predicting one exact future path, a Markov chain describes the probabilities of many possible paths.
This makes it a powerful tool in statistics, physics, computer science, economics, and biology.
The key idea is the memoryless property: the next state depends only on the current state, not on the full history of how the system got there. Transition probabilities tell how likely each move is, and these probabilities are often organized in a transition matrix. By multiplying probability vectors by the transition matrix, you can predict the distribution of states after many steps.
In many chains, the probabilities approach a steady state, where the long-run distribution stops changing.
Understanding Statistics: Markov Chains
Building a useful Markov chain starts with choosing the states carefully. States must be distinct and cover every possible situation in the model. For a school bus, states might be early, on time, or late.
The time step must be clear too. It could mean one day, one stop, or one week. A model can give misleading results when its states are too broad.
For example, a weather model using only sunny and rainy may miss an important difference between light rain and a storm. More states can make a model more realistic, but they require more data to estimate reliable probabilities.
The entries in a transition table usually come from observations. If a shop records where visitors go after opening its home page, it can count each next-page move. Dividing each count by the total number of visitors currently on that page gives an estimated chance for each move.
These estimates are not perfect facts. A small sample can produce noisy values.
Patterns may differ on weekends, during holidays, or after a website redesign. Good statistical work checks whether the same probabilities make sense for the period being studied.
Several features of a chain affect its long-term behavior. An absorbing state is one that cannot be left after the process reaches it. A board game ending square is a simple example.
Some chains can get trapped in separate groups of states. In that case, the final pattern depends strongly on where the process began. Other chains cycle, moving back and forth in a regular rhythm.
A chain that alternates between two states does not settle at each individual step, even if its average behavior over many steps is balanced. These details matter before assuming that a stable long-run distribution exists.
Markov chains appear in search engines, speech recognition, genetics, queues, games, and routes through transport systems. They are especially useful when a full history would be huge to store or analyze. Still, the memory assumption is a simplification.
Tomorrow's weather can depend on more than today, and a person's next purchase can depend on earlier choices. One solution is to enlarge the state. A weather state could include both today's conditions and the season.
When learning, practice reading rows as choices from one starting state, checking that every probability is sensible, and explaining results in ordinary words. Computer calculations can handle many steps, but they cannot fix a poorly designed model.
Key Facts
- Memoryless property: P(X_{n+1} = j | X_n = i, past states) = P(X_{n+1} = j | X_n = i).
- A transition probability p_ij is the probability of moving from state i to state j in one step.
- Each row of a transition matrix sums to 1: p_i1 + p_i2 + ... + p_ik = 1.
- If v_n is a row vector of state probabilities, then v_{n+1} = v_n P.
- After two steps, the transition matrix is P^2, and after n steps it is P^n.
- A steady state distribution pi satisfies pi = pi P and the probabilities in pi sum to 1.
Vocabulary
- State
- A state is one possible condition or category that the system can be in at a given step.
- Transition probability
- A transition probability is the chance that the system moves from one state to another in one step.
- Transition matrix
- A transition matrix is a table of transition probabilities for all possible moves between states.
- Memoryless property
- The memoryless property means the next state depends only on the current state and not on earlier states.
- Steady state
- A steady state is a long-run probability distribution that stays the same after applying the transition matrix.
Common Mistakes to Avoid
- Forgetting that each row of the transition matrix must sum to 1. This is wrong because the entries in a row represent all possible next states from one current state.
- Using the full history to compute the next step in a basic Markov chain. This is wrong because the Markov property says only the current state matters.
- Mixing up row vectors and column vectors when multiplying by the transition matrix. This is wrong because v_{n+1} = v_n P uses a row vector, while column-vector notation usually uses v_{n+1} = P v_n.
- Assuming every Markov chain has one simple steady state. This is wrong because some chains are periodic, reducible, or have absorbing states that change the long-run behavior.
Practice Questions
- 1 A two-state Markov chain has transition matrix P = [[0.7, 0.3], [0.4, 0.6]]. If the current distribution is v_0 = [1, 0], find v_1.
- 2 For P = [[0.8, 0.2], [0.1, 0.9]], solve for the steady state distribution pi = [x, y] where pi = pi P and x + y = 1.
- 3 A student says a Markov chain cannot model weather because yesterday's weather also matters. Explain when a Markov chain could still be a useful weather model and what assumption it makes.