Misplaced Pages

Lumpability

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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 ti. This forms a partition T = { t 1 , t 2 , … } {\displaystyle \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 } {\displaystyle \{X_{i}\}} 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,

∑ m ∈ t j q ( n , m ) = ∑ m ∈ t j q ( n ′ , m ) , {\displaystyle \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.

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,

∑ m ∈ t j p ( n , m ) = ∑ m ∈ t j p ( n ′ , m ) , {\displaystyle \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.

Example

Consider the matrix

P = ( 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 ) {\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}}}

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

P t = ( 7 8 1 8 1 16 15 16 ) {\displaystyle P_{t}={\begin{pmatrix}{\frac {7}{8}}&{\frac {1}{8}}\\{\frac {1}{16}}&{\frac {15}{16}}\end{pmatrix}}}

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.

Quasi–lumpability

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

See also

References

  1. 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. p. 124. ISBN 978-0-387-90192-3.
  2. 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
  3. Peter G. Harrison and Naresh M. Patel, Performance Modelling of Communication Networks and Computer Architectures Addison-Wesley 1992
  4. 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.
  5. Franceschinis, G.; Muntz, Richard R. (1993). "Bounds for quasi-lumpable Markov chains". Performance Evaluation. 20 (1–3). Elsevier B.V.: 223–243. doi:10.1016/0166-5316(94)90015-9.
Category: