### Current browse context:

math.CO

### Change to browse by:

### References & Citations

# Mathematics > Combinatorics

# Title: Hitting Time Quasi-metric and Its Forest Representation

(Submitted on 1 Jan 2018 (v1), last revised 29 Jul 2018 (this version, v5))

Abstract: Let $\hat m_{ij}$ be the hitting (mean first passage) time from state $i$ to state $j$ in an $n$-state ergodic homogeneous Markov chain with transition matrix $T$. Let $\Gamma$ be the weighted digraph whose vertex set coincides with the set of states of the Markov chain and arc weights are equal to the corresponding transition probabilities. It holds that $$ \hat m_{ij}= q_j^{-1}\cdot \begin{cases} f_{ij},&\text{if }\;\; i\ne j,\\ q, &\text{if }\;\; i=j, \end{cases} $$ where $f_{ij}$ is the total weight of 2-tree spanning converging forests in $\Gamma$ that have one tree containing $i$ and the other tree converging to $j$, $q_j$ is the total weight of spanning trees converging to $j$ in $\Gamma,$ and $q=\sum_{j=1}^nq_j$ is the total weight of all spanning trees in $\Gamma.$ Moreover, $f_{ij}$ and $q_j$ can be calculated by an algebraic recurrent procedure. A forest expression for Kemeny's constant is an immediate consequence of this result. Further, we discuss the properties of the hitting time quasi-metric $m$ on the set of vertices of $\Gamma$: $m(i,j)=\hat m_{ij}$, $i\neq j$, and $m(i,i)=0$. We also consider a number of other metric structures on the set of graph vertices related to the hitting time quasi-metric $m$---along with various connections between them. The notions and relationships under study are illustrated by two examples.

## Submission history

From: Pavel Chebotarev [view email]**[v1]**Mon, 1 Jan 2018 08:28:00 GMT (47kb)

**[v2]**Wed, 3 Jan 2018 06:49:46 GMT (47kb)

**[v3]**Fri, 18 May 2018 16:26:15 GMT (48kb)

**[v4]**Mon, 21 May 2018 09:53:34 GMT (48kb)

**[v5]**Sun, 29 Jul 2018 08:32:31 GMT (48kb)

Link back to: arXiv, form interface, contact.