8
$\begingroup$

Consider a random walk on an undirected, non-bipartite graph. Let $\pi$ be the stationary distribution of this process, and let the hitting time $H(s,t)$ be the expected time until a walk beginning at node $s$ reaches node $t$.

I learned from Random walks on graphs: a survey, by L. Lovasz, that the quantity

$$ \sum_{t} \pi(t) H(s,t)$$

is independent of $s$. In the Lovasz survey, this falls out as a byproduct of a lengthy calculation. I have two questions:

(i) Is there a simple (calculation-free, combinatorial) proof of this statement?

(ii) In what generality does this statement hold? Random walks on undirected graphs are a very particular kind of Markov process. What conditions on the probability transition matrix of the process do you need for the above to hold?

  • 1
    It's just a hunch at this point, but I think this result should work for any *reversible* Markov chain.2010-11-09
  • 0
    And connected, I assume.2010-11-12

2 Answers 2

6

This holds for any irreducible finite state Markov chain. I'm not sure about a pure combinatorial proof, but it can be shown quite quickly.

Let $M(t)$ be the expected time the chain takes to return to its initial state, if started at $t$. As it spends, on average, a time $M(t)-1$ outside the state $t$ after each visit to $t$, the fraction of its time spent at $t$ is $1/M(t)$. So, the stationary distribution is $\pi(t)=1/M(t)$ (this is standard, see Wikipedia).

Now $X_n$ be a Markov chain with the given transition matrix and, for a fixed state $t$, consider the process $H(X_n,t)$. This is just the expected time remaining before it next hits $t$. On average, at each step, this will decrease by 1 when $X_n\not=t$ and increase by $M(t)-1=1/\pi(t)-1$ when $X_n=t$. So, $Y_n\equiv\sum_tH(X_n,t)\pi(t)$ stays the same on average across each step, regardless of the value of $X_n$. That, is it is a martingale. Consider what happens when $Y_n$ reaches its maximum value. As it can't increase further and its expected value remains constant, $Y_n$ must remain constant. So, $\sum_tH(s,t)\pi(t)$ is constant.


The bit above the line answers your question. However, the calculations in the linked paper follow through for all irreducible Markov chains. In particular the formula (3.3) holds. This is the product of the lengthy calculation that you mention. I would like to show this now, which will involve going through some calculations. Let $M_{ij}=\mathbb{P}(X_{n+1}=j\vert X_n=i)$ be the transition matrix, $H_{ij}=H(i,j)$ be the hitting time matrix, $I$ be the identity matrix, $J_{ij}=1$ be the matrix of ones, and $F$ be the diagonal matrix with entries being the mean return times $F_{ii}=1/\pi(i)$. The description above of the average change in $H(X_n,t)$ across each time step can be written in matrix form $$ (M-I)H=F-J.\qquad\qquad{\rm(1)} $$ Note that $F\pi=J\pi={\bf 1}$. So, (1) gives $(M-I)H\pi=0$, which is just the martingale property described above. The only eigenvalues of M with eigenvector 1 are proportional to ${\bf 1}$. So, $H\pi$ is proportional to ${\bf 1}$.

We can solve (1). Let $M^*={\bf 1}\pi^{\rm T}$. Then $MM^*=M^*M=M^*$ and $M^*F=M^*J=J$. Trying $A=(I-M+M^*)^{-1}(J-F)$ in place of H in (1), $$ \begin{align} (M-I)A &=(I-M+M^*)^{-1}(M-I)(J-F)\\\\ &=(I-M+M^*)^{-1}(M-M^*-I)(J-F)\\\\ &=F-J. \end{align} $$ Also, the only square matrices satisfying $(M-I)A=0$ are the ones with constant columns, so of the form ${\bf 1}v^{\rm T}$ for a vector v. So, (1) has the general solution $$ H = (I-M+M^*)^{-1}(J-F)+{\bf 1}v^{\rm T} $$ and, using the condition $H_{ii}=0$ gives $$ v_i=\left((1-M+M^*)^{-1}(F-J)\right)_{ii}. $$ Next, $J\pi=F\pi={\bf 1}$ so, $$ H\pi = (v^{\rm T}\pi){\bf 1} $$ has constant entries of value $$ \begin{align} v^{\rm T}\pi &= \sum_i\left((I-M+M^*)^{-1}(F-J)\right)_{ii}\pi_i\\\\ &= {\rm Tr}\left[(I-M+M^*)^{-1}(F-J)F^{-1}\right]\\\\ &= {\rm Tr}\left[(I-M+M^*)^{-1}(I-M^*)\right]. \end{align} $$ If the eigenvalues of M are $\lambda_1,\ldots,\lambda_n$ with $\lambda_1=1$, then it can be seen that the corresponding eigenvalues of $(I-M+M^*)^{-1}(I-M^*)$ are $0,(1-\lambda_2)^{-1},(1-\lambda_3)^{-1},\ldots,(1-\lambda_n)^{-1}$ giving $$ (H\pi)_i=\sum_{j=2}^n\frac{1}{1-\lambda_j}. $$ This is independent of i, and is the same as equation (3.3) in the linked paper.

0

To answer (ii), I think it needs to be ergodic, i.e., aperiodic and recurrent.