l.logQ Let $P$ be the transition matrix of a Markov chain. For $\alpha \in [0, 1]$, define the transition matrix $Q := \alpha I + (1 -
\alpha) P$. For a state $x$, let $p_k(x)$ and $q_k(x)$ denote the return probabilities to $x$ after $k$ steps when the Markov chains start at $x$, where the transition matrices are $P$ and $Q$, respectively. We have $$\sum_k q_k(x)/k 
=
- \log (1 - \alpha) + \sum_k p_k(x)/k 
\,.
\label e.logQ$$

Write $(\cbuldot, \cbuldot)$ for the ordinary inner product in $\ell^2(V)$, where $V$ is the state space. Given $x \in V$ and $z \in (0, 1)$, we have \_k q\_k(x) z\^k/k &= -(\[(I-z Q)\] x, x) &= -(x, x) &= -(x, x) - ([1 - z ]{}) (x, x) &= - (1 - z) + \_k p\_k(x) ([z ( 1 -) 1-z]{})\^k[1 k]{} . Letting $z \uparrow 1$, we obtain the desired equation.

Next we give a universal bound for the rate of convergence of $p_k(x;\gh)$ to the stationary probability $\deg_\gh(x)/2|\edges(\gh)|$ for finite graphs and to 0 for infinite graphs. In the case of infinite graphs, such a result is first due to \[b\].CKS/. Our argument is a modification of that of \[b\].TC:survey/ 