# Non-backtracking random walk in regular (finite) graphs

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.

• What do you mean by 'universal'? Many of these walks will be periodic on regular graphs (the $d$-dimensional hypercube is $d$-regular and bipartite). – Marcus M Oct 18 '18 at 0:00
• By 'universal' I mean not depending on the graph, but only if it is k-regular or not (for instance, or any other general condition) . The first thing I would like to know (i.e., references) if starting at a fixed vertex there is a uniform distribution to arrive to any other independently of the graph. I am happy with the restriction of the graph to be k-regular. – Johnny Cage Oct 18 '18 at 5:34
• No such universal condition may exist; if a graph is bipartite, then all walks are periodic and no stationary distribution exists. The $d$-cubes are all bipartite (if you view each vertex as a binary string then the parity of each vertex is the parity of the hamming weight), and thus no stationary distribution exists for any random walk on them. – Marcus M Oct 18 '18 at 13:10
• Sure: I forgot to say that we want of course to avoid bipartiteness... apart from this natural condition, are there other obstructions? – Johnny Cage Oct 18 '18 at 20:15
• What if the graph in question is a cycle graph? – LeechLattice Oct 19 '18 at 12:01

## 2 Answers

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/.

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.

• Do you have a nice argument why vertices $A$ and $B$ must exist? – Brendan McKay Jun 28 '19 at 19:52
• $A$ and $B$ exists by the construction above using the longest path $L$, but the previous argument is flawed(it even works for bipartite graphs, which has non-uniform stationary distributions and should be excluded). – LeechLattice Jun 29 '19 at 3:59