Uniformization (probability theory)

In probability theory, uniformization method, (also known as Jensen's method or the randomization method) is a method to compute transient solutions of finite state continuous-time Markov chains. The method involves the constructions of an analgous discrete time Markov chain, where transitions occur according to an exponential distribution with the same parameter in every state. This parameter, γ, is the same in all states hence the name uniformisation. The method is simple to program and efficiently calculates an approximation to the transient distribution at a single point in time (near zero). The method was first introduced by Grassman in 1977.

Method description

For a continuous time Markov chain with transition rate matrix Q, the uniformized discrete time Markov chain has probability transition matrix P is defined to be

$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

$\gamma \geq \max _{i}|\sum _{j}q_{ij}|.$

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

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

In practice this series is terminated after finitely many terms.

Implementation

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