From a Transition Matrix to a Simulated Path
A transition matrix specifies the probability law of a Markov chain, but it does not by itself display a particular path. Simulation constructs paths by repeatedly turning those probabilities into choices. For a finite-state chain, the basic procedure is direct: sample the initial state from its distribution; at each later step, use a fresh uniform random number to select a next state from the row corresponding to the current state.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, let \(S=\{1,\ldots,m\}\) be a finite state space, and let \((X_n)_{n\ge0}\) be a discrete-time Markov chain. Write its initial distribution as the row vector \(\mu=(\mu_i)_{i\in S}\), where \(\mu_i\ge0\) and \(\sum_{i\in S}\mu_i=1\). Its transition matrix is \(P=(p_{ij})\), with \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\). The entry \(p_{ij}\) is the probability of moving from state \(i\) to state \(j\) in one step.
The state order used to form cumulative probabilities must be fixed in advance. The intervals are half-open: their left endpoints are included and their right endpoints are excluded. Together, the nonempty intervals partition \([0,1)\), including when some probabilities are zero. This convention also specifies what to do if a random number lands exactly on a cumulative boundary.
For the initial state, apply this rule to \((\mu_i)\). If the current state is \(i\), apply it to the row \((p_{ij})_{j\in S}\). The latter step must use the current state’s row, not a different row or a column of \(P\).
Generate \(U_0\) uniformly on \([0,1)\), and use the cumulative probabilities of \(\mu\) to set \(X_0\).
If \(X_n=i\), calculate the cumulative sums \(c_j=\sum_{\ell=1}^{j}p_{i\ell}\).
Generate a fresh \(U_{n+1}\), and choose the unique \(j\) with \(c_{j-1}\le U_{n+1}<c_j\). Repeat for each required step.
In a mathematical description, the uniforms are independent random variables, each uniform on \([0,1)\). A computer usually uses a pseudorandom number generator: a specified seed makes the resulting sequence reproducible, while the ideal probability argument below describes the target sampling procedure. The method is for a homogeneous chain with one fixed transition matrix \(P\).
Why the Procedure Gives the Correct Chain
Proof. For any probability vector \((a_1,\ldots,a_m)\), the interval assigned to index \(j\) is \([c_{j-1},c_j)\), whose length is \(c_j-c_{j-1}=a_j\). Thus a uniform random variable selects index \(j\) with probability \(a_j\); if \(a_j=0\), the interval is empty and that probability is zero.
Apply this first to \(\mu\). It gives \(\mathbb{P}(X_0=i_0)=\mu_{i_0}\). At step \(r\), conditional on the states generated through time \(r\), the next uniform \(U_{r+1}\) is independent of those states. The interval rule applied to the row indexed by \(X_r=i_r\) therefore gives \(\mathbb{P}(X_{r+1}=i_{r+1}\mid X_0=i_0,\ldots,X_r=i_r)=p_{i_r i_{r+1}}\) whenever the conditioning event has positive probability. Multiplying these conditional probabilities with the initial probability gives the displayed path probability. If any factor is zero, the corresponding transition interval is empty, and both the path probability and the product are zero. These path probabilities are exactly the defining finite-dimensional probabilities of the chain with initial distribution \(\mu\) and transition matrix \(P\). \(\square\)
For clarity, the conditioning in the proof is on the history \(\mathcal{F}_r=\sigma(X_0,\ldots,X_r)\). The fresh uniform used at the next step is independent of this history because the states in it were generated using only the initial and earlier transition uniforms. This is the role of using a new independent draw at every step.
Worked Paths
Worked Example: A Three-State Chain
Let \(S=\{1,2,3\}\), and use the initial distribution and transition matrix \(\mu=(\tfrac12,\tfrac13,\tfrac16)\) and \(P=\begin{bmatrix}\tfrac12&\tfrac13&\tfrac16\\[2pt]\tfrac14&\tfrac12&\tfrac14\\[2pt]0&\tfrac23&\tfrac13\end{bmatrix}\). Before simulating, check the rows: \(\tfrac12+\tfrac13+\tfrac16=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(0+\tfrac23+\tfrac13=1\). The initial probabilities also sum to \(\tfrac12+\tfrac13+\tfrac16=1\).
Use the supplied uniforms \(U_0=\tfrac35\), \(U_1=\tfrac15\), \(U_2=\tfrac34\), and \(U_3=\tfrac9{10}\). For the initial state, the cumulative probabilities are \(\tfrac12,\tfrac56,1\). Since \(\tfrac12\le\tfrac35<\tfrac56\), \(X_0=2\).
From state \(2\), the cumulative row probabilities are \(\tfrac14,\tfrac34,1\). Since \(0\le\tfrac15<\tfrac14\), \(U_1\) selects state \(1\), so \(X_1=1\). From state \(1\), the cumulative row probabilities are \(\tfrac12,\tfrac56,1\). Since \(\tfrac12\le\tfrac34<\tfrac56\), \(X_2=2\). From state \(2\) again, the cumulative probabilities are \(\tfrac14,\tfrac34,1\). Here \(\tfrac34\) is the left endpoint of the third interval, so \(\tfrac34\le\tfrac9{10}<1\) gives \(X_3=3\). The path is therefore \((2,1,2,3)\).
Check: Its path probability is \(\mu_2p_{21}p_{12}p_{23}=\tfrac13\cdot\tfrac14\cdot\tfrac13\cdot\tfrac14=\tfrac1{144}\). Each factor is the probability of the corresponding starting state or transition in the path.
Worked Example: A Uniform Exactly on a Boundary
Consider \(S=\{1,2\}\), \(\mu=(1,0)\), and \(P=\begin{bmatrix}\tfrac12&\tfrac12\\[2pt]\tfrac13&\tfrac23\end{bmatrix}\). Both rows sum to \(1\): \(\tfrac12+\tfrac12=1\) and \(\tfrac13+\tfrac23=1\); the initial probabilities sum to \(1+0=1\).
Use \(U_0=\tfrac23\), \(U_1=\tfrac12\), \(U_2=\tfrac13\), and \(U_3=0\). The initial cumulative probabilities are \(1,1\), so the interval for state \(1\) is \([0,1)\) and the interval for state \(2\) is empty. Thus \(X_0=1\). From state \(1\), the intervals are \([0,\tfrac12)\) for state \(1\) and \([\tfrac12,1)\) for state \(2\). The boundary value \(U_1=\tfrac12\) belongs to the second interval, giving \(X_1=2\).
From state \(2\), the intervals are \([0,\tfrac13)\) for state \(1\) and \([\tfrac13,1)\) for state \(2\). Since \(U_2=\tfrac13\) is included at the left endpoint of the second interval, \(X_2=2\). On the next draw from state \(2\), \(U_3=0\) lies in \([0,\tfrac13)\), so \(X_3=1\). The resulting path is \((1,2,2,1)\).
Check: Its probability is \(\mu_1p_{12}p_{22}p_{21}=1\cdot\tfrac12\cdot\tfrac23\cdot\tfrac13=\tfrac19\). The zero initial probability for state \(2\) causes no problem: its initial interval is empty, and it is never chosen at time zero.
Worked Example: Zero Transitions and an Absorbing State
Take \(S=\{1,2,3\}\), \(\mu=(0,1,0)\), and \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\[2pt]0&\tfrac13&\tfrac23\\[2pt]0&0&1\end{bmatrix}\). The row sums are \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac13+\tfrac23=1\), and \(0+0+1=1\); the initial probabilities sum to \(0+1+0=1\). State \(3\) is absorbing because its transition probability to itself is \(1\).
Use \(U_0=\tfrac25\), \(U_1=\tfrac45\), \(U_2=\tfrac1{10}\), and \(U_3=\tfrac{99}{100}\). The initial intervals for states \(1,2,3\) are \([0,0)\), \([0,1)\), and \([1,1)\), respectively. Thus \(X_0=2\). From state \(2\), the cumulative probabilities are \(0,\tfrac13,1\); because \(\tfrac13\le\tfrac45<1\), \(X_1=3\). From state \(3\), the cumulative probabilities are \(0,0,1\), so every \(U\in[0,1)\) selects state \(3\). Therefore \(X_2=X_3=3\), and the path is \((2,3,3,3)\).
Check: The probability of this path is \(\mu_2p_{23}p_{33}p_{33}=1\cdot\tfrac23\cdot1\cdot1=\tfrac23\). The zero entries in the rows create empty intervals, while the absorbing row leaves the chain at state \(3\) for every possible uniform draw.
Implementation Details and a Common Mistake
For a small state space, one can scan a row’s cumulative sums from left to right and stop at the first cumulative sum strictly greater than \(U\). Equivalently, choose \(j\) when \(c_{j-1}\le U<c_j\). The strict inequality at the right endpoint is important: at a cumulative boundary, the draw moves into the next interval. If a row contains zero entries, repeated cumulative sums simply indicate empty intervals. Since each row sums to \(1\), its final cumulative sum is exactly \(1\), so every \(U\in[0,1)\) selects a state.
Common mistake: using the wrong row or including the right endpoint. In the first example, suppose the current state is \(2\) and \(U=\tfrac34\). The correct row has cumulative probabilities \(\tfrac14,\tfrac34,1\), so \(\tfrac34\) selects state \(3\): the second interval excludes its right endpoint. If one mistakenly uses row \(1\), whose cumulative probabilities are \(\tfrac12,\tfrac56,1\), the same number selects state \(2\). That produces the wrong transition law. Always identify the current state first, then use its row and the half-open interval rule.
A simulated path is one realization, not a list of all possibilities. Changing the uniforms generally changes the path, while the probability law remains determined by \(\mu\) and \(P\). The proof above is what guarantees that the procedure reproduces the desired chain law; the examples show how to implement the rule carefully, including at exact boundaries and in the presence of zero transition probabilities.
Check Your Understanding
For each question, use cumulative intervals with the left endpoint included and the right endpoint excluded.
- For probabilities \((\tfrac14,\tfrac34)\), which state is selected by \(U=\tfrac14\)?
- For the row \((0,\tfrac25,\tfrac35)\), write the three sampling intervals and state what happens when \(U=0\).
- Suppose the current state is \(i\). Which entries of \(P\) determine the next-state intervals, and why must a fresh uniform draw be used?
- For \(\mu=(\tfrac12,\tfrac12)\) and \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\), describe the path when \(U_0=\tfrac34\), \(U_1=0\), and \(U_2=\tfrac12\).
- Explain why a transition with probability zero cannot be selected by the cumulative-interval method.