

























In each step of the overlapping cycles shuffle on $n$ cards, a fair coin is flipped which determines whether the $m$th card or the $n$th card is moved to the top of the deck. Angel, Peres, and Wilson showed the following interesting fact: If $m = \lfloor αn \rfloor$ where $α$ is rational, then the relaxation time of a single card in the overlapping cycles shuffle is $θ(n^2)$. However if $α$ is the golden ratio, then the relaxation time of a single card is $θ(n^\frac{3}{2})$. We show that the mixing time of the entire deck under the overlapping cycles shuffle matches these bounds up to a factor of $\log(n)^3$. That is, the mixing time of the entire deck is $O(n^2 \log(n)^3)$ if $α$ is rational and $O(n^\frac{3}{2} \log(n)^3)$ if $α$ is the golden ratio.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。