Let $X$ be a locally finite, connected graph without vertices ofdegree $1$. Non-backtracking random walk moves at each step with equalprobability to one of the ``forward'' neighbours of the actual state,emph{i.e.,} it does not go back alongthe preceding edge to the precedingstate. This is not a Markov chain, but can be turned into a Markovchain whose state space is the set of oriented edges of $X$. Thus weobtain for infinite $X$ that the $n$-step non-backtracking transitionprobabilities tend to zero, and we can also compute their limit when$X$ is finite. This provides a short proof of old results concerningcogrowth of groups, and makes the extension of that result toarbitrary regular graphs rigorous. Even when $X$ is non-regular, butemph{small cycles are dense in} $X$, we show that the graph $X$ isnon-amenable if and only if the non-backtracking $n$-step transitionprobabilities decay exponentially fast. This is a partialgeneralization of the cogrowth criterion for regular graphs whichcomprises the original cogrowth criterion for finitely generatedgroups of Grigorchuk and Cohen.
展开▼
机译：假设$ X $是一个局部有限的，连通的图，没有顶点为$ 1 $的顶点。非回溯随机游走在每一步上具有与实际状态（例如mph）的``前向''邻居之一相等的概率，它不会沿着前沿返回前一状态。这不是马尔可夫链，但可以变成状态空间为$ X $的有向边集合的马尔可夫链。因此，对于无限的$ X $，我们可以得出$ n $步的非回溯过渡概率趋于零，并且当$ X $是有限的时，我们还可以计算其极限。这为有关组共生的旧结果提供了简短的证明，并使该结果对任意正则图的扩展严格。即使$ X $是非常规的，但是{{$中的小周期密集时}，我们也表明，当且仅当非回溯的$ n $步跃迁概率以指数速度快速衰减时，图$ X $还是不可接受的。 。这是正则图的共生准则的部分一般化，它包含了Grigorchuk和Cohen的有限生成群的原始共生准则。
展开▼
