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 ''t
i''. 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 ...
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'',
:
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'',
:
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
:
and notice it is lumpable on the partition ''t'' = so we write
:
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