On Block Skip Free Transition Matrices and First Passage Times

Abstract

Starting from an abstract setting which extends the property “skip free to the left” for transition matrices to a partition of the state space, we develop bounds for the mean hitting time of a Markov chain to an arbitrary subset from an arbitrary initial law. We apply our theory to the embedded Markov chains associated with the M/G/1 and the GI/M/1 queueing systems. We also illustrate its applicability with an asymptotic analysis of a non-reversible Markovian star queueing network with losses.

Keywords:

• Markov chains on discrete state spaces
• Hitting times
• Stationary distributions
• Invariant measures
• Skip free Markov chains
• Aggregation of states
• Balanced partitions
• Markovian analysis of queueing networks
• Primary 60J10
• Secondary 60J20, 60K25, 90B22

Acknowledgment

I thank Professor Dr. Gunter Ritter for some valuable comments.