A Fixed Point Approach to the Classification of Markov Chains with a Tree Structure

Abstract

In this paper, we study the classification problem of discrete time and continuous time Markov processes with a tree structure. We first show some useful properties associated with the fixed points of a nondecreasing mapping. Mainly we find the conditions for a fixed point to be the minimal fixed point by using fixed point theory and degree theory. We then use these results to identify conditions for Markov chains of M/G/1 type or GI/M/1 type with a tree structure to be positive recurrent, null recurrent, or transient. The results are generalized to Markov chains of matrix M/G/1 type with a tree structure. For all these cases, a relationship between a certain fixed point, the matrix of partial differentiation (Jacobian) associated with the fixed point, and the classification of the Markov chain with a tree structure is established. More specifically, we show that the Perron-Frobenius eigenvalue of the matrix of partial differentiation associated with a certain fixed point provides information for a complete classification of the Markov chains of interest.

Keywords:

• Markov chains
• Ergodicity
• Tree structure
• Matrix analytic methods
• Fixed point theory
• Degree theory

Acknowledgments

The author would like to thank Dr. Attahiru S. Alfa, Dr. B. Sengupta, Dr. Yiqiang Zhao, Dr. Carl Sandblom for their encouragement and useful suggestions on this research project. This research project was financially supported by the National Science and Engineering Research Council of Canada through an operating grant and, in part, by a research award (2002) from Chinese Academy of Sciences and K.C. Wang Foundation.