Tree formulas, mean first passage times and Kemeny's constant of a
Markov chain
(2016)cite arxiv:1603.09017.Аннотация
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.