MAST30001 Chap.2 Discrete-Time Markov Chains
Discrete-Time Markov Chains
Discrete-time Markov chains model systems that move among states at integer steps. This chapter develops transition matrices and multi-step probabilities, then uses the directed graph to find communicating classes, recurrence and period. Stationary distributions are interpreted only after the structural conditions are checked.
First-step equations provide a compact method for hitting probabilities and expected hitting times without enumerating every possible path. Matrix calculations and graph structure answer different questions: powers describe finite-step movement, while closed classes and periods determine what long-run claims are justified. Keeping those layers separate prevents a solved stationary equation from being mistaken for convergence.
What this chapter covers
- 01
The Markov property and homogeneous one-step transitions
- 02
Transition matrices, initial distributions and matrix powers
- 03
Directed graphs and communicating classes
- 04
Recurrence, transience, period and positive recurrence
- 05
Stationary and limiting distributions
- 06
First-step equations for hitting probabilities and times
Worked example · free
Solve a first-step absorption problem
- 1Set boundary values h(0)=0 and h(2)=1.
- 1First-step conditioning gives h(1)=0.30(0)+0.20h(1)+0.50(1).
- 1Rearrange to 0.80h(1)=0.50.
- 1Therefore h(1)=0.625, which lies between zero and one.
Key terms
- Communicating Class
- A maximal set of states that can each reach every other state with positive probability.
- Irreducible Chain
- A Markov chain whose state space consists of one communicating class.
- Recurrent State
- A state that is revisited with probability one after the chain starts there.
- Period
- The greatest common divisor of the possible positive return times to a state.
- Ergodic Chain
- A chain with long-run state probabilities that are positive and independent of the initial state under the course conditions.
- First-Step Analysis
- A method that conditions once on the next state to form recursive equations for future events or times.
- Closed Class
- A communicating class that has no positive-probability transition to any state outside the class.
- Hitting Probability
- The probability that a chain reaches a specified target set, often found by first-step equations.
Discrete-Time Markov Chains FAQ
How do I orient a transition matrix?
Under the course convention, row i describes the current state and column j the next state, so p_ij means from i to j. Each row must be nonnegative and sum to one, and a row-vector distribution evolves by multiplying on the right.
Does a stationary distribution always describe the limit?
No. A stationary distribution is preserved by a transition, but periodicity can make probabilities oscillate and reducibility can make long-run behaviour depend on the starting class. Check irreducibility, aperiodicity and positive recurrence before claiming convergence from arbitrary starts.
Why is first-step analysis efficient?
It replaces an infinite collection of possible paths with recursive equations for smaller versions of the same problem. Boundary values encode success, failure or zero remaining time, while self-loops remain in the equation because they consume a step without resolving the event.
How do I identify a closed communicating class?
First draw every positive-probability arrow. States communicate when each can reach the other through directed paths. A communicating class is closed when no arrow leaves it for a state outside the class. Once entered, that class traps the chain, so transient states outside it cannot receive positive stationary mass in many finite examples.
What does the period measure?
The period is the greatest common divisor of all positive return lengths available from a state. In an irreducible class every state has the same period. A self-loop forces period one, but period one can also arise from return cycles whose lengths have greatest common divisor one.
How should I check a system of hitting equations?
Insert the boundary values first, then substitute the proposed solution into every non-boundary equation. Hitting probabilities must remain between zero and one; finite expected hitting times must be nonnegative. If a self-loop occurs, retain its term before collecting unknowns because the loop consumes a transition.
Exam move
Draw the transition graph before doing matrix algebra. Use it to partition communicating classes, identify closed classes and inspect return lengths. Then practise two algebra routines: solve a normalised stationary equation and form first-step equations with explicit boundary values. On every stationary question, write the structural condition that supports the interpretation.
On every hitting question, check that probabilities stay between zero and one and that expected times are nonnegative. Substitute final vectors back into the transition equation rather than trusting a single rearrangement. During mixed practice, annotate each problem with one of four verbs: propagate, classify, balance or hit.
Propagation calls for matrix powers, classification for the directed graph, balance for a stationary equation, and hitting for first-step recursion. After solving, vary the initial state or add a self-loop and predict which conclusions change. This builds structural judgement instead of formula recall and exposes whether you have confused stationarity with limiting behaviour.
Working through Discrete-Time Markov Chains in MAST30001? Sia is AskSia’s AI Statistics tutor — ask any MAST30001 Discrete-Time Markov Chains question and get a clear, step-by-step explanation grounded in how MAST30001 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
