Nonreversible vs. reversible chains

Workshop introduction

In general, we will use the following notation in the problem list. We consider aperiodic irreducible Markov chains on a state space, $\Omega$ with unique invariant (stationary) distribution $\pi$. In the discrete time setting we allow the matrix $(P)_{x,y\in\Omega}$ with $P_{xy}=P(x,y)$ to denote the transition matrix of the Markov chain.

A chain is reversible if $\pi(x)P(x,y)=\pi(y)P(y,x)$ for all $x,y\in\Omega$. $Q(x,y)=\pi(x)P(x,y)$ is the edge measure on $(x,y)$. We denote by $t_{\mbox{mix}}$ the total variation mixing time defined as

and set $t_{\mbox{mix}}=t_{\mbox{mix}}(\epsilon)$, where the total variation distance

Section context

For a nonreversible chain with transition matrix $P(x,y)$, define its time-reversal by $\hat P(x,y)=(\pi(x))^{-1}\pi(y)P(y,x)$. Then the symmetrization of the chain is given by the Markov chain with transition matrix $\frac 12 (P+\hat P)$.

Question context

Let $P$ be the transition matrix of a general nonreversible chain with, say, bounded degree vertices and transition probabilities uniformly bounded from below. Denote its mixing time by $t_{\mbox{mix}}^P$ and let $\tilde t_{\mbox{mix}}$ be the mixing time of its symmetrization.

Historical workshop record. Current open/solved status has not been independently reassessed.

Status note in the source

Counterexample by Jonathan Hermon and Hubert Lacoin : consider a $d$-regular tree $T$ of depth $n$. For each non-leaf vertex $x$, if $y$ denotes the right-most child of $x$, then the edge $\{x,y\}$ is replaced by a "diamond", i.e. a lozenge formed by two consecutive up-going edges from $x$ to $y$ and two consecutive down-going edges from $y$ to $x$. Each directed edge has weight $2$, so that the symmetrization is simply obtained by replacing directed edges by non-directed edges. This device allows to separate the harmonic measures of the two walks at the boundary of $T$: for $d$ large enough, the directed walk has about twice more chance to escape through right-most edges. Now, on each leaf of $T$ corresponding to a right-most child, add a path of length $n$. To ensure that the worst starting point of the non-directed walk is still at the root, repeat this graph on $n$ levels. At the leaves of the resulting graph, attach an expander graph, so that the mixing time is given by the hitting time of the expander, which is larger for the directed walk.