Non-backtracking random walk in regular (finite) graphs

Question

I know that many things are known when dealing with random walks on a finite (or even infinite) graph: mixing time, returns to origin, etc. All is based in the use of the Markovian property of such a random walk (I am assuming that on each vertex we can choose the next one among neighbours with uniform probability distribution).

My question is the following: when dealing with non-backtracking random walks (namely, we cannot go back through an edge we have just used, inducing on every edge a uniform distribution) we lose all markovian property, but this can be manage by taking orientation on edges.

Q: is there some kind of 'universal' result for regular graphs concerning the existence of stationary distribution for such random walks?

I have looked for bibliography on this topic (this should be like the first question on these models), but I have not been able to find any reference on this.

Answer 1

Indeed, understanding non-backtracking walks is often the key to analyzing the simple random walk and random graphs. See e.g. [1], [2] and [3], [4]. Basic properties of the non-backtracking walk are collected in [5], Exercise 6.59.

[1] Lubetzky, Eyal, and Allan Sly. "Cutoff phenomena for random walks on random regular graphs." Duke Mathematical Journal 153, no. 3 (2010): 475-510.

[2] Lubetzky, Eyal, and Yuval Peres. "Cutoff on all Ramanujan graphs." Geometric and Functional Analysis 26, no. 4 (2016): 1190-1216.
https://www.math.nyu.edu/~eyal/papers/ramanujan.pdf

[3] C. Bordenave. A new proof of Friedman’s second eigenvalue Theorem and its extension to random lifts. arXiv preprint arXiv:1502.04482, 2015.

[4] Bordenave, Charles, Marc Lelarge, and Laurent Massoulié. "Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs." In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1347-1357. IEEE, 2015.

[5] R. Lyons and Y. Peres. Probability on Trees and Networks. Cambridge University Press. (2016). Available at http://pages.iu.edu/~rdlyons/.

Answer 2

Edit: The previous argument is flawed, as pointed out by Brendan Mckay.

Let $G$ be a non-bipartite regular graph with $δ≥3$, and $X$ its transition matrix on directed arcs.

We need to prove that

There exists a number $N$ and a vertex $V$ such that for every $n>N$ there's a non-backtracking walk from $V$ to $V$.

If the statement is true, there exists some number $N$ for which we can reach every directed arc in $G$ starting from any directed arc in $G$ in $n$ steps, for every $n>N$, as $G$ is connected. So there exists a number $N$ for which $X^N$ is strictly positive. By Perron–Frobenius theory, it implies that there is only one stationary distribution on $X$, which is the uniform distribution.

We could prove the statement above by showing that there are some cycles in $G$ whose lengths has no common divisor $>1$.

Let $L$ be the longest path in $G$, and let $l_1$ be one of its ends. $l_1$ is incident to at least two vertices on $L$, say $l_2$ and $l_3$. So there are three cycles formed by the edges $E\{L\}\cup l_1l_2 \cup l_1l_3$. The gcd of the lengths of the cycles are either $1$ or $2$; If it's $1$, we are already done, and if it's $2$, pick an odd cycle, and the gcd will become $1$.

The cycle lengths have finite Frobenius Number, and the statement follows.