lumpability

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 $\backslash scriptstyle\{T\; =\; \backslash \{\; t\_1,\; t\_2,\; \backslash ldots\; \backslash \}\}$ of the states. Both the state-space and the collection of subsets may be either finite or countably infinite.

A continuous-time Markov chain $\backslash \{\; X\_i\; \backslash \}$ 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,

: $\backslash sum\_\{m\; \backslash in\; t\_j\}\; q(n,m)\; =\; \backslash sum\_\{m\; \backslash in\; t\_j\}\; q(n\text{'},m)\; ,$

where q(i,j) is the transition rate from state i to state j.Jane Hillston, [http://www.dcs.ed.ac.uk/pepa/compositional.ps.gz Compositional Markovian Modelling Using A Process Algebra] in the Proceedings of the Second International Workshop on Numerical Solution of Markov Chains: Computations with Markov Chains, Raleigh, North Carolina, January 1995. Kluwer Academic Press

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,

: $\backslash sum\_\{m\; \backslash in\; t\_j\}\; p(n,m)\; =\; \backslash sum\_\{m\; \backslash in\; t\_j\}\; p(n\text{'},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

Consider the matrix

: $P\; =\; \backslash begin\{pmatrix\}$

\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{pmatrix}

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

: $P\_t\; =\; \backslash begin\{pmatrix\}$

\frac{7}{8} & \frac{1}{8} \\

\frac{1}{16} & \frac{15}{16} \end{pmatrix}

and call P_t the lumped matrix of P on t.

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.{{Cite journal | last1 = Katehakis | first1 = M. N. | author-link1 = Michael Katehakis| last2 = Smit | first2 = L. C. | doi = 10.1017/S0269964812000150 | title = A Successive Lumping Procedure for a Class of Markov Chains | journal = Probability in the Engineering and Informational Sciences | volume = 26 | issue = 4 | pages = 483 | year = 2012 }}

Franceschinis and Muntz introduced quasi-lumpability, a property whereby a small change in the rate matrix makes the chain lumpable.{{cite journal |last1=Franceschinis |first1=G. |last2=Muntz |first2=Richard R. |year=1993 |title=Bounds for quasi-lumpable Markov chains |journal=Performance Evaluation |publisher=Elsevier B.V. |volume=20 |issue=1–3 |pages=223–243 |doi=10.1016/0166-5316(94)90015-9}}

• Nearly completely decomposable Markov chain

{{Reflist}}

Category:Markov processes