3. Non-reversible chains
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)$.-
Hitting time of trajectory
Such an upper bound is known for the mixing time. The current best bound on the hitting time of a trajectory is $|E||V|(1+\log \frac {|E|}{|V|})$.Problem 3.1.
[Perla Sousi] Consider a nonreversible (say $\frac 23$–$\frac 13$) random walk on an Eulerian digraph $(V,E)$. Prove that the first time, $\tau_{(X^{(y)}_t)}$ the random walk hits a moving target $X^{(y)}_t$ with $X_0=y$ satisfies the following: $\max_{x,y} \mathbb E_x [\tau_{(X_t^{(y)})}] \leq |E|\,|V|$. -
Cycle + Erdos-Renyi
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.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)$.Problem 3.2.
[Balazs Gerencser] Prove that for $p=\frac \epsilon n$, $\epsilon>0$ fixed, the nonreversible chain has $t_{\mbox{mix}}\asymp \log n$.
Prove that when $p=\epsilon n^{-\frac 32}$ the nonreversible chain has $t_{\mbox{mix}}=\tilde O(\sqrt n)$. -
Nonreversible vs. reversible chains
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.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.Problem 3.3.
Is it always true that $t_{\mbox{mix}}^P\lesssim \tilde t_{\mbox{mix}}$? Is the same also true of the cover time? -
Non-backtracking vs. simple random walk
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.Problem 3.4.
[Yuval Peres] Is it true that the lazy non-backtracking random walk (NBRW) mixes faster than the lazy simple random walk (SRW)?
Cite this as: AimPL: Markov chain mixing times, available at http://aimpl.org/markovmixing.