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

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 .