# 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. – gaussian-matter 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? – gaussian-matter Oct 18 '18 at 20:15
• What if the graph in question is a cycle graph? – Bullet51 Oct 19 '18 at 12:01

Let $$G$$ be a non-bipartite regular graph with $$δ≥3$$, and $$X$$ its transition matrix on directed arcs.
Let $$A$$ and $$B$$ be two vertices in the graph $$G$$, where there are three edge-disjoint paths $$l_1$$, $$l_2$$ and $$l_3$$ between them, satisfying $$gcd(l_1,l_2,l_3)=1$$. Let $$G^*$$be the graph composed of $$l_1$$,$$l_2$$ and $$l_3$$. We know that $$(l_1,l_2,l_3)$$ have finite Frobenius Number.
So the 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 the transition matrix on directed arcs is connected, the proposition above also holds for $$G$$. This means there exists a number $$N$$ for which $$X^N$$ is strictly positive.
By Perron–Frobenius theory, there is only one stationary distribution on $$X$$, which is the uniform distribution.