Lumpability Explained

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.^[1]

Definition

\scriptstyle{T = \{ t _{1,} t _{2,} \ldots \}} 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',m) ,

where q(i,j) is the transition rate from state i to state j.^[2]

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',m) ,

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

Example

Consider the matrix

P = \begin{pmatrix} (1)/(2) & (3)/(8) & (1)/(16) & (1)/(\\ 16) (7)/(16) & (7)/(16) & 0 & (1)/(\\ 8) (1)/(16) & 0 & (1)/(2) & (7)/(16) \\ 0 & (1)/(16) & (3)/(8) & (9)/(16) \end{pmatrix}

and notice it is lumpable on the partition t =  so we write

P _{t} = \begin{pmatrix} (7)/(8) & (1)/(\\ 8) (1)/(16) & (15)/(16) \end{pmatrix}

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.^[4]

Quasi–lumpability

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

See also

• Nearly completely decomposable Markov chain

Notes and References

1. Book: Kemeny , John G. . John George Kemeny. J. Laurie. Snell. F. W.. Gehring. P. R.. Halmos. Finite Markov Chains. Second. 1960. July 1976. Springer-Verlag. New York Berlin Heidelberg Tokyo. 978-0-387-90192-3. 124.
2. [Jane Hillston]
3. [Peter Harrison (computer scientist)|Peter G. Harrison]
4. Katehakis . M. N. . Michael Katehakis. Smit . L. C. . 10.1017/S0269964812000150 . A Successive Lumping Procedure for a Class of Markov Chains . Probability in the Engineering and Informational Sciences . 26 . 4 . 483 . 2012 .
5. Franceschinis . G. . Muntz . Richard R. . 1993 . Bounds for quasi-lumpable Markov chains . . Elsevier B.V. . 20 . 1–3 . 223–243 . 10.1016/0166-5316(94)90015-9.