A Three-State Uniformization Calculation

From a Generator to Virtual Steps

A continuous-time Markov chain can make zero, one, or many state changes during a fixed time interval. Uniformization reorganizes this random evolution by placing potential transitions at the times of a Poisson process. Some potential transitions leave the state unchanged; these are called virtual steps. Conditional on there being exactly $n$ potential transitions, the state distribution is calculated using an ordinary discrete-time transition matrix raised to the $n$th power.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $(X_t)_{t\ge0}$ be a continuous-time Markov chain with finite state space $S=\{1,2,3\}$ and generator $Q=(q_{ij})$. A generator has $q_{ij}\ge0$ for $i\ne j$, and each row sums to zero. Write $q_i=-q_{ii}$ for the exit rate from state $i$. Choose a rate $\nu>0$ satisfying $\nu\ge\max_i q_i$, and define

R=I+\frac{Q}{\nu}.

The matrix $R$ describes one potential transition. Its off-diagonal entries give the probabilities of actual moves at that potential transition; its diagonal entries give the probabilities of staying in the current state.

Result (Uniformization mixture): If the chain starts with row distribution $\mu$, then its distribution at time $t$ is $$ \mu P(t)=\sum_{n=0}^{\infty}e^{-\nu t}\frac{(\nu t)^n}{n!}\,\mu R^n. $$ Here $N_t$, the number of potential transitions by time $t$, has a Poisson distribution with mean $\nu t$. Conditional on $N_t=n$, the distribution is $\mu R^n$. The uniformization formula is a standard result established in the earlier material on uniformization; the calculations below apply it term by term.

For clarity, the mixture also follows directly from conditioning. Construct a discrete-time Markov chain $(Y_n)_{n\ge0}$ with transition matrix $R$, independently of a Poisson process $(N_t)_{t\ge0}$ of rate $\nu$, and put $X_t=Y_{N_t}$. With the filtration $\mathcal{F}_t=\sigma(Y_0,\ldots,Y_{N_t},N_s:0\le s\le t)$, conditioning on the event $N_t=n$ gives the distribution $\mu R^n$. Since $\mathbb{P}(N_t=n)=e^{-\nu t}(\nu t)^n/n!$, summing over $n\ge0$ gives the displayed mixture. This representation is the reason each term has a fixed-step interpretation.

Why $R$ is a transition matrix. For each state $i$, its diagonal entry is $r_{ii}=1-q_i/\nu\ge0$, and for $j\ne i$, $r_{ij}=q_{ij}/\nu\ge0$. Also, using the zero row sum of $Q$,

\sum_j r_{ij}=1+\frac{1}{\nu}\sum_j q_{ij}=1.

Thus $R$ is row-stochastic. Its powers are row-stochastic as well: if $A$ and $B$ are row-stochastic, then their entries are nonnegative and $\sum_j(AB)_{ij}=\sum_k a_{ik}\sum_jb_{kj}=\sum_k a_{ik}=1$. Repeated multiplication applies this argument to every power $R^n$, including $R^0=I$.

Worked Example: Building the Three-State Step Matrix

Consider the generator, with states ordered as $1,2,3$,

Q= \begin{bmatrix} -3&2&1\\ 1&-3&2\\ 2&0&-2 \end{bmatrix}.

Before using it, check the generator rows: $-3+2+1=0$, $1-3+2=0$, and $2+0-2=0$. The off-diagonal entries are nonnegative. The exit rates are $q_1=3$, $q_2=3$, and $q_3=2$. Take $\nu=3$, which satisfies $\nu\ge\max_iq_i=3$. Then

R=I+\frac{Q}{3} = \begin{bmatrix} 0&\tfrac23&\tfrac13\\ \tfrac13&0&\tfrac23\\ \tfrac23&0&\tfrac13 \end{bmatrix}.

Check the rows before using $R$: $0+\tfrac23+\tfrac13=1$, $\tfrac13+0+\tfrac23=1$, and $\tfrac23+0+\tfrac13=1$. In state $2$, for example, every potential transition leads to a different state. In state $3$, a potential transition stays in state $3$ with probability $\tfrac13$.

To calculate two virtual steps, multiply rows of $R$ by $R$. The first row of $R^2$ is $\tfrac23$ times row $2$ of $R$, plus $\tfrac13$ times row $3$ of $R$: it is $(\tfrac49,0,\tfrac59)$. The second row is $\tfrac13$ times row $1$ plus $\tfrac23$ times row $3$: it is $(\tfrac49,\tfrac29,\tfrac13)$. The third row is $\tfrac23$ times row $1$ plus $\tfrac13$ times row $3$: it is $(\tfrac29,\tfrac49,\tfrac13)$. Therefore

R^2= \begin{bmatrix} \tfrac49&0&\tfrac59\\ \tfrac49&\tfrac29&\tfrac13\\ \tfrac29&\tfrac49&\tfrac13 \end{bmatrix}.

As a check, its row sums are $\tfrac49+0+\tfrac59=1$, $\tfrac49+\tfrac29+\tfrac13=1$, and $\tfrac29+\tfrac49+\tfrac13=1$. Starting from state $1$, the probability of being in state $3$ after exactly two virtual steps is $\tfrac59$.

Reading the First Poisson-Weighted Terms

Each matrix power is weighted by the probability of seeing that many potential transitions. For a fixed time $t$, put $m=\nu t$. The weight for $n$ virtual steps is $e^{-m}m^n/n!$. The first three terms, for $n=0,1,2$, are therefore $e^{-m}I$, $e^{-m}mR$, and $e^{-m}(m^2/2)R^2$. A finite sum of these terms includes only paths with at most two potential transitions; it is not the full transition matrix unless all omitted terms vanish.

The interpretation of each entry can be proved from the definition of a matrix product. For $n=0$, $R^0=I$, so no potential transition leaves the initial state unchanged. For $n\ge1$, $(R^n)_{ij}$ is the sum, over all state sequences $i=i_0,i_1,\ldots,i_n=j$, of the products $r_{i_0i_1}\cdots r_{i_{n-1}i_n}$. This holds for $n=1$ by the definition of $R$. If it holds for $n$, then $(R^{n+1})_{ij}=\sum_k(R^n)_{ik}r_{kj}$; substituting the path sum for $(R^n)_{ik}$ appends the final step from $k$ to $j$, giving exactly all paths of length $n+1$. This proves the interpretation by induction.

Worked Example: A State-Three Probability Through Two Steps

Use the generator and step matrix from the preceding calculation, start in state $1$, and take $t=\tfrac13$. Here $\nu=3$, so $m=\nu t=1$. The rows of $R$ sum to $1$, as checked above, and the rows of $R^2$ also sum to $1$, by the explicit checks above.

We calculate the contributions to the probability of being in state $3$ from $n=0,1,2$. With zero steps, the contribution is $e^{-1}(I)_{13}=0$. With one step, it is $e^{-1}R_{13}=e^{-1}\tfrac13$. With two steps, it is $e^{-1}\tfrac12(R^2)_{13}=e^{-1}\tfrac12\cdot\tfrac59$. Thus the sum through two steps is

e^{-1}\left(0+\frac13+\frac12\cdot\frac59\right) =e^{-1}\left(\frac{6}{18}+\frac{5}{18}\right) =\frac{11}{18}e^{-1}.

The two-step entry can also be checked by listing its possible paths from $1$ to $3$: $1\to2\to3$ has probability $\tfrac23\cdot\tfrac23=\tfrac49$, and $1\to3\to3$ has probability $\tfrac13\cdot\tfrac13=\tfrac19$. Their sum is $\tfrac49+\tfrac19=\tfrac59$, as in $R^2$. The calculation through $n=2$ is a partial contribution to the full probability; terms with $n\ge3$ remain.

Worked Example: A Three-Term Matrix at Time One

Keep the same generator and start with $\mu=(\tfrac12,\tfrac13,\tfrac16)$. The generator rows sum to zero and its off-diagonal entries are nonnegative, as checked in the first example. With $\nu=3$, the rows of $R$ sum to $1$, namely $0+\tfrac23+\tfrac13=1$, $\tfrac13+0+\tfrac23=1$, and $\tfrac23+0+\tfrac13=1$. At $t=1$, $m=3$, so the weights for $n=0,1,2$ are $e^{-3}$, $3e^{-3}$, and $\tfrac92e^{-3}$.

Using $R$ and $R^2$, the matrix inside this three-term partial sum is

C=I+3R+\frac92R^2 = \begin{bmatrix} 3&2&\tfrac72\\ 3&2&\tfrac72\\ 3&2&\tfrac72 \end{bmatrix}.

For instance, the first row is $(1,0,0)+(0,2,1)+(2,0,\tfrac52)=(3,2,\tfrac72)$. The second row is $(0,1,0)+(1,0,2)+(2,1,\tfrac32)=(3,2,\tfrac72)$, and the third is $(0,0,1)+(2,0,1)+(1,2,\tfrac32)=(3,2,\tfrac72)$. Each row sums to $3+2+\tfrac72=\tfrac{17}{2}$. This also equals the sum of the three unnormalized Poisson weights $1+3+\tfrac92=\tfrac{17}{2}$.

Multiplying by the initial row distribution gives $\mu C=(3,2,\tfrac72)$, since the entries of $\mu$ sum to $\tfrac12+\tfrac13+\tfrac16=1$. The distributional contribution from $n\le2$ is consequently $e^{-3}(3,2,\tfrac72)$. Its entries sum to $\tfrac{17}{2}e^{-3}$, exactly the probability $\mathbb{P}(N_1\le2)=e^{-3}(1+3+\tfrac92)$. It is a sub-probability row: the omitted mass is $\mathbb{P}(N_1\ge3)=1-\tfrac{17}{2}e^{-3}$, supplied by terms with three or more virtual steps.

Checks, Uses, and a Common Pitfall

These calculations are useful when the generator is sparse or when the first few terms already describe the transitions of interest. They also make the time dependence transparent: the matrix powers describe the possible state sequences, while the Poisson weights describe how many potential transitions occur by time $t$. A diagonal entry of $R$ must not be discarded merely because it represents no state change. Such an event is still one potential transition, so it affects which power $R^n$ is used and has its own Poisson weight.

Common mistake. One might calculate the two-step contribution at $t=\tfrac13$ as $\tfrac12(R^2)_{13}=\tfrac5{18}$, omitting the Poisson factor. That is the conditional probability of ending in state $3$ given exactly two potential transitions, not its contribution to the unconditional transition probability. The correct term is $\mathbb{P}(N_{1/3}=2)(R^2)_{13}=e^{-1}\tfrac12\cdot\tfrac59=\tfrac5{18}e^{-1}$. The distinction is between a conditional probability for a fixed number of steps and a Poisson-weighted contribution to the continuous-time probability.

When reporting a finite uniformization calculation, state which values of $n$ are included, keep the Poisson weight attached to each matrix power, and check the row sums. The full infinite mixture has row sums one because the Poisson probabilities sum to one and every $R^n$ is stochastic. A truncated mixture generally has row sums below one; the missing probability is precisely the Poisson mass of the omitted step counts.

Check Your Understanding

Use the generator and rate $\nu=3$ from the examples. In each calculation, distinguish a fixed-step probability from its Poisson-weighted contribution.

Compute the probability of going from state $2$ to state $1$ in exactly two virtual steps, and verify it using the two possible intermediate states.
At $t=\tfrac13$, what is the Poisson weight for exactly one virtual step? What is its contribution to the probability of going from state $1$ to state $3$?
Explain why the rows of $R^n$ sum to one for every nonnegative integer $n$, including $n=0$.
For the time-one calculation, what probability mass is omitted by keeping only the $n=0,1,2$ terms?
What error occurs if a diagonal entry of $R$ is set to zero whenever a potential transition leaves the state unchanged?

A Three-State Uniformization Calculation

What You'll Learn