Comparing mixing times on sparse random graphs
Comparing mixing times on sparse random graphs
复制标题
比较稀疏随机图上的混合时间
DOI：
10.1137/1.9781611975031.113
复制
发表时间：
2017
期刊：
影响因子：
6
通讯作者：
Y. Peres
中科院分区：
文献类型：
--
作者：
Anna Ben;E. Lubetzky;Y. Peres
人们很自然地期望非回溯随机游动比简单随机游动混合得更快，但到目前为止，这只在正则图中得到了证明。为了分析典型的不规则图，设G是一个具有最小度为3的n个顶点的随机图，其度分布具有指数尾。我们确定了精确的最坏情况下的混合时间为简单的随机游走$G$，并表明，以高概率，它表现出截止时间$\mathbf{h}^{-1} \log n$，其中$\mathbf{h}$是渐近熵为简单的随机游走的高尔顿-沃森树，近似$G$本地。（以前，这只是典型的起点。此外，我们表明，这个渐近混合时间是严格大于混合时间的nonbacktracking步行，通过一个微妙的比较上的Galton-Watson树的熵。
It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let $G$ be a random graph on $n$ vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise worst-case mixing time for simple random walk on $G$, and show that, with high probability, it exhibits cutoff at time $\mathbf{h}^{-1} \log n$, where $\mathbf{h}$ is the asymptotic entropy for simple random walk on a Galton--Watson tree that approximates $G$ locally. (Previously this was only known for typical starting points.) Furthermore, we show that this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton-Watson tree.