Space Reduction for a Class of Multidimensional Markov Chains: A Summary and Some Applications

作者：He Qi Ming^*; Alfa Attahiru Sule

来源：INFORMS Journal on Computing, 2018, 30(1): 1-10.

DOI：10.1287/ijoc.2017.0759

• Markov chains
• order statistics
• queues with multiple servers
• reliability
• phase type distribution
• Markovian arrival process

In this paper, we present examples of a class of Markov chains that occur frequently, but whose associated matrices are a challenge to construct efficiently. These are Markov chains that arise as a result of several identical Markov chains running in parallel. Specifically for the cases considered, both the infinitesimal generator matrix for the continuous case, and more so the transition probability matrix for the discrete equivalent, are complex to construct effectively and efficiently. We summarize the algorithms for constructing the associated matrices and present examples of applications, ranging from special queueing problems to reliability issues and order statistics. MATLAB subroutines are provided in an online supplement for the implementation of the algorithms.

• 出版日期2018