Non-backtracking vs. simple random walk

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)$.

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

Status note in the source

Hubert Lacoin and Jonathan Hermon counterexample: let $T$ be a GW tree of depth $n$. The harmonic measures of SRW and NBRW at the boundary of $T$ are singular. On each point of the boundary reached by NBRW, add a path of length $n^{1+\varepsilon}$, with $\varepsilon<1/2$. Repeat this graph on $n^2$ levels. Join the $C^{n^3}$ leaves of this graph by an expander, with mixing time of order $n^3$. With this construction, the worst starting point of both walks is the original root, and mixing comes down to reaching the expander. The NBRW is slowed down by paths, and the ratio of mixing times tends to infinity.