Uniformization of CTMC

Definition

Let

• $\{X(t),t\ge 0\}$ a continuous-time Markov chain with transition rate matrix $\mathbf{Q}$ and state-dependent departure rates $v_i={\sum }_{j\ne i}{q}_{ij}$
• $\gamma$ a constant satisfying $\gamma \ge {\sup }_i{v}_i$

Uniformization (or randomization) is a technique that converts the CTMC into a Poisson process of rate $\gamma$ driving transitions in a discrete-time Markov chain with one-step transition matrix ${\mathbf{P}}^{\ast }$.

Interpretation

Instead of having each state with its own exponential holding time parameter $v_i$, we “level the playing field” — events occur at a uniform rate $\gamma$ everywhere. At each event, the chain either makes a real transition (probability $v_i/\gamma$) or stays put (probability $1-v_i/\gamma$). This decouples the timing from the state transitions, making numerical computation tractable.

Uniformized Transition Matrix

Define the uniformized discrete-time transition matrix ${\mathbf{P}}^{\ast }$:

$$P_{ij}^{\ast }=\{\begin{array}{ll}\frac{q_{ij}}{\gamma }=\frac{v_i{P}_{ij}}{\gamma },& i\ne j\\ 1-\frac{v_i}{\gamma },& i=j\end{array}$$

where $P_{ij}$ are the transition probabilities of the embedded Markov chain.

Equivalently, in matrix form:

$${\mathbf{P}}^{\ast }=\mathbf{I}+\frac{1}{\gamma }\mathbf{Q}$$

Transition Probability via Uniformization

The transition probability matrix $\mathbf{P}(t)$ is given by:

$$\boxed{\mathbf{P}(t)=e^{\mathbf{Q}t}=\sum _{n=0}^{\infty }{e}^{-\gamma t}\frac{(\gamma t{)}^n}{n!}({\mathbf{P}}^{\ast }{)}^n}$$

The interpretation: $N\sim \text{Poisson}(\gamma t)$ events occur by time $t$. Given $N=n$ events, the state after $n$ transitions of the uniformized DTMC follows $({\mathbf{P}}^{\ast }{)}^n$. A weighted sum over all possible numbers of Poisson events yields $\mathbf{P}(t)$.

Procedure

1. Compute $v_i={\sum }_{j\ne i}{q}_{ij}$ for each state $i$
2. Choose $\gamma \ge {\max }_i{v}_i$ (typically $\gamma ={\max }_i{v}_i$; larger $\gamma$ gives faster convergence but more terms)
3. Construct ${\mathbf{P}}^{\ast }=\mathbf{I}+\frac{1}{\gamma }\mathbf{Q}$
4. For a given $t$, truncate the series at $n=N$ where $e^{-\gamma t}(\gamma t{)}^N/N!<ϵ$ (e.g., $ϵ=10^{-8}$)
5. Compute $\mathbf{P}(t)$ via the weighted sum

Properties

Property	Description
Decouples timing	Transitions occur at Poisson rate $\gamma$, independent of the current state
Self-loops	$P_{ii}^{\ast }>0$ when $v_i<\gamma$ — these are “fictitious” transitions where the chain stays in place
Numerical stability	Converges faster than direct matrix exponentiation for moderate $t$
Stochasticity	${\mathbf{P}}^{\ast }$ is a valid stochastic matrix (row sums = 1, entries $\ge 0$)

Related

• Matrix Exponential
• Kolmogorov Differential Equations
• Embedded Markov Chain

Exercises

Back to Roadmap 📖 → 🃏 → ✏

Terapkan uniformization. Untuk $Q=\left[\begin{array}{ccc}-2& 2& 0\\ 1& -3& 2\\ 0& 2& -2\end{array}\right]$:

(a) Tentukan $\gamma$ yang sesuai.

Jawaban: ${\nu }_0=2$, ${\nu }_1=3$, ${\nu }_2=2$. $\gamma ={\max }_i{\nu }_i=3$.

(b) Konstruksi ${\mathbf{P}}^{\ast }=I+\frac{1}{\gamma }Q$.

Jawaban: ${\mathbf{P}}^{\ast }=\left[\begin{array}{ccc}1-\frac{2}{3}& \frac{2}{3}& 0\\ \frac{1}{3}& 1-\frac{3}{3}& \frac{2}{3}\\ 0& \frac{2}{3}& 1-\frac{2}{3}\end{array}\right]=\left[\begin{array}{ccc}1/3& 2/3& 0\\ 1/3& 0& 2/3\\ 0& 2/3& 1/3\end{array}\right]$.

(c) Interpretasi $P_{11}^{\ast }=0$ dan $P_{00}^{\ast }=1/3$.

Jawaban: $P_{11}^{\ast }=0$ karena ${\nu }_1=\gamma =3$, jadi semua event Poisson di state 1 menghasilkan transisi riil. $P_{00}^{\ast }=1/3$ adalah “fictitious transition” — proses tetap di state 0 dengan probabilitas $1-{\nu }_0/\gamma =1/3$.