%0 Generic %1 pitman2016formulas %A Pitman, Jim %A Tang, Wenpin %D 2016 %K Aldous-Broder_algorithm Green_function Markov_chain hitting_times spanning_trees %T Tree formulas, mean first passage times and Kemeny's constant of a Markov chain %U http://arxiv.org/abs/1603.09017 %X In this paper, we aim to provide probabilistic and combinatorial insights into tree formulas for the Green function and hitting probabilities of Markov chains on a finite state space. These tree formulas are closely related to loop-erased random walks by Wilson's algorithm for random spanning trees, and to mixing times by the Markov chain tree theorem. Let $m_ij$ be the mean first passage time from $i$ to $j$ for an irreducible chain with finite state space $S$ and transition matrix $(p_ij; i, j S)$. It is well-known that $m_jj = 1/\pi_j = \Sigma^(1)/\Sigma_j$, where $\pi$ is the stationary distribution for the chain, $\Sigma_j$ is the tree sum, over $n^n-2$ trees $t$ spanning $S$ with root $j$ and edges $i k$ directed to $j$, of the tree product $\prod_i k t p_ik$, and $\Sigma^(1):= \sum_j S \Sigma_j$. Chebotarev and Agaev derived further results from Kirchhoff's matrix tree theorem. We deduce that for $i \ne j$, $m_ij = \Sigma_ij/\Sigma_j$, where $\Sigma_ij$ is the sum over the same set of $n^n-2$ spanning trees of the same tree product as for $\Sigma_j$, except that in each product the factor $p_kj$ is omitted where $k = k(i,j,t)$ is the last state before $j$ in the path from $i$ to $j$ in $t$. It follows that Kemeny's constant $\sum_j S m_ij/m_jj$ equals to $ \Sigma^(2)/\Sigma^(1)$, where $\Sigma^(r)$ is the sum, over all forests $f$ labeled by $S$ with $r$ trees, of the product of $p_ij$ over edges $i j$ of $t$. We show that these results can be derived without appeal to the matrix tree theorem. A list of relevant literature is also reviewed.

@misc{pitman2016formulas, abstract = {In this paper, we aim to provide probabilistic and combinatorial insights into tree formulas for the Green function and hitting probabilities of Markov chains on a finite state space. These tree formulas are closely related to loop-erased random walks by Wilson's algorithm for random spanning trees, and to mixing times by the Markov chain tree theorem. Let $m_{ij}$ be the mean first passage time from $i$ to $j$ for an irreducible chain with finite state space $S$ and transition matrix $(p_{ij}; i, j \in S)$. It is well-known that $m_{jj} = 1/\pi_j = \Sigma^{(1)}/\Sigma_j$, where $\pi$ is the stationary distribution for the chain, $\Sigma_j$ is the tree sum, over $n^{n-2}$ trees $\textbf{t}$ spanning $S$ with root $j$ and edges $i \rightarrow k$ directed to $j$, of the tree product $\prod_{i \rightarrow k \in \textbf{t} }p_{ik}$, and $\Sigma^{(1)}:= \sum_{j \in S} \Sigma_j$. Chebotarev and Agaev derived further results from {\em Kirchhoff's matrix tree theorem}. We deduce that for $i \ne j$, $m_{ij} = \Sigma_{ij}/\Sigma_j$, where $\Sigma_{ij}$ is the sum over the same set of $n^{n-2}$ spanning trees of the same tree product as for $\Sigma_j$, except that in each product the factor $p_{kj}$ is omitted where $k = k(i,j,\textbf{t})$ is the last state before $j$ in the path from $i$ to $j$ in $\textbf{t}$. It follows that Kemeny's constant $\sum_{j \in S} m_{ij}/m_{jj}$ equals to $ \Sigma^{(2)}/\Sigma^{(1)}$, where $\Sigma^{(r)}$ is the sum, over all forests $\textbf{f}$ labeled by $S$ with $r$ trees, of the product of $p_{ij}$ over edges $i \rightarrow j$ of $\textbf{t}$. We show that these results can be derived without appeal to the matrix tree theorem. A list of relevant literature is also reviewed.}, added-at = {2016-06-27T21:55:16.000+0200}, author = {Pitman, Jim and Tang, Wenpin}, biburl = {https://www.bibsonomy.org/bibtex/29d892d1593c525a7b7199b6cc91e5232/peter.ralph}, interhash = {f6d69798c8f766979088ff7ab806f14b}, intrahash = {9d892d1593c525a7b7199b6cc91e5232}, keywords = {Aldous-Broder_algorithm Green_function Markov_chain hitting_times spanning_trees}, note = {cite arxiv:1603.09017}, timestamp = {2016-06-27T21:55:16.000+0200}, title = {Tree formulas, mean first passage times and {Kemeny}'s constant of a {Markov} chain}, url = {http://arxiv.org/abs/1603.09017}, year = 2016 }