Lumpability

In probability theory, lumpability is a method for reducing the size of the state space of some continuous-time Markov chains, first published by Kemeny and Snell.

Definition

Suppose that the complete state-space of a Markov chain is divided into disjoint subsets of states, where these subsets are denoted by t_i. This forms a partition $T=\{t_1,t_2,\dots \}$ of the states. Both the state-space and the collection of subsets may be either finite or countably infinite. A continuous-time Markov chain $\{X_i\}$ is lumpable with respect to the partition T if and only if, for any subsets t_i and t_j in the partition, and for any states n,n’ in subset t_i,

$\sum _{m\in t_j}q(n,m)=\sum _{m\in t_j}q(n^{\prime },m),$

where q(i,j) is the transition rate from state i to state j.

Similarly, for a stochastic matrix P, P is a lumpable matrix on a partition T if and only if, for any subsets t_i and t_j in the partition, and for any states n,n’ in subset t_i,

$\sum _{m\in t_j}p(n,m)=\sum _{m\in t_j}p(n^{\prime },m),$

where p(i,j) is the probability of moving from state i to state j.

Example

Consider the matrix

$P=\left(\begin{array}{cccc}\frac{1}{2}& \frac{3}{8}& \frac{1}{16}& \frac{1}{16}\\ \frac{7}{16}& \frac{7}{16}& 0& \frac{1}{8}\\ \frac{1}{16}& 0& \frac{1}{2}& \frac{7}{16}\\ 0& \frac{1}{16}& \frac{3}{8}& \frac{9}{16}\end{array}\right)$

and notice it is lumpable on the partition t = {(1,2),(3,4)} so we write

$P_t=\left(\begin{array}{cc}\frac{7}{8}& \frac{1}{8}\\ \frac{1}{16}& \frac{15}{16}\end{array}\right)$

and call P_t the lumped matrix of P on t.

Successively lumpable processes

In 2012, Katehakis and Smit discovered the Successively Lumpable processes for which the stationary probabilities can be obtained by successively computing the stationary probabilities of a propitiously constructed sequence of Markov chains. Each of the latter chains has a (typically much) smaller state space and this yields significant computational improvements. These results have many applications reliability and queueing models and problems.

Quasi–lumpability

Franceschinis and Muntz introduced quasi-lumpability, a property whereby a small change in the rate matrix makes the chain lumpable.

See also

• Nearly completely decomposable Markov chain