Thorp Shuffling, Butterflies, and Non-Markovian Couplings
Thorp Shuffling, Butterflies, and Non-Markovian Couplings
复制标题
DOI：
10.1007/978-3-662-43948-7_29
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
A. Czumaj;Berthold Vöcking
中科院分区：
文献类型：
--
作者：
A. Czumaj;Berthold Vöcking
索普洗牌是一个简单的随机洗牌模型，多年来一直逃避良好的分析。在索普洗牌中，首先将一副牌切成两半，然后开始从左手或右手开始扔牌，就像普通的洗牌一样，这样每次，一个人都有可能选择左手或右手牌并扔它，然后从另一只手扔牌。然后继续这个归纳，直到所有的卡都被丢弃。问题是要重复这个过程多少次才能随机洗牌。尽管索普洗牌的描述相当简单，人们对理解它的行为也很感兴趣，但它一直很难分析，直到最近，莫里斯才证明索普洗牌是在多对数轮中混合的。在我们的主要结果中，我们证明，如果索普洗牌将由n-k个不同元素组成的序列与k个相同元素混合在一起，（所谓的k-部分n-置换），其中k = Θ（n），则舍入足以随机混合输入元素。换句话说，Thorp shuffles with n个输入元素随机置换任何一组anycn < 1的元素，或者等价地，几乎是独立的。我们证明的关键技术部分是一个新的分析洗牌过程，使用non-Markovian耦合。虽然非马尔可夫耦合被认为比马尔可夫耦合更强大，但我们的处理是严格的非马尔可夫耦合可以用来正式证明强混合时间的少数例子之一。我们的非马尔可夫耦合被用来减少问题的一些随机过程的分析网络（特别是，当是2的幂时，这是在蝴蝶网络中），我们使用组合和概率参数来解决这个问题。我们的结果可以用于使用Thorp shuffle随机置换任何数量的元素：如果输入的牌组有N张牌，那么再添加一组0.01N的“空”牌，然后运行Thorp洗牌。然后，如果我们删除空卡，得到的甲板将有原始的ncards随机排列。我们还分析了一个相关的洗牌过程，我们称之为完美洗牌。我们把一副牌切成两半，随机排列每一半，然后执行索普洗牌的一个步骤。除了本身有趣之外，我们研究这个过程的动机是一个单一的Perfect shuffle非常类似于Thorp shuffles，因此理解Perfect shuffle可以对Thorp shuffle的性能有所了解。我们应用耦合表明，完美洗牌混合脚背，我们推测是渐近紧。
Thorp shuffleis a simple model for a random riffle shuffle that for many years has eluded good analysis. In Thorp shuffle, one first cuts a deck of cards in half, and then starts dropping the cards from the left or right hand as with an ordinary shuffle, so that at each time, one chooses the left or right card with probabilityand drops it, and then drops the card from the opposite hand. Then one continues this inductively until all cards have been dropped. The question is how many times one has to repeat this process to randomly shuffle a deck ofncards. Despite its rather simple description and wide interest in understanding its behavior, Thorp shuffle has been very difficult to analyze and only very recently, Morris showed that Thorp shuffle mixes in a polylogarithmic number of rounds.In our main result, we show that if Thorp shuffle mixes sequences consisting ofn−kdistinct elements together withkidentical elements (so-calledk-partial n-permutations) withk= Θ(n), thenrounds are sufficient to randomly mix the input elements. In other words,Thorp shuffles withninput elements randomly permutes any set ofcnelements with anyc< 1, or, equivalently, is almostcn-wise independent. The key technical part of our proof is a novel analysis of the shuffling process that usesnon-Markovian coupling. While non-Markovian coupling is known to be more powerful than the Markovian coupling, our treatment is one of only a few examples where strictly non-Markovian coupling can be used to formally prove a strong mixing time. Our non-Markovian coupling is used to reduce the problem to the analysis of some random process in networks (in particular, whennis a power of two then this is in a butterfly network), which we solve using combinatorial and probabilistic arguments.Our result can be used to randomly permute any number of elements using Thorp shuffle: If the input deck hasNcards, then add another set of 0.01N“empty” cards and runThorp shuffles. Then, if we remove the empty cards, the obtained deck will have the originalNcards randomly permuted.We also analyze a related shuffling process that we callPerfect shuffle. We cut a deck ofncards into two halves, randomly permute each half, and then perform one step of Thorp shuffle. Apart from being interesting on its own, our motivation to study this process is that a single Perfect shuffle is very similar toThorp shuffles, and thus understanding of Perfect shuffle can shed some light on the performance of Thorp shuffle. We apply coupling to show that Perfect shuffle mixes insteps, which we conjecture to be asymptotically tight.