Build a Transition Matrix from a Verbal Model

From a Verbal Rule to a Matrix

A verbal model usually describes what can happen next, not a matrix. To construct the matrix, first decide exactly what counts as the state; then, for each possible current state, list the possible next states and their probabilities. The matrix is a compact record of those one-step conditional probabilities. Getting the matrix right depends on making the state definition and the timing of the update just as precise as the arithmetic.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). A finite-state process \((X_n)_{n\ge0}\) has state space \(S\), and its natural filtration is \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). It is a time-homogeneous Markov chain with transition matrix \(P=(p_{ij})\) if, for every \(n\ge0\) and \(j\in S\),

\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}\quad\text{almost surely},

where \(p_{ij}\) does not depend on \(n\). We use the row-stochastic convention: \(p_{ij}\) is the probability of moving from state \(i\) to state \(j\), so each row is indexed by the current state and each column by the next state.

Definition: To build a transition matrix from a verbal model, specify a state space \(S\), fix an ordering of its states, and for each current state \(i\) calculate \(p_{ij}=\mathbb{P}(X_{n+1}=j\mid X_n=i)\) for every next state \(j\). The resulting array is a transition matrix only if every entry is nonnegative and every row sums to \(1\). For a Markov-chain model, the one-step conditional probabilities given the full observed past must also depend only on the current state and must be the same at each time.

The conditional probability given \(X_n=i\) is directly defined by a ratio when \(\mathbb{P}(X_n=i)>0\). A model may also prescribe its transition rule from a state that has probability zero of being visited under a particular initial distribution. In that case the row is part of the specified transition kernel, rather than a conditional probability identified by that ratio. State rules should be defined for every state in \(S\).

A Reliable Construction Procedure

Choose the state variable.
State what information \(X_n\) records at time \(n\), and list all possible values. Include enough information so that the rule for the next state does not need extra information from the past.

Fix the timing.
Specify what happens during one time step and in what order. If two events can occur in a step, say whether they are simultaneous or sequential.

Build one row at a time.
For each current state, identify every possible next state. Add probabilities when different outcomes of the underlying events produce the same next state.

Choose and state an ordering.
Use the same ordering for rows and columns. A matrix has no unambiguous state labels without this convention.

Check the model and the arithmetic.
Verify that each entry is nonnegative and that each row sums to \(1\). Also ask whether the state definition makes the one-step rule depend only on the current state.

Proposition: Suppose that, at each step, the next state is determined by the current state and a fresh random input whose distribution is the same at every step and independent of the observed history. If the update rule is defined for every state, then the process is a time-homogeneous Markov chain. Its transition probabilities are obtained by summing the probabilities of all random-input outcomes that produce each next state.

Proof. Let the fresh input at step \(n+1\) be \(U_{n+1}\), and write the update rule as \(X_{n+1}=g(X_n,U_{n+1})\). Assume \(U_{n+1}\) is independent of \(\mathcal{F}_n\) and has the same distribution at every step. For fixed states \(i,j\), define \(p_{ij}=\mathbb{P}(g(i,U_{n+1})=j)\); this value does not depend on \(n\). On the event \(X_n=i\), the event \(X_{n+1}=j\) is exactly \(g(i,U_{n+1})=j\). Independence of \(U_{n+1}\) from \(\mathcal{F}_n\) therefore gives \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{ij}\) whenever \(X_n=i\), almost surely. Combining the cases \(i\in S\) gives \(\mathbb{P}(X_{n+1}=j\mid\mathcal{F}_n)=p_{X_nj}\) almost surely. Finally, the events \(\{g(i,U_{n+1})=j\}\), as \(j\) ranges over the state space, are disjoint and cover all outcomes because the update rule always returns a state in \(S\). Their probabilities are nonnegative and sum to \(1\). Thus the rows are stochastic, and the conditional probabilities do not depend on time. \(\square\)

Worked Constructions

Worked Example: Daily Activity Categories

A person's daily activity is recorded as \(Q\) (quiet), \(M\) (moderate), or \(A\) (active). Each day, the next category is selected using probabilities determined by the current category: from \(Q\), the probabilities of \(Q,M,A\) are \(\tfrac12,\tfrac13,\tfrac16\); from \(M\), they are \(\tfrac14,\tfrac12,\tfrac14\); and from \(A\), they are \(\tfrac16,\tfrac13,\tfrac12\). Construct the transition matrix in the order \(Q,M,A\).

The state records the category on the current day. The verbal rules directly give one-step probabilities, with no additional event ordering to resolve. Taking the listed state order for rows and columns gives

P= \begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac14&\tfrac12&\tfrac14\\ \tfrac16&\tfrac13&\tfrac12 \end{bmatrix}.

Row checks: the row for \(Q\) sums to \(\tfrac12+\tfrac13+\tfrac16=\tfrac36+\tfrac26+\tfrac16=1\). The row for \(M\) sums to \(\tfrac14+\tfrac12+\tfrac14=\tfrac14+\tfrac24+\tfrac14=1\). The row for \(A\) sums to \(\tfrac16+\tfrac13+\tfrac12=\tfrac16+\tfrac26+\tfrac36=1\). Each entry is nonnegative, so this is a transition matrix. The verbal model makes a time-homogeneous Markov chain if the day's selection rule uses only the current category and fresh randomness independent of earlier days.

Worked Example: A Queue with Capacity Two

At the beginning of each time slot, a queue contains \(i\in\{0,1,2\}\) customers. During a slot, a service attempt occurs first if the queue is nonempty; it succeeds with probability \(\mu=\tfrac12\). Then one potential arrival occurs with probability \(\lambda=\tfrac13\), independently of service. Arrivals that would exceed capacity two are rejected. Let \(X_{n+1}\) be the queue length at the beginning of the next slot. Construct \(P\) in the order \(0,1,2\).

The order matters: service happens before arrival. From state \(0\), there is no service, so the next queue length is \(0\) with probability \(1-\lambda=\tfrac23\), and \(1\) with probability \(\lambda=\tfrac13\). Thus the first row is \((\tfrac23,\tfrac13,0)\), which sums to \(\tfrac23+\tfrac13+0=1\).

From state \(1\), successful service followed by no arrival gives next state \(0\), with probability \(\mu(1-\lambda)=\tfrac12\cdot\tfrac23=\tfrac13\). Successful service followed by an arrival gives next state \(1\), with probability \(\mu\lambda=\tfrac12\cdot\tfrac13=\tfrac16\). Failed service followed by no arrival also gives next state \(1\), with probability \((1-\mu)(1-\lambda)=\tfrac12\cdot\tfrac23=\tfrac13\). Failed service followed by an arrival gives next state \(2\), with probability \((1-\mu)\lambda=\tfrac12\cdot\tfrac13=\tfrac16\). Combining the two outcomes leading to state \(1\), the second row is \((\tfrac13,\tfrac16+\tfrac13,\tfrac16)=(\tfrac13,\tfrac12,\tfrac16)\). It sums to \(\tfrac13+\tfrac12+\tfrac16=\tfrac26+\tfrac36+\tfrac16=1\).

From state \(2\), successful service followed by no arrival leaves one customer, with probability \(\mu(1-\lambda)=\tfrac13\). Successful service followed by an arrival restores the queue to capacity, with probability \(\mu\lambda=\tfrac16\). If service fails, the queue remains at capacity whether or not an arrival occurs; the combined probability is \(1-\mu=\tfrac12\). The last row is therefore \((0,\tfrac13,\tfrac16+\tfrac12)=(0,\tfrac13,\tfrac23)\), whose sum is \(0+\tfrac13+\tfrac23=1\). The complete matrix is

P= \begin{bmatrix} \tfrac23&\tfrac13&0\\ \tfrac13&\tfrac12&\tfrac16\\ 0&\tfrac13&\tfrac23 \end{bmatrix}.

Every entry is nonnegative, and all three row sums have been checked. The state is sufficient because, given the current queue length, the service and arrival rules determine the next queue length without needing earlier queue lengths.

Worked Example: A Bounded Account Balance

An account balance is recorded in units as \(0,1,\) or \(2\). In each period, a credit of one unit occurs with probability \(\tfrac14\), a debit of one unit occurs with probability \(\tfrac12\), and no transaction occurs with probability \(\tfrac14\). These three outcomes are mutually exclusive. A debit when the balance is zero leaves it at zero; a credit when the balance is two leaves it at two. Construct the transition matrix in the order \(0,1,2\).

From balance \(0\), a debit or no transaction leaves the balance at \(0\), with combined probability \(\tfrac12+\tfrac14=\tfrac34\), while a credit moves it to \(1\) with probability \(\tfrac14\). The first row is \((\tfrac34,\tfrac14,0)\), with sum \(\tfrac34+\tfrac14+0=1\).

From balance \(1\), a debit, no transaction, or credit leads respectively to \(0,1,2\), so the second row is \((\tfrac12,\tfrac14,\tfrac14)\). Its sum is \(\tfrac12+\tfrac14+\tfrac14=1\). From balance \(2\), a debit moves to \(1\) with probability \(\tfrac12\), while a credit or no transaction leaves the balance at \(2\), with combined probability \(\tfrac14+\tfrac14=\tfrac12\). The last row is \((0,\tfrac12,\tfrac12)\), with sum \(0+\tfrac12+\tfrac12=1\). Hence

P= \begin{bmatrix} \tfrac34&\tfrac14&0\\ \tfrac12&\tfrac14&\tfrac14\\ 0&\tfrac12&\tfrac12 \end{bmatrix}.

As a check on the boundary handling, the debit at balance \(0\) contributes to the entry \(p_{00}\), not to a nonexistent state \(-1\); similarly, the credit at balance \(2\) contributes to \(p_{22}\), not to a state \(3\). Every row is nonnegative and sums to \(1\). The model is Markov if transaction probabilities are independent of the past given the current balance.

Why the Matrix Is Determined by the Ordering

Proposition: Once the state labels and their ordering are fixed, the verbal model determines at most one transition matrix. If the ordering is changed, rows and columns must both be relabelled according to the new ordering; changing only one does not represent the same transition rule.

Proof. Fix an ordering \(s_1,\ldots,s_m\) of the finite state space. By definition, the entry in row \(r\), column \(c\) must be the one-step probability of moving from \(s_r\) to \(s_c\). The verbal model fixes that conditional probability for each ordered pair, so any matrix representing the model must have exactly those entries. Thus there is at most one such matrix. Now let \(t_1,\ldots,t_m\) be a different ordering of the same states. The entry in row \(r\), column \(c\) under the new ordering must be the probability of moving from \(t_r\) to \(t_c\). Both the current-state label and next-state label have changed positions; relabelling only rows would make columns refer to the wrong next states, and relabelling only columns would make rows refer to the wrong current states. Therefore a valid reordered representation must relabel both dimensions. \(\square\)

This is why a matrix should always be accompanied by its state ordering. The entries alone do not say which real-world condition a row or column represents. Also, a row summing to one checks that the listed outcomes form a probability distribution, but does not by itself establish that the chosen state is sufficient for the Markov property.

Common Pitfall: Reversing Rows and Columns

For the account-balance model, the probability of moving from \(1\) to \(0\) is \(\tfrac12\), while the probability of moving from \(0\) to \(1\) is \(\tfrac14\). The correct matrix records these in \(p_{10}\) and \(p_{01}\), respectively. A common wrong calculation is to write the column for each current state, producing the transpose of the correct matrix:

\begin{bmatrix} \tfrac34&\tfrac12&0\\ \tfrac14&\tfrac14&\tfrac12\\ 0&\tfrac14&\tfrac12 \end{bmatrix}.

This wrong array happens to have rows summing to \(1\): \(\tfrac34+\tfrac12+0\) does not, in fact, equal \(1\), so the first row check already catches the error: \(\tfrac34+\tfrac12=\tfrac54\). The correction is to keep current states as rows and next states as columns, giving the previously derived matrix. A row-sum check is necessary, though not sufficient: some transposed matrices may also have rows summing to one, so verify an entry against its verbal meaning as well.

Before accepting a constructed matrix, ask three questions: Does each state contain the information needed for the next-step rule? Have all event outcomes, including boundary cases, been assigned to a next state? Does the entry in row \(i\), column \(j\) mean the probability of moving from \(i\) to \(j\)? These checks distinguish a correct model from an array that merely looks plausible.

Check Your Understanding

For each question, state the state ordering you use and check any row sums exactly.

A two-state process has states \(L,H\). From \(L\), the next state is \(L\) with probability \(\tfrac23\); from \(H\), it is \(L\) with probability \(\tfrac14\). Write the transition matrix.
In a finite-capacity queue, why must the rule specify whether service or arrival occurs first when both can happen in one time slot?
For the account-balance model, identify the event outcomes that combine in the entry \(p_{00}\), and compute that entry.
Can a matrix have every row sum to \(1\) even if its rows and columns are assigned the wrong state labels? Explain what additional check is needed.
State the condition on a random update rule that makes the resulting process time-homogeneous Markov.