Cycle + Erdos-Renyi

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

Consider the graph $G=\mathbb Z_n \cup ER(n,p)$ and make the simple random walk on $G$ nonreversible by adding a counterclockwise drift to the cycle part.

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

Status note in the source

In the reversible case of simple random walk, the former has mixing time $\asymp \log^2 n$ and the latter has mixing time $\tilde O(n)$.