Triangle Inequality for hitting time of Markov Chains

Question

Given a finite, irreducible and aperiodic discrete time Markov chain on state space, $\{1, 2,\cdots, n\}$, define $h(i,j)$ to be the expected time for the first visit to $j$ from state $i$. Here we consider $h(i,i)$ to be the mean return time to $i$, so that $h(i,i) \geq 1$. Can we show the following $$h(i,k) \leq h(i,j) + h(j,k),$$ for any $i,j,k$ in the state space?

Answer 1

Let $T_{ij}$ be the number of steps for a first passage from state $i$ to state $j$. Then $h(i,j)=\mathbf{E}T_{ij}$.

The proof is given, for example, in Lemma 4.1 in Jeffrey Hunter. Stationary distributions and mean first passage times of perturbed Markov chains. Linear Algebra and its Applications, 410:217–243, 2005. DOI 10.1016/j.laa.2005.08.005

I (almost) cite:

The inequality $T_{ik}\le T_{ij}+T_{jk}$ follows from the sample path of a typical chain, since the chain will clearly take at least as many transitions (steps) to move from state i to state k via a first passage through state j starting at state i as it will without making such a forced first passage through state j. The inequality for expectations follows upon taking expectations of the respective random variables (which are all well-defined proper random variables if the chain is irreducible.)

p.s.

The value $(T_{ij}+T_{jk})$ is also known as commute time.

In fact this inequality (graph-geodetic property) is more related to the graph theory. See

Kirkland, S. J. and M. Neumann, “Group inverses of M-matrices and their applications,” CRC Press, 2012.

Chebotarev, P., Studying new classes of graph metrics, in: F. Nielsen and F. Barbaresco, editors, Proceedings of the SEE Conference “Geometric Science of Information” (GSI-2013), Lecture Notes in Computer Science, LNCS 8085 (2013), pp. 207–214.