algorithm - 具有随机性的 Riffle 洗牌算法

Question

riffle shuffle 算法过于机械和可预测。我们如何添加一些随机性，就好像真人在洗牌但仍然使用浅滩法一样？

Answer 1

在 Aldous 和 Diaconis 的论文 Shuffling Cards and Stopping Times(来自美国数学月刊，93:5，第 333-348 页)中，作者研究了如何随机化一副​​纸牌需要多次洗牌。该论文的第 4 部分是Riffle Shuffles 的分析，他们讨论了(非完美)纸牌洗牌的一些等效公式。

特别是，他们引用了一个随机 riffling shuffling 模型，该模型模拟“真实”人如何 riffling shuffle。从本质上讲，一副牌按照二项分布分成两部分，一手拿着 c 牌，另一手拿着 n-c 牌。然后卡片“以与数据包大小成正比的概率从给定的手中掉落”。

因此，一个简单的应用是假设您的牌组最初被分成两个相等的部分，然后重复选择下一张牌来自哪个部分，概率为 a/(a+b)它来自大小为 a 的片段和 b/(a+b) 当前大小为 b 的片段的概率。