Lumpable Markov Chain

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 $\scriptstyle$ of the states. Both the state-space and the collection of subsets may be either finite or countably infinite.
A continuous-time Markov chain $\$ 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_ q(n,m) = \sum_ q(n',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_ p(n,m) = \sum_ p(n',m) ,$

where ''p''(''i,j'') is the probability of moving from state ''i'' to state ''j''. Peter G. Harrison and Naresh M. Patel, ''Performance Modelling of Communication Networks and Computer Architectures'' Addison-Wesley 1992

Example

Consider the matrix

: $P = \begin \frac & \frac & \frac & \frac \\ \frac & \frac & 0 & \frac \\ \frac & 0 & \frac & \frac \\ 0 & \frac & \frac & \frac \end$

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

: $P_t = \begin \frac & \frac \\ \frac & \frac \end$

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

References

{{Reflist

Markov processes