\(\newcommand{\Cat}{{\rm Cat}}
\)
\(\newcommand{\A}{\mathcal A}
\)
\(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)
3. Nonreversible chains
For a nonreversible chain with transition matrix $P(x,y)$, define its timereversal 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
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$.
Such an upper bound is known for the mixing time.
The current best bound on the hitting time of a trajectory is $EV(1+\log \frac {E}{V})$.

Cycle + ErdosRenyi
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.
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)$.
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)$.

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.
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?
Counterexample by Jonathan Hermon and Hubert Lacoin : consider a $d$regular tree $T$ of depth $n$. For each nonleaf vertex $x$, if $y$ denotes the rightmost child of $x$, then the edge $\{x,y\}$ is replaced by a "diamond", i.e. a lozenge formed by two consecutive upgoing edges from $x$ to $y$ and two consecutive downgoing edges from $y$ to $x$. Each directed edge has weight $2$, so that the symmetrization is simply obtained by replacing directed edges by nondirected 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 rightmost edges. Now, on each leaf of $T$ corresponding to a rightmost child, add a path of length $n$. To ensure that the worst starting point of the nondirected 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.

Nonbacktracking vs. simple random walk
Problem 3.4.
[Yuval Peres]
Is it true that the lazy nonbacktracking random walk (NBRW) mixes faster than the lazy simple random walk (SRW)?
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.