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.[1]
Definition
Suppose that the complete state-space of a Markov chain is divided into disjoint subsets of states, where these subsets are denoted by ti. This forms a partition [math]\displaystyle{ \scriptstyle{T = \{ t_1, t_2, \ldots \}} }[/math] of the states. Both the state-space and the collection of subsets may be either finite or countably infinite. A continuous-time Markov chain [math]\displaystyle{ \{ X_i \} }[/math] is lumpable with respect to the partition T if and only if, for any subsets ti and tj in the partition, and for any states n,n’ in subset ti,
- [math]\displaystyle{ \sum_{m \in t_j} q(n,m) = \sum_{m \in t_j} q(n',m) , }[/math]
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 ti and tj in the partition, and for any states n,n’ in subset ti,
- [math]\displaystyle{ \sum_{m \in t_j} p(n,m) = \sum_{m \in t_j} p(n',m) , }[/math]
where p(i,j) is the probability of moving from state i to state j.[3]
Example
Consider the matrix
- [math]\displaystyle{ P = \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} }[/math]
and notice it is lumpable on the partition t = {(1,2),(3,4)} so we write
- [math]\displaystyle{ P_t = \begin{pmatrix} \frac{7}{8} & \frac{1}{8} \\ \frac{1}{16} & \frac{15}{16} \end{pmatrix} }[/math]
and call Pt 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
References
- ↑ Kemeny, John G.; Snell, J. Laurie (July 1976). Gehring, F. W.; Halmos, P. R.. eds. Finite Markov Chains (Second ed.). New York Berlin Heidelberg Tokyo: Springer-Verlag. pp. 124. ISBN 978-0-387-90192-3.
- ↑ Jane Hillston, 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
- ↑ Peter G. Harrison and Naresh M. Patel, Performance Modelling of Communication Networks and Computer Architectures Addison-Wesley 1992
- ↑ Katehakis, M. N.; Smit, L. C. (2012). "A Successive Lumping Procedure for a Class of Markov Chains". Probability in the Engineering and Informational Sciences 26 (4): 483. doi:10.1017/S0269964812000150.
- ↑ Franceschinis, G.; Muntz, Richard R. (1993). "Bounds for quasi-lumpable Markov chains". Performance Evaluation (Elsevier B.V.) 20 (1–3): 223–243. doi:10.1016/0166-5316(94)90015-9.
 |  |
