HOME

TheInfoList



OR:

In
probability theory Probability theory is the branch of mathematics concerned with probability. Although there are several different probability interpretations, probability theory treats the concept in a rigorous mathematical manner by expressing it through a set o ...
, 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 A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happe ...
is divided into disjoint subsets of states, where these subsets are denoted by ''ti''. This forms a
partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
\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 ''ti'' and ''tj'' in the partition, and for any states ''n,n’'' in subset ''ti'', : \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 ''ti'' and ''tj'' in the partition, and for any states ''n,n’'' in subset ''ti'', : \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