Uniformization (probability theory)

For a continuous-time Markov chain with transition rate matrix Q, the uniformized discrete-time Markov chain has probability transition matrix ${\displaystyle P:=(p_{ij})_{i,j}}$, which is defined by[1][6][7]

${\displaystyle p_{ij}={\begin{cases}q_{ij}/\gamma &{\text{ if }}i\neq j\\1-\sum _{j\neq i}q_{ij}/\gamma &{\text{ if }}i=j\end{cases}}}$

with γ, the uniform rate parameter, chosen such that

${\displaystyle \gamma \geq \max _{i}|q_{ii}|.}$

In matrix notation:

${\displaystyle P=I+{\frac {1}{\gamma }}Q.}$

For a starting distribution π(0), the distribution at time t, π(t) is computed by[1]

${\displaystyle \pi (t)=\sum _{n=0}^{\infty }\pi (0)P^{n}{\frac {(\gamma t)^{n}}{n!}}e^{-\gamma t}.}$

This representation shows that a continuous-time Markov chain can be described by a discrete Markov chain with transition matrix P as defined above where jumps occur according to a Poisson process with intensity γt.

In practice this series is terminated after finitely many terms.

Pseudocode for the algorithm is included in Appendix A of Reibman and Trivedi's 1988 paper.[8] Using a parallel version of the algorithm, chains with state spaces of larger than 10⁷ have been analysed.[9]

Reibman and Trivedi state that "uniformization is the method of choice for typical problems," though they note that for stiff problems some tailored algorithms are likely to perform better.[8]

• Matlab implementation