Non-backtracking random walks mix faster
Non-backtracking random walks mix faster
复制标题
DOI：
10.1142/s0219199707002551
复制
发表时间：
2007-08-01
影响因子：
1.6
通讯作者：
Sodin, Sasha
中科院分区：
文献类型：
--
作者：
Alon, Noga;Benjamini, Itai;Sodin, Sasha
我们计算了正则扩展上的非回溯随机游动的混合率。利用第二类切比雪夫多项式的一些性质，我们表明，这个速度可能是两倍的简单随机游走的混合率。作为应用，我们证明了如果G是n个顶点上的高围长正则扩张，则G上长度为n的典型非回溯随机游动访问一个顶点的次数不超过（1 + o（1））logn/loglogn，并且这个结果是紧的.在这个意义上，多个访问顶点的集合类似于将n个球均匀地扔到n个箱子中的结果，与G上的简单随机行走相反，它几乎肯定会访问一些顶点Ω（log n）次。
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is.As an application, we show that if G is a high-girth regular expander on n vertices, then a typical non-backtracking random walk of length n on G does not visit a vertex more than (1 + o(1)) log n/log log n times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing n balls to n bins uniformly, in contrast to the simple random walk on G, which almost surely visits some vertex Omega(log n) times.