结果族 238：Optimal logarithmic mixing of the Thorp shuffle · 学科：Probability and statistical mechanics · 验证状态：主结果已 Lean 形式化
赌场荷官有一种极简洗牌法：把牌对半分、两两一摞、每摞掷一枚硬币决定换不换。硬币看着乱来，但究竟要洗多少轮，整副牌才和”彻底洗匀”分不出差别？这篇论文给出精确回答：@@M@@N=2^d@@ 张牌只需固定次数的整轮扫描就够了——而且这个速度已碰到理论天花板，一步都不能再省。
关键词卡片
@@M@@d@@ 个二进制方向各配对交换一轮，等于 @@M@@d@@ 次物理洗牌看个具体例子
取 @@M@@N=2^{10}=1024@@ 张牌。硬币数给出下界：@@M@@t@@ 次物理洗牌至多产生 @@M@@2^{tN/2}@@ 种牌序，远小于 @@M@@1024!@@，所以至少约 @@M@@2d=20@@ 次。本文证明：存在与 @@M@@N@@ 无关的常数次扫掠，使任何起点的总变差随 @@M@@N@@ 增大趋于零，上界与下界夹出 @@M@@t_{\rm mix}=\Theta(\log N)@@。证明图景是把”扫＋反扫”看成下面的开关网络，两张牌的路线若共用开关就会”牵手”，密度估计于是变成数圈。
为什么值得关心
洗牌是”局部随机操作如何搅浑全局信息”的基准模型，本文把悬置多年的多项式鸿沟一步填平到最优阶，主结果还通过了计算机形式化验证。
已 Lean 形式化
第一级台阶
入门导读把”一扫＋反扫”比作一张掷币开关网络，现在把这张图说得更实在一点：对象是一副牌从输入位走到输出位的全部走线方案，操作是每个开关独立掷一枚公平硬币、决定两条线是否对调。导读里说两张牌的路线”共用开关就牵手”——意思是它们的命运被同一枚硬币绑定，而整副牌洗得匀不匀，归结为这类绑定能否被系统地数清楚。
第二级台阶
翻译成数学：牌的位置是二元域 @@M@@\mathbb F_2^d@@ 中的向量，一次坐标扫掠 @@M@@T_N@@ 是依次沿 @@M@@d@@ 个坐标方向做公平交换得到的平均作用算子，而 @@M@@K_N=T_N^*T_N@@ 表示”一次扫掠再接它的反向”所成的正算子。衡量混乱程度用总变差距离：两个分布对所有事件概率之差总和的一半。固定起点 @@M@@x@@、追踪 @@M@@k@@ 张牌时，核心量是落点密度 @@M@@R_x(y)=(N)_k\Pr_{K_N}(x\mapsto y)@@，即相对于均匀律的偏倚倍数。
第三级台阶
定理在 @@M@@N=2^d@@、追踪张数 @@M@@1\le k\le N@@ 任取的语境下陈述，除开关独立公平外不对初始牌序加任何限制——这正是”最坏起点一致成立”的分量。结论有两层：密度的 @@M@@1+a@@ 阶矩对数被 @@M@@Ck(k/N)^\eta@@ 压住，说明任何一部分牌的路由近乎均匀；同时扫掠在每个非平凡不可约表示 @@M@@\lambda@@ 上要么恒为零，要么算子范数不超过其维数 @@M@@D_\lambda@@ 的负幂。前者是组合信息（数圈），后者是代数收缩，经 Plancherel 求和衔接，得到固定次数扫掠后总变差趋于零；再配计数下界 @@M@@2d-O(1)@@，混合时间恰为 @@M@@\Theta(\log N)@@ 阶。
证明对 @@M@@N=2^d@@ 张牌，绝对常数次坐标”扫”即可使整副牌排列律与均匀律的总变差趋于零，Thorp 洗牌混合时间具最优阶 @@M@@\Theta(\log N)@@；主结果已有 Lean 形式化证明。
Thorp 洗牌把 @@M@@2^d@@ 张牌对半分、成对独立公平交换，在旋转坐标下即沿 @@M@@\mathbb F_2^d@@ 各坐标方向依次做公平交换；@@M@@d@@ 个方向各一次为一”扫”（sweep），耗 @@M@@d@@ 次物理洗牌。全牌混合的经典上界法是 Diaconis–Shahshahani 的有限群 Fourier 方法：控制律在每个不可约表示上的 Fourier 矩阵。但该方法为共轭不变律设计，那里 Fourier 矩阵是标量、可用特征比（character ratio）估计；定向的坐标扫给出的是投影矩阵的乘积，矩阵非正规，其幂与奇异值须同时控制，纯标量方法失效。历史界为：Morris @@M@@O(d^{44})@@、Montenegro–Tetali @@M@@O(d^{29})@@、Morris @@M@@O((\log N)^4)@@ 与 @@M@@O(d^3)@@；部分置换方面，Gelman–Ta-Shma 的双子网递推给出无序 @@M@@k@@ 子集误差 @@M@@k(k-1)/(2N)@@，Czumaj–Vöcking 借填充空牌的非马尔可夫耦合得到固定比例部分牌的 @@M@@O((\log N)^2)@@。计数下界 @@M@@t\ge 2d-O(1)@@（@@M@@t@@ 次洗牌至多产生 @@M@@2^{tN/2}@@ 个排列）与 @@M@@O(d^3)@@ 上界之间的多项式鸿沟，正是本文要填平的。
定理（路由密度与表示收缩）：存在绝对常数 @@M@@\eta,c,C>0@@，取 @@M@@a=1/1000@@。设 @@M@@T_N@@ 为一扫的平均作用矩阵，@@M@@K_N=T_N^*T_N@@ 是”一扫再接其反射”（用新鲜独立开关）的正算子，@@M@@R_x(y)=(N)_k\Pr_{K_N}(x\mapsto y)@@ 为相对均匀单射 @@M@@u_{N,k}@@ 的密度，则
@@M@@D\log\E_{y\sim u_{N,k}}R_x(y)^{1+a}\le Ck(k/N)^\eta\qquad(1\le k\le N),@@
对一切起始单射 @@M@@x@@ 一致成立；且对充分大的二进 @@M@@N@@ 与每个非平凡不可约表示（irreducible representation）@@M@@\lambda\vdash N@@，
@@M@@DT_N(\lambda)=0\quad\text{或}\quad\|T_N(\lambda)\|_{\op}\le D_\lambda^{-c},@@
其中 @@M@@D_\lambda@@ 为维数。推论：绝对常数次正向扫即可使最坏起点的全排列律与均匀律总变差趋于零，故混合时间 @@M@@t_{\mathrm{mix}}=\Theta(\log N)@@（按物理洗牌计）。附带熵解释：@@M@@\KL(P_x\|u_{N,k})\le(C/a)k(k/N)^\eta@@，当 @@M@@k/N\to0@@ 时每张被追踪牌的熵亏趋于零。
骨架是把”扫+反射”（@@M@@2d@@ 层回文 @@M@@d,\dots,1,1,\dots,d@@，拓扑即经典 Beneš 网络）在最外坐标处劈开，得到两个独立的半尺寸网络。给定输入、输出单射，追踪路径之间因共用外输入开关或共用外输出开关而连边，两族匹配的并集由交替的路与圈组成：每条路比圈少一条约束边，而每个圈给”路径分配给两个子网”的指派多出一个因子 2（指派数为 @@M@@2^{s-a+C}@@）。于是密度相对均匀单射的超额指数恰为 @@M@@X=\sum_jC_j+\log_2\big((N)_k/N^k\big)@@，@@M@@C_j@@ 为第 @@M@@j@@ 高度的圈数——密度估计归结为圈数的指数矩。
先证圈数难以累积。组合事实（蝶形接触引理）：@@M@@h@@ 条不同路径在蝶形网络上至多共享 @@M@@h\log_2h/2@@ 个开关。阶乘矩引理：给若干圈开”特异槽”并按非降长度逐条暴露路径，最后一条闭合路径的条件概率为 @@M@@2^u/n@@（@@M@@u@@ 为该路径上已暴露的开关数）；对起点做均匀旋转以平均掉历史暴露的增益，得 @@M@@\E\prod_j(F_j)_{a_j}\le(k/\sqrt n)^A\prod_jj^{-a_j/2}@@。由于不同高度共享开关币，把高度分成交替两族的带状层，在条件估计下逐层求和（不假设高度间独立）；低高度靠稀疏占据——乘积边际界在公平交换下保持（一种负相依性）——高高度几何衰减，两段用 Cauchy–Schwarz 合并得稀疏密度界。稠密端把中央定尺寸子网换成独立均匀置换（在少数指定块容许恒等），并在半正定序下比较 @@M@@K_N\le\theta^{\epsilon N/S}I+\sum_EQ_E@@。
再从密度走向表示。截断引理：若核 @@M@@Q=A+E@@、@@M@@A@@ 的元素 @@M@@\le B/M@@、@@M@@E@@ 的行列和 @@M@@\le p@@，则在重数（multiplicity）为 @@M@@m@@ 的不可约表示上 @@M@@\|Q(\lambda)\|_{\op}\le\sqrt{B/m}+p@@。序 @@M@@k@@ 单射模包含 @@M@@\lambda@@ 的重数为 @@M@@m=f^{\lambda/(N-k)}@@：首行很长的形状在略大的单射模中出现极多次，密度截断使 Hilbert–Schmidt 范数有界，重复拷贝逼出该形状上的小范数；超过 @@M@@N/2@@ 行的形状被 @@M@@T_N@@ 直接消灭（奇偶性）；中等维数用改造后的网络，极大维数用 @@M@@k=N@@ 的密度界。最后由 Plancherel 与 Schatten 范数，对固定 @@M@@r@@ 次正向扫求和 @@M@@\sum_\lambda D_\lambda^{2-2rc_*}\to0@@；全程不把非正规 @@M@@T_N@@ 的幂与 @@M@@(T_N^*T_N)@@ 的幂混同。后文的 Casimir 分裂、调和限制、自适应字母表、核心截断等给出另外的收缩机制与定量界面。
本篇是族 238 的骨架篇，主结果已由 Lean 形式化（族内附文档 lean/docs/238.md）。其共享开关接触界、密度平滑等接口被族内多篇伙伴篇引用；姊妹篇《Conditional information under deterministic coordinate sweeps》《Conditional permutations in a revealed switching environment》从条件信息角度给出显式常数（@@M@@2048d@@、@@M@@16040400\,d@@），伙伴篇另给出 @@M@@1600d@@ 的显式界，本篇则以绝对常数达到同阶。按 OpenAI 官方声明，未经形式化的结果可能有问题；本篇主结论已形式化，是族内可信度最高的一环。
问 1：证明里最关键、也最脆弱的一步是哪里？
（答：把密度估计归约为”圈数的指数矩”之后，阶乘矩引理负责证明圈数难以累积：按非降长度逐条暴露路径，最后一条闭合路径的条件概率只有 @@M@@2^u/n@@，再对起点做均匀旋转以平均掉历史暴露的增益。这一步承担了从”看得见的对称”到”可定量的衰减”的全部转换，任何一处条件概率或旋转平均算错，整个 @@M@@\|T_N(\lambda)\|\le D_\lambda^{-c}@@ 都会塌。）
问 2：为什么要绕道 @@M@@K_N=T_N^*T_N@@，不直接控制 @@M@@T_N@@ 的幂？
（答：因为定向扫掠的 Fourier 块是非正规矩阵，其幂与奇异值须分别控制；论文明确声明从不把 @@M@@(T_N^*T_N)@@ 的幂与 @@M@@T_N@@ 的幂混同，最后经 Schatten 范数与次乘性完成放大。这是与 Diaconis–Shahshahani 标量特征比方法的本质分歧。）
问 3：密度界 @@M@@Ck(k/N)^\eta@@ 在 @@M@@k@@ 接近 @@M@@N@@ 的稠密端如何过关？
（答：稀疏端靠”公平交换保持乘积边际界”的负相依加带状层条件求和；稠密端则把中央定尺寸子网替换成独立均匀置换（在少数指定块容许恒等），并在半正定序下比较 @@M@@K_N\le\theta^{\epsilon N/S}I+\sum_E Q_E@@。两个机制的拼接处是审稿最该盯的地方。）
问 4：与 Morris 的 @@M@@O(d^3)@@、Gelman–Ta-Shma 的部分置换界相比，真正新意是什么？
（答：新意在两点：处理有序单射且覆盖稠密元组（前人只做无序 @@M@@k@@ 子集或固定比例部分牌）；以及”密度截断＋表示重数”的转换——首行很长的形状在更大的单射模中出现 @@M@@f^{\lambda/(N-k)}@@ 次，重复拷贝逼出该形状上的小范数。这条从部分信息通往全牌排列的路此前不存在。）
问 5：作为 AI 生成的证明，最可能出错的模式是什么？
（答：典型风险是”看似显然”的组合恒等式——交替路/圈计数中每圈贡献因子 2、指派数 @@M@@2^{s-a+C}@@ 的指数符号、以及负相依边际界的传递。主定理已 Lean 形式化，风险被大幅压低；但 Casimir 分裂、调和限制、核心截断等后续章节只作为接口引用、未全部形式化，仍是暴露面。）
问 6：下游谁会用到这个结果？
（答：小域加密分析（Morris–Rogaway–Stegers 路线直接关心指定牌的联合位置）、Beneš 型网络上的随机路由，以及一般”局部随机化搅浑全局”的马尔可夫链研究。族内伙伴篇已引用其共享开关接触界与密度平滑接口。）
问 7：结果离”完美”还差什么？
（答：论文自陈未给出最小混合常数与 cutoff profile——只知道阶最优，不知道精确到常数的行为；下界 @@M@@2d-O(1)@@ 与上界的绝对常数之间仍隔具体数值距离。）
总评
这项工作把 Thorp 洗牌悬置多年的多项式鸿沟一步压到最优阶，且主定理有 Lean 形式化背书，是族 238 的可信支柱；最大风险集中在未形式化的稠密端算子比较与圈计数接口上。