Lumpability

Last updated April 20, 2019

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]

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 of axioms. Typically these axioms formalise probability in terms of a probability space, which assigns a measure taking values between 0 and 1, termed the probability measure, to a set of outcomes called the sample space. Any specified subset of these outcomes is called an event.

Definition

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 $\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}\}$ 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,

A Markov chain 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.

Partition of a set Mathematical ways to group elements of a set

In mathematics, a partition of a set is a grouping of the set's elements into non-empty subsets, in such a way that every element is included in one and only one of the subsets.

\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.^[2]

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,

In mathematics, a stochastic matrix is a square matrix used to describe the transitions of a Markov chain. Each of its entries is a nonnegative real number representing a probability. It is also called a probability matrix, transition matrix, substitution matrix, or Markov matrix.

\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.^[3]

Example

Consider the matrix

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}={\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.

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]

Related Research Articles

In probability theory and statistics, the multivariate normal distribution, multivariate Gaussian distribution, or joint normal distribution is a generalization of the one-dimensional (univariate) normal distribution to higher dimensions. One definition is that a random vector is said to be k-variate normally distributed if every linear combination of its k components has a univariate normal distribution. Its importance derives mainly from the multivariate central limit theorem. The multivariate normal distribution is often used to describe, at least approximately, any set of (possibly) correlated real-valued random variables each of which clusters around a mean value.

In mathematics, the determinant of a skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial with integer coefficients that only depend on the size of the matrix. The value of this polynomial, when applied to the coefficients of a skew-symmetric matrix, is called the Pfaffian of that matrix. The term Pfaffian was introduced by Cayley (1852) who indirectly named them after Johann Friedrich Pfaff. The Pfaffian is nonvanishing only for 2n × 2n skew-symmetric matrices, in which case it is a polynomial of degree n.

Quantum statistical mechanics is statistical mechanics applied to quantum mechanical systems. In quantum mechanics a statistical ensemble is described by a density operator S, which is a non-negative, self-adjoint, trace-class operator of trace 1 on the Hilbert space H describing the quantum system. This can be shown under various mathematical formalisms for quantum mechanics. One such formalism is provided by quantum logic.

A Markov decision process (MDP) is a discrete time stochastic control process. It provides a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker. MDPs are useful for studying optimization problems solved via dynamic programming and reinforcement learning. MDPs were known at least as early as the 1950s; a core body of research on Markov decision processes resulted from Howard's 1960 book, Dynamic Programming and Markov Processes. They are used in many disciplines, including robotics, automatic control, economics and manufacturing. The name of MDPs comes from the Russian mathematician Andrey Markov.

In mathematics, the Cheeger bound is a bound of the second largest eigenvalue of the transition matrix of a finite-state, discrete-time, reversible stationary Markov chain. It can be seen as a special case of Cheeger inequalities in expander graphs.

A number of different Markov models of DNA sequence evolution have been proposed. These substitution models differ in terms of the parameters used to describe the rates at which one nucleotide replaces another during evolution. These models are frequently used in molecular phylogenetic analyses. In particular, they are used during the calculation of likelihood of a tree and they are used to estimate the evolutionary distance between sequences from the observed differences between the sequences.

The Gittins index is a measure of the reward that can be achieved through a given stochastic process with certain properties, namely: the process has an ultimate termination state and evolves with an option, at each intermediate state, of terminating. Upon terminating at a given state, the reward achieved is the sum of the probabilistic expected rewards associated with every state from the actual terminating state to the ultimate terminal state, inclusive. The index is a real scalar.

In probability theory, Kolmogorov's criterion, named after Andrey Kolmogorov, is a theorem giving a necessary and sufficient condition for a Markov chain or continuous-time Markov chain to be stochastically identical to its time-reversed version.

In probability theory, a balance equation is an equation that describes the probability flux associated with a Markov chain in and out of states or set of states.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/c queue is a multi-server queueing model. In Kendall's notation it describes a system where arrivals form a single queue and are governed by a Poisson process, there are c servers and job service times are exponentially distributed. It is a generalisation of the M/M/1 queue which considers only a single server. The model with infinitely many servers is the M/M/∞ queue.

In probability theory, uniformization method, is a method to compute transient solutions of finite state continuous-time Markov chains, by approximating the process by a discrete time Markov chain. The original chain is scaled by the fastest transition rate γ, so that transitions occur at the same rate in every state, hence the name uniformisation. The method is simple to program and efficiently calculates an approximation to the transient distribution at a single point in time. The method was first introduced by Winfried Grassmann in 1977.

In the mathematical theory of probability, an absorbing Markov chain is a Markov chain in which every state can reach an absorbing state. An absorbing state is a state that, once entered, cannot be left.

In queueing theory, a discipline within the mathematical theory of probability, a fluid queue is a mathematical model used to describe the fluid level in a reservoir subject to randomly determined periods of filling and emptying. The term dam theory was used in earlier literature for these models. The model has been used to approximate discrete models, model the spread of wildfires, in ruin theory and to model high speed data networks. The model applies the leaky bucket algorithm to a stochastic source.

In probability theory, a nearly completely decomposable (NCD) Markov chain is a Markov chain where the state-space can be partitioned in such a way that movement within a partition occurs much more frequently than movement between partitions. Particularly efficient algorithms exist to compute the stationary distribution of Markov chains with this property.

In queueing theory, a discipline within the mathematical theory of probability, the M/M/∞ queue is a multi-server queueing model where every arrival experiences immediate service and does not wait. In Kendall's notation it describes a system where arrivals are governed by a Poisson process, there are infinitely many servers, so jobs do not need to wait for a server. Each job has an exponentially distributed service time. It is a limit of the M/M/c queue model where the number of servers c becomes very large.

In probability theory, a transition rate matrix is an array of numbers describing the rate a continuous time Markov chain moves between states.

In probability theory, the matrix analytic method is a technique to compute the stationary probability distribution of a Markov chain which has a repeating structure and a state space which grows unboundedly in no more than one dimension. Such models are often described as M/G/1 type Markov chains because they can describe transitions in an M/G/1 queue. The method is a more complicated version of the matrix geometric method and is the classical solution method for M/G/1 chains.

In probability theory, Kemeny’s constant is the expected number of time steps required for a Markov chain to transition from a starting state i to a random destination state sampled from the Markov chain's stationary distribution. Surprisingly, this quantity does not depend on which starting state i is chosen. It is in that sense a constant, although it is different for different Markov chains. When first published by John Kemeny in 1960 a prize was offered for an intuitive explanation as to why quantity was constant.

References

↑ Kemeny, John G.; Snell, J. Laurie (July 1976) [1960]. 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.
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Kemeny, John G.; Snell, J. Laurie (July 1976) [1960]. 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

[mnksmit-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.

[fra-5] 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.