Space Reduction for a Class of Multidimensional Markov Chains: A Summary and Some Applications
Qi-Ming He, Attahiru Sule Alfa
INFORMS Journal on Computing · 2018 · Volume 30 · Issue 1
Abstract
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. The online supplement is available at https://doi.org/10.1287/ijoc.2017.0759 .
Keywords
Markov chains, order statistics, queues with multiple servers, reliability, phase-type distribution, Markovian arrival process
Enable JavaScript for citation tools and additional paper interactions.