七次完美洗牌能使一副牌随机化，但洗得不完美需要多少次？

# 七次完美洗牌足以随机化一副牌。但需要多少次随意洗牌？| Quanta Magazine 来源：https://www.quantamagazine.org/seven-perfect-shuffles-randomize-a-deck-of-cards-but-how-many-sloppy-ones-20260617/ 1992年，数学家们著名地证明了七次“鸽尾洗牌”（https://www.stat.berkeley.edu/~aldous/157/Papers/bayer_diaconis.pdf）——即玩家将一副牌分成两叠，然后用拇指像拉链一样将它们交错合并在一起——足以打乱整副牌。 当Dave Bayer（https://www.math.columbia.edu/~bayer/）和Persi Diaconis（https://diaconis.ckirby.su.domains/）提出这个证明时，他们还揭示了过程中发生的一些令人惊讶的事情：起初，牌的顺序相对有序。但在第七次洗牌时，整副牌突然进入一种高度无序的状态。这种行为被称为截止现象，其意义不仅限于纸牌，许多动态系统——包括凝聚态物理中的“自旋玻璃”（https://www.quantamagazine.org/pioneering-climate-modelers-earn-nobel-prize-in-physics-20211005/）——被认为会表现出这种现象（https://cordis.europa.eu/project/id/101123174）。 不幸的是，Bayer和Diaconis的证明——被一些人称为数学奇迹——只在你严格遵守关于如何切牌和洗牌的某些严格约束时才成立。如果你像中学生而非魔术师那样洗牌，结果就不成立了。 现在，三位数学家终于将这一发现（https://arxiv.org/abs/2510.22783）扩展到了不那么精确的洗牌方式。哈佛大学统计学家Mark Sellke（https://msellke.com/）（目前休假在OpenAI工作），与Jialu Shi（https://jlsirh.faculty.bio/）和Jiamin Wang（https://www.math.princeton.edu/people/jiamin-wang）（分别为剑桥大学和普林斯顿大学的研究生）共同证明，即使不将牌切成两个整齐均匀的堆，鸽尾洗牌也存在截止现象。 Diaconis对自己的工作更新赞不绝口。他说：“这是一个新颖的想法，令人惊叹的是，像这样的方法能如此有效地工作。这是一项杰出的数学成果。” ## **混合冷点** 称普通的鸽尾洗牌为“复杂”是对其的严重低估。一副普通扑克牌的可能排列数量是52的阶乘——即52 × 51 × 50 × ... × 3 × 2 × 1，或者粗略地说是一个8后面跟着67个零，接近我们银河系中估计的原子数量。另一种理解这个数字的方式是：每当你洗一副牌时，你几乎肯定产生了一个以前从未存在过、也永远不会再出现的排列。 但数学界对洗牌的兴趣不仅限于其组合复杂性。早在1981年，Diaconis和Mehrdad Shahshahani（https://link.springer.com/article/10.1007/BF00535487）就在洗牌的背景下发现了截止现象——此后数学家们开始在各处发现它们。 一位戴着帽子、穿着格子衬衫的男子。Persi Diaconis在14岁时离家出走，跟随一位魔术师工作。10年后他重返校园，成为了一名专业数学家。纸牌戏法在他的研究中仍然扮演着角色。Caroline Gates 截止现象类似于物理学中的相变（https://www.quantamagazine.org/tag/phase-transitions/），例如液态水在零摄氏度时突然结晶成固态冰。但截止发生在“马尔可夫链”（https://www.quantamagazine.org/how-big-data-carried-graph-theory-into-new-dimensions-20210819/）这一特定数学背景下，这些数学模型概率性地描述系统（如一副牌）如何在不同的配置之间移动。 截止现象，正如其名，与欧内斯特·海明威著名描述破产的方式如出一辙：逐渐地，然后突然发生。虽然截止现象无处不在——根据Sellke的说法，它们预计会在“大多数大型复杂系统”中出现——但证明关于它们的一般定理也很困难。康奈尔大学数学家Laurent Saloff-Coste（https://math.cornell.edu/laurent-saloff-coste）曾与Diaconis合作，他说：“对于大多数人们认为存在截止的问题，人们不知道如何证明它。” 这就是为什么“七次洗牌就够了”这一定理如此重要。Bayer和Diaconis——后者在十几岁时离家出走，跟随一位专门研究纸牌戏法的魔术师学徒（https://www.quantamagazine.org/persi-diaconis-mixes-math-and-magic-20150414/），后来成为著名数学家——不仅证明了现实世界系统中精确截止的存在。他们还提供了一个单一公式来确定截止点，并且该公式适用于任何大小的牌组。 然而，条款和条件同样适用。第一：鸽尾洗牌必须遵循一个现实但严格的模型，即卡片从左堆或右堆随机逐一交错落下。（每张牌从左侧或右侧堆落下的概率与该堆中剩余卡片数量成正比。这意味着卡片不会简单地左右交替，否则会产生可预测的结构；相反，顺序可能是“左、右、右、左、右、左、左”。）第二：洗牌前必须将牌大致切成两半。 “我们所有的分析都依赖于这些细节，”Diaconis说。 1999年，芝加哥大学数学家Steven Lalley（https://galton.uchicago.edu/~lalley/）试图放宽这些约束（https://www.stat.uchicago.edu/~lalley/Papers/GSRp.pdf），寻求一种不要求起始牌堆大致均匀切分的鸽尾洗牌的截止证明。他说：“对我来说，很自然地会问——有些人倾向于切得高一点或低一点。” 这些切分不太均匀的牌堆中，有一些牌组即使在多次洗牌后仍倾向于保持相同的相对顺序。当牌堆的其他部分看起来混合得很好时，这些特定的牌组——Lalley称之为“冷点”——仍然保留着关于它们在牌堆中原始位置的信息。 例如，假设你将牌标记为1到52。经过多次洗牌后，16和17不再紧挨着出现，但16可能仍然比在随机牌堆中更倾向于出现在17之前。如果原始牌堆某一部分内的许多对（比如15到25）表现出类似的偏差，那么这组牌就形成了一个冷点。 Lalley希望证明，当这些冷点消失时，牌堆中最后的秩序痕迹也会消失——这为他提供了一种证明截止存在的方法。但他无法证明这一点。 ## **追踪标签** 二十年后，2019年，Lalley的合作者Thomas Sellke（https://www.stat.purdue.edu/people/faculty/tsellke/）的儿子Mark（当时是斯坦福大学的研究生）在Diaconis的课堂上了解到最初的七次洗牌结果。Mark Sellke回忆道：“他随口提到，如果不把牌切成两半，那么（关于证明的）一切都不再有效。我当时想，‘就这样？……拜托，我们一定能够做到。’” 到2021年，Mark Sellke已经确定了对于切分远不均匀的牌堆的截止点（https://arxiv.org/abs/2103.05068）——包括那些被切成多于两堆的牌堆。但每轮洗牌之间仍然必须以相同方式切牌。他想要一个更现实的结果，即相邻两次洗牌之间的切牌方式可能差异很大。于是在2024年夏天，他与同样对这个问题的Shi和Wang组成了团队。 三人首先为每张牌分配一个条形码。从切牌开始。左堆的所有牌被赋值为1；右堆的牌赋值为0。然后洗牌，随机地将两堆牌逐一交错。再次切牌。如果一张牌最后落在左堆，其标签上加1；如果落在右堆，加0。 随着这个过程在更多的鸽尾洗牌中重复，每张牌都会建立越来越长的由1和0组成的条形码，编码了它在洗牌过程中从左到右来回跳跃的路径。例如，如果第17张牌在四次洗牌后有条形码0110，这意味着它从右堆开始，两次落在左堆，然后回到右堆。 这些数字为牌堆中的每张牌创建了唯一的追踪标签。如果两张起始相对顺序相同的牌（比如16和17）最终拥有相同的1和0条形码，这意味着它们在洗牌过程中走了完全相同的路径，并且仍然保持相同的相对顺序。 要证明截止的存在，你必须表明在特定次数的洗牌之后，那些匹配的条形码所剩无几——无论你一开始有多少张牌，或者牌是如何切分的。但比较每一个条形码非常耗时。幸运的是，冷点提供了一个捷径，正如Lalley所希望的那样。由于这些是牌堆中倾向于抵抗混合的区域，因此你只需要在这些地方检查匹配的条形码。 从一副有n张牌的牌堆开始，按升序列出牌堆冷点中所有牌的条形码。