Markov Chains & Stochastic Processes Practice Questions, Quiz, and Step-by-Step Lesson - improve your math skills with focused questions and clear explanations.
Markov Chains & Stochastic Processes Practice Quiz with a Step-by-Step Interactive Lesson
Use the quiz at the top of the page to practice Markov chains and stochastic processes: the Markov property, row-stochastic transition matrices, distribution updates \(pP\), powers \(P^n\), the Chapman-Kolmogorov law, stationary distributions \(\pi P=\pi\), absorbing states and closed classes, irreducibility, recurrence and transience, period and aperiodicity, finite-chain convergence, martingales, submartingales, supermartingales, filtrations, and stopping times. If you need a refresher, open the lesson for mentally followable examples and quick checks.
How this Markov chains and stochastic processes practice works
1. Take the quiz: answer questions about transition probabilities, stationary distributions, recurrence, periodicity, martingales, and stopping times.
2. Open the lesson: review row-stochastic matrices, class structure, long-run behavior, absorbing chains, and conditional expectation tools.
3. Retry: return to the quiz and decide whether to compute a matrix entry, solve \(\pi P=\pi\), classify a state, or check a conditional expectation.
What you will learn in the Markov chains & stochastic processes lesson
Transition laws and matrix powers
Read \(P_{ij}\) as the probability of moving from state \(i\) to state \(j\) in one step.
Update row-vector distributions by \(p_{n+1}=p_nP\) and \(p_n=p_0P^n\).
Use Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Stationary and long-run behavior
Solve \(\pi P=\pi\) together with \(\sum_i\pi_i=1\).
Recognize \(\pi\) as a left eigenvector with eigenvalue \(1\).
Recognize uniform stationary distributions in doubly stochastic chains and stationary rows in finite irreducible aperiodic chains.
Class structure of finite chains
Classify communicating classes, closed classes, and absorbing states.
Distinguish recurrent states from transient states in finite chains.
Compute periods from the gcd of possible return times.
Processes, martingales, and stopping times
Use filtrations \(\mathcal F_n\) to represent the information known by time \(n\).
Check martingales using \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Recognize that stopping times must be decided from past and present information, not unseen future data.
Ready to model the next step?
Return to the quiz and identify the state, transition rule, and relevant time horizon before choosing an answer.
Loading...
Random dynamics
Markov Chains & Stochastic Processes Lesson
1 / 8
Model random motion one step at a time
Purpose: Build a reliable toolkit for finite Markov chains and nearby stochastic-process ideas. You will read transition matrices, compute multi-step probabilities, solve for stationary distributions, classify states, recognize periodic behavior, and connect conditional expectation to martingales and stopping times.
Success criteria
State the Markov property: conditional on the present state, the future does not need the earlier past.
Check that a finite transition matrix is row-stochastic: entries are nonnegative and each row sums to \(1\).
Update row-vector distributions by \(p_{n+1}=p_nP\) and read \(P^n_{ij}\) as an \(n\)-step probability.
Use Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Solve \(\pi P=\pi\) with \(\sum_i\pi_i=1\) for stationary distributions, including uniform distributions for doubly stochastic chains.
Classify absorbing states, communicating classes, irreducibility, recurrence, and transience.
Find periods from return times and know why a self-loop forces period \(1\).
State the finite irreducible aperiodic convergence picture.
Recognize martingales, submartingales, supermartingales, and stopping times using conditional expectation and information available so far.
Key vocabulary
Stochastic process: a sequence of random variables such as \(X_0,X_1,X_2,\dots\).
Markov chain: a stochastic process whose next-state law depends on the current state, not the full past.
Transition matrix: \(P_{ij}=\Pr(X_{n+1}=j\mid X_n=i)\), with each row a probability distribution.
Stationary distribution: a distribution \(\pi\) with \(\pi P=\pi\).
Communicating class: states that can reach each other.
Period: the gcd of possible return times to a state.
Martingale: a process with \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Stopping time: a random time decided using information available up to that time.
Quick pre-check
Pre-check: In a Markov chain, after conditioning on the present state, what does the one-step future depend on?
Hint: The past can influence the future through the current state, but once the current state is known, earlier states add no extra information for the next-step law.
Rows encode one-step probabilities
Learning goal: Read a finite transition matrix and compute one-step or multi-step distributions without losing the probability convention.
Key idea
With the row-vector convention, a current distribution \(p_n\) updates by \(p_{n+1}=p_nP\). The entry \(P_{ij}\) is the chance to move from state \(i\) to state \(j\) in one step.
Matrix rules
Every entry satisfies \(0\le P_{ij}\le1\).
Each row sums to \(1\), because the next state must be somewhere.
A deterministic move has one row entry equal to \(1\) and the others \(0\).
An absorbing state \(i\) has \(P_{ii}=1\).
If \(p_0\) is a distribution, then \(p_0P^n\) is the distribution after \(n\) steps.
If all rows are identical, one step sends every starting distribution to that common row.
Chapman-Kolmogorov
Multi-step transitions compose: \[P^{m+n}=P^mP^n.\] Entrywise, this sums over all possible intermediate states.
Worked example
Example: Let \(P=\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}\) and \(p_0=(1,0)\). What is \(p_1\)?
Multiply on the right: \[p_1=p_0P=(1,0)\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}=(1/2,1/2).\] Starting in state \(1\), the next distribution is just row \(1\) of \(P\).
Try it
Try it: In a transition matrix, how should the row \((1/4,3/4)\) be classified?
Hint: Check nonnegativity and the row sum.
A stationary distribution is unchanged by one step
Learning goal: Recognize and solve stationary equations for finite chains.
Key idea
A row distribution \(\pi\) is stationary when \(\pi P=\pi\). In linear algebra terms, \(\pi\) is a left eigenvector of \(P\) with eigenvalue \(1\), normalized so its entries are nonnegative and sum to \(1\).
Solving checklist
Write \(\pi=(\pi_1,\dots,\pi_k)\).
Solve \(\pi P=\pi\).
Add the normalization \(\pi_1+\cdots+\pi_k=1\).
Check entries are nonnegative.
A finite doubly stochastic matrix preserves the uniform distribution.
For \(P=I\), every probability distribution is stationary.
In reducible chains, stationary distributions may be nonunique.
Two-state shortcut
For \(P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}\) with positive \(a+b\), the stationary distribution is proportional to \((b,a)\), so \(\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)\).
Worked example
Example: Find a stationary distribution for \(P=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\).
Both rows are uniform. Multiplying any distribution by \(P\) gives \((1/2,1/2)\), so \(\pi=(1/2,1/2)\) is stationary. This is the common-row shortcut: identical rows send every current distribution to that row.
Try it
Try it: What does \(\pi P=\pi\) mean?
Hint: One transition leaves the distribution exactly as it was.
Reachability controls the structure of the chain
Learning goal: Use graph reachability to classify states and communicating classes.
Key idea
Say \(i\) reaches \(j\) if \((P^n)_{ij}>0\) for some \(n\ge0\). States communicate when each reaches the other. An irreducible finite chain has one communicating class.
Classification language
Closed class: once entered, the chain cannot leave the class.
Absorbing state: a one-state closed class, equivalently \(P_{ii}=1\).
Recurrent state: returned to with probability \(1\).
Transient state: visited only finitely many times with probability \(1\).
Irreducible chain: every state communicates with every other state.
Finite-chain facts
In a finite irreducible chain, every state is recurrent. In a finite reducible chain, states outside closed classes are often transient because probability eventually moves into a closed class and stays there.
Worked example
Example: For \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\), which state is absorbing?
State \(1\) is absorbing because row \(1\) is \((1,0)\), so \(P_{11}=1\). State \(2\) can move to state \(1\), but state \(1\) cannot move back to state \(2\), so the chain is not irreducible.
Try it
Try it: What does irreducible mean for a finite Markov chain?
Hint: Think of the directed graph with an arrow \(i\to j\) when a transition has positive probability.
Return-time arithmetic decides aperiodicity
Learning goal: Compute simple periods and know why aperiodicity matters for convergence.
Key idea
The period of a state \(i\) is the gcd of all positive \(n\) such that \((P^n)_{ii}>0\). A state with period \(1\) is aperiodic. In an irreducible chain, all states have the same period.
Convergence picture
If a finite chain is irreducible and aperiodic, it has a unique stationary distribution \(\pi\).
For such a chain, \(P^n\) converges to a matrix whose rows are all \(\pi\).
If the chain is periodic, a stationary distribution can exist while \(P^n\) still oscillates.
If the chain is reducible, limiting behavior depends on the closed classes that can be reached.
Self-loops
A self-loop \(P_{ii}>0\) gives a possible return in one step, so the gcd of return times includes \(1\). That forces period \(1\).
Worked example
Example: For \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\), what happens after two steps?
The chain switches states every step. Thus \(P^2=I\), returns occur at even times, and each state has period \(2\).
Try it
Try it: What is the period of the chain with \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)?
Hint: Starting from a state, count the times at which return is possible.
Closed states turn probability questions into equations
Learning goal: Set up simple hitting-probability and hitting-time equations for absorbing behavior.
Key idea
An absorbing state traps the chain after it is entered. More generally, a closed communicating class cannot be left. Hitting questions ask whether and when the process enters a chosen set.
Hitting equations
For a hitting probability \(h_i\), use boundary values \(h_i=1\) on the target and \(h_i=0\) on impossible closed classes.
For other states, use \(h_i=\sum_j P_{ij}h_j\).
For an expected hitting time \(t_i\), use \(t_i=0\) on the target and \(t_i=1+\sum_jP_{ij}t_j\) elsewhere.
Keep equations small by using symmetry or obvious absorbing states.
Closed classes
An absorbing class is a communicating class that cannot be left. A single absorbing state is the smallest example of this idea.
Worked example
Example: For \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\), starting from state \(2\), what is the expected time to hit state \(1\)?
Let \(t_1=0\). From state \(2\), \[t_2=1+\frac12t_1+\frac12t_2=1+\frac12t_2.\] Hence \(t_2=2\).
Try it
Try it: If a Markov chain starts in an absorbing state, where is it after one step?
Hint: An absorbing state has \(P_{ii}=1\).
Conditional expectation tracks fair drift
Learning goal: Connect Markov-chain intuition to the broader language of stochastic processes, filtrations, martingales, and stopping times.
Key idea
A stochastic process is any indexed family of random variables. A filtration \((\mathcal F_n)\) records the information available by time \(n\). Martingale statements are conditional expectations relative to this information.
Conditional-expectation dictionary
Martingale: \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Submartingale: \(E[X_{n+1}\mid\mathcal F_n]\ge X_n\), so the conditional drift is nonnegative.
Supermartingale: \(E[X_{n+1}\mid\mathcal F_n]\le X_n\), so the conditional drift is nonpositive.
These are statements about conditional averages, not about every sample path increasing or decreasing.
Stopping times
A stopping time \(\tau\) must be decidable from information available up to time \(n\) when checking whether \(\tau\le n\). For example, the first time a process hits \(5\) is a stopping time; the last time before tomorrow that it hits \(5\) depends on future information.
Worked example
Example: Let \(S_n\) be a fair random walk with independent steps \(+1\) or \(-1\), each with probability \(1/2\). Why is \(S_n\) a martingale?
Given the current information, the next step has conditional mean \(0\). Therefore \(E[S_{n+1}\mid\mathcal F_n]=S_n+0=S_n\).
Try it
Try it: A martingale satisfies \(E[X_{n+1}\mid\mathcal F_n]=\) what?
Hint: A martingale has zero conditional drift from the present value.
Most mistakes mix conventions or ignore assumptions
Learning goal: Finish by separating transition-matrix facts, long-run facts, and conditional-expectation facts.
Common traps
Row versus column convention: this lesson uses row distributions \(pP\). With column distributions, formulas transpose.
Invalid matrix rows: probabilities must be nonnegative and each row must sum to \(1\).
Stationary is not absorbing: \(\pi P=\pi\) describes a distribution, not necessarily a fixed state.
Reducible chains can have many stationary distributions: closed classes can each support stationary mass.
Period can block convergence: the two-state switch has a stationary distribution but \(P^n\) oscillates.
Self-loop shortcut: \(P_{ii}>0\) gives period \(1\) for that recurrent class.
Transient is eventual: a transient state may be visited several times, but only finitely many times with probability \(1\).
Stopping times use available information: they cannot depend on unseen future outcomes.
Martingale means fair conditional mean: it does not mean the path stays constant.
Worked example
Example: Is the row \((1/4,1/4)\) valid as a complete transition row?
No. It is nonnegative, but its entries sum to \(1/2\), not \(1\). A complete transition row must assign total probability \(1\) across all next states.
Try it
Try it: A stopping time cannot depend on what?
Hint: At time \(n\), the decision must be based on information available by time \(n\).
Final recap
Markov property: the next-state law depends on the current state once the current state is known.
A transition matrix has nonnegative entries and rows summing to \(1\).
With row vectors, \(p_n=p_0P^n\).
Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Stationary distributions solve \(\pi P=\pi\) and \(\sum_i\pi_i=1\).
Identical rows send every current distribution to the common row; doubly stochastic finite chains preserve the uniform distribution; \(P=I\) preserves every distribution.
An absorbing state has \(P_{ii}=1\); a closed class cannot be left.
Irreducible means every state can reach every other state.
Period is the gcd of possible return times; a self-loop gives period \(1\).
Finite irreducible aperiodic chains converge to stationary rows.
Stopping times are decided from past and present information, not unseen future data.
Next step: Close this lesson and try the quiz again. For each question, first decide whether it is asking about one step, many steps, a stationary distribution, state classification, period, or conditional expectation.
Streak 5+
Streak 10+
Streak 15+
Streak 20+
Streak 25+