# DIMACS Focus on Discrete Probability Seminar

## Title:

Proof of a Conjecture of Aldous

Leonid Gurvits

## Place:

CoRE Building, Room 431
Busch Campus, Rutgers University.

## Time:

3:30 - 4:30 PM - After the DIMACS Tea
Thursday, May 1, 1997
Abstract:

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.