Let us consider an Ergodic Markov Chain with transitional matrix $P$ and fundamental matrix $Z$. We prove the following conjecture posed by David Aldous: ${\rm trace}(Z^2 (P^\ast - P)) \geq 0$. Moreover,we prove that all eigenvalues of $Z^i (P^\ast - P) (i=1,2)$ have nonnegative real parts.
FUNDAMENTAL MATRIX;TRACE;LYUPUNOV's THEOREM;EIGENVALUES
AMS 1991 SUBJECT CLASSIFICATION: 60J27
Let us consider an ergodic Markov chain with transitional matrix $P=(P_{i,j,1\leq i, j\leq n})$ and vector of stationary probabilities % $$ \pi = (\pi_1, \ldots, \pi_n), \pi_i>0, \sum \pi_i=1. $$
We use the notation $\hat{\pi}$ for a square matrix with all rows equal to $\pi$. As usual, the fundamental matrix $$ Z =: (I - P + \hat{\pi})^{-1}, $$
The time reversal $$ P^\ast =: ( P_{j,i} \cdot \frac{\pi_j}{\pi_i}; 1\leq i, j\leq n) $$
in [Ald] D.\ Aldous has proved the following
${\rm trace}(Z \cdot (P^\ast - P)) \geq 0$ and posed the following ${\rm trace}(Z^2 (P^\ast - P)) \geq 0$.
It was shown in [Ald] that Proposition 21 can be used to prove one inequality for hitting times which plays rather important role in a recent paper [Te] by P.\ Tetali. Also in [Ald] based on the conjecture 22, another important inequality for hitting times was proven.
Both proofs in [Ald] and [Te] are based on the trace inquality for M-matrices from [FJMN]. We will use different and simpler technique in this paper and will prove the following strengthening of both Proposition 21 and Conjecture 22.
Real parts of eigenvalues of both $Z(P^\ast - P)$ and $Z^2(P^\ast - P)$ are nonnegative.