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.

  • $\begingroup$ 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). $\endgroup$ – Marcus M Oct 18 '18 at 0:00
  • $\begingroup$ 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. $\endgroup$ – Johnny Cage Oct 18 '18 at 5:34
  • $\begingroup$ 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. $\endgroup$ – Marcus M Oct 18 '18 at 13:10
  • $\begingroup$ Sure: I forgot to say that we want of course to avoid bipartiteness... apart from this natural condition, are there other obstructions? $\endgroup$ – Johnny Cage Oct 18 '18 at 20:15
  • 1
    $\begingroup$ What if the graph in question is a cycle graph? $\endgroup$ – LeechLattice Oct 19 '18 at 12:01

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.

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

  • $\begingroup$ Do you have a nice argument why vertices $A$ and $B$ must exist? $\endgroup$ – Brendan McKay Jun 28 '19 at 19:52
  • $\begingroup$ $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). $\endgroup$ – LeechLattice Jun 29 '19 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.