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

I'm not sure what you mean by "we cannot go back through an edge we have just used", but if it means "an edge can be used twice but not immediately", there is still Markovian property in the model, but on directed arcs instead of vertices.

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.


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.