Ever-reaching probabilities and mean first passage times of higher order ergodic Markov chains

Abstract

Within a tensor framework, the notions of ergodicity, ever-reaching probabilities, and mean first passage times of Markov chains have recently been extended to higher order Markov chains. In this paper, we establish the relations between ergodicity of a higher order Markov chain and its ever-reaching probabilities and mean first passage times. In particular, we demonstrate the key role ergodicity plays in the existence and uniqueness of the mean first passage times. We exploit the structure of the tensor equation governing the mean first passage times and propose a block iterative algorithm and a block direct algorithm for computing these quantities. We show that ergodicity guarantees the convergence of the block iterative algorithm. Some illustrative numerical results comparing these algorithms with a brute-force direct method are also given.

Keywords:

• Higher order Markov chains
• transition tensor
• ergodicity
• ever-reaching probabilities
• mean first passage times

Acknowledgments

The authors would like to thank the anonymous reviewer for his/her constructive comments, which have led to a much improved presentation of our results.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 It is a square matrix in the form rI−B, where $B\ge 0$ with the spectral radius $\rho (B)$, and $r>\rho (B)$, see [14].