solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看6069次
Cutoff for Mixing Times on Random Abelian Cayley Graphs. (arXiv:1810.05130v1 [math.PR])
来源于:arXiv
Consider the random Cayley graph of a finite, Abelian group $G =
\oplus_{j=1}^d \mathbb{Z}_{m_j}$ with respect to $k$ generators chosen
uniformly at random. We prove that the simple random walk on this graph
exhibits abrupt convergence to equilibrium, known as cutoff, subject to $k \gg
1$, $\log k \ll \log |G|$ and mild conditions on $d$ and $\min_j m_j$ in terms
of $|G|$ and $k$.
In accordance with spirit of a conjecture of Aldous and Diaconis, the cutoff
time is shown to be independent of the algebraic structure of the group; it
occurs around the time that the entropy of the simple random walk on
$\mathbb{Z}^k$ is $\log|G|$, independent of $d$ and $\{m_j\}_{j=1}^d$.
Moreover, we prove a Gaussian profile of convergence to equilibrium inside the
cutoff window.
We also prove that the order of the spectral gap is $|G|^{-2/k}$ with high
probability (as $|G|$ and $k$ diverge); this extends a celebrated result of
Alon and Roichman. 查看全文>>