结果族 238：Optimal logarithmic mixing of the Thorp shuffle · 学科：Probability and statistical mechanics · 验证状态：暂无形式化证明，请以社区核验为准
一台老式洗牌机：把 @@M@@2^d@@ 张牌对半分开、前后对齐配成对，每一对掷一枚公平硬币——正面就交换、反面就不动——再交错合拢。单张牌很快就洗匀了，但所有牌共用同一批硬币，整副牌的”秩序”顽固得多。这篇论文给出最终答案：恰好 @@M@@\Theta(d)@@ 次完整洗牌，不多不少（就数量级而言）。
关键词卡片
@@M@@1/4@@ 以下所需的洗牌次数。@@M@@\|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_g|\mu(g)-\nu(g)|@@。@@M@@t@@ 次洗牌至多产生 @@M@@2^{tn/2}@@ 种硬币结果，远少于 @@M@@n!@@ 种排列。看个具体例子
取 @@M@@n=2^{10}=1024@@ 张牌：每次洗牌只消耗 @@M@@n/2=512@@ 个随机比特，硬币结果的总数远不够区分 @@M@@n!@@ 种排列，故 @@M@@t\ge 2d-O(1)\approx 20@@ 次；另一端，数字版定理给出 @@M@@\|q_d^{*(1600d)}-U_n\|_{\mathrm{TV}}=\|q^{*16000}-U\|_{\mathrm{TV}}\to 0@@，即一万六千次后任何初始牌序都被洗匀。
为什么值得关心
此前最好结果是 @@M@@O(d^3)@@，对数阶是悬置多年的目标；本文首次达到并配上同阶下界。常数 @@M@@1600@@ 是证明里的显式选择而非最优值，更小的领先常数与切断现象留作公开问题。顺带还得到：用 @@M@@O(n\log n)@@ 个公平比特即可生成近似均匀的随机排列，且这个比特数已是必需。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读里的”配对掷硬币”洗牌机，剥掉机械细节后是：把一副牌对半分开、前后配对，每对的内部次序由一枚独立硬币决定，再交错合拢。微妙之处在于每张牌单独很快变匀，但所有牌共用同一批硬币、轨迹高度相关，整副牌的联合次序顽固得多——问的是后者的命运。
第二级台阶
精确化：把一次完整洗牌看成位置集合上的一个随机置换，其分布记 @@M@@q_d@@；@@M@@t@@ 次独立洗牌的合成分布是卷积 @@M@@q_d^{*t}@@。两个分布的差距用总变差距离度量，即逐点差绝对值之和的一半；混合时间定义为该距离首次不超过 @@M@@1/4@@ 的时刻，参照目标是置换群上的均匀分布 @@M@@U_n@@。
第三级台阶
定理在牌数恰为 @@M@@2^d@@ 的假设下陈述——这一结构让位置等同于 @@M@@d@@ 维立方体的顶点、洗牌分解为逐坐标的开关层。上界说：当 @@M@@d\to\infty@@，@@M@@1600d@@ 次洗牌后 @@M@@\|q_d^{*(1600d)}-U_n\|_{\mathrm{TV}}\to0@@，且由平移不变性对任意初始牌序一致；下界来自支撑计数：@@M@@t@@ 次洗牌至多产生 @@M@@2^{tn/2}@@ 种硬币串，远不够覆盖 @@M@@n!@@ 种排列，迫使 @@M@@t\ge 2d-O(1)@@。两边合并即最优混合阶 @@M@@\Theta(d)=\Theta(\log n)@@。常数 @@M@@1600@@ 是证明中的显式选择而非最优值，上界的渐近性质意味着它不承诺对每个固定 @@M@@d@@ 都成立。
证明 @@M@@2^d@@ 张牌的 Thorp 洗牌经 @@M@@1600d@@ 次完整洗牌后，整副牌的排列律在总变差（total variation）意义下收敛到均匀分布，而支撑计数给出 @@M@@2d-O(1)@@ 的下界，从而把该洗牌的最优混合阶确定为 @@M@@\Theta(d)=\Theta(\log N)@@。
Thorp 洗牌由 Thorp 于 1973 年研究非随机洗牌对 Faro 纸牌游戏的影响时提出：把 @@M@@2^d@@ 张牌等分成两半，配对处于对应位置的牌，每对内部次序由一枚独立公平硬币决定，再交错合并。其微妙之处在于：@@M@@d@@ 次洗牌后每张牌的位置已单独均匀，但所有牌共用同一组硬币，轨迹高度相关，整副牌的联合排列远未随机。整副牌到底需要多少次洗牌，悬置多年：Morris 用演化集（evolving set）方法首先给出多项式界 @@M@@O(d^{44})@@，Montenegro 与 Tetali 改进到 @@M@@O(d^{29})@@，Morris 又用相对熵方法得到一般偶数牌数的 @@M@@O((\log n)^4)@@ 与二进制牌数的 @@M@@O(d^3)@@；对数阶正是 Jonasson 笔记中讨论的目标。本文首次达到这一最优阶。
记 @@M@@q_d@@ 为一次完整洗牌作为位置置换的分布，@@M@@U_n@@ 为对称群（symmetric group）@@M@@S_n@@上的均匀分布，距离取总变差 @@M@@\|\mu-\nu\|_{\mathrm{TV}}=\frac12\sum_g|\mu(g)-\nu(g)|@@，混合时间（mixing time）@@M@@t_{\mathrm{mix}}(d)@@ 是距离首次不超过 @@M@@1/4@@ 的时刻。主定理分两半：上半是当 @@M@@d\to\infty@@ 时 @@M@@\|q_d^{*(1600d)}-U_n\|_{\mathrm{TV}}\to0@@，且对任意确定性初始牌序一致成立；下半是支撑下界——@@M@@t@@ 次洗牌至多产生 @@M@@2^{tn/2}@@ 种硬币串，故 @@M@@\|q_d^{*t}-U_n\|_{\mathrm{TV}}\ge1-2^{tn/2}/n!@@，距离不超过 @@M@@1/4@@ 就迫使 @@M@@t\ge\lceil\frac2n\log_2\frac{3n!}{4}\rceil=2d-O(1)@@。合并得 @@M@@t_{\mathrm{mix}}(d)=\Theta(d)@@。常数 @@M@@1600@@ 是证明中的显式选择而非最优值，领先常数与切断现象（cutoff）留作公开问题。附带推论：该洗牌以 @@M@@O(n\log n)@@ 个公平比特生成近似均匀的随机排列，而支撑论证表明同阶比特数是必要的。
先把位置等同于 @@M@@\mathbb F_2^d@@ 的顶点：一次物理洗牌是确定性坐标循环 @@M@@R@@ 与沿方向 @@M@@e_1@@ 的随机开关 @@M@@S@@ 之复合；撤销旋转后，相继洗牌变成沿相继坐标方向的独立开关层，扫完 @@M@@d@@ 个方向恰花 @@M@@d@@ 次洗牌，单牌均匀性由此立得。
上界分两阶段。第一阶段控制”大部分牌”的联合位置：先均匀随机选取 @@M@@7n/8@@ 张牌的有序表并逐张暴露轨迹，考察下一张被追踪牌在剩余位置上的条件分布与均匀分布之差，即中心化流 @@M@@w_s@@。两个位置都空闲的开关把两份质量平均，平方范数不增；只剩一个空闲位置的开关被迫沿已暴露路径输运质量，恰好产生条件均值为零的噪声，写成 @@M@@w_{s+1}=A_{i_s}w_s+\xi_s@@。由于 @@M@@d@@ 个坐标平均算子的乘积把任何均值为零的向量映为其整体均值，能量恒等式断言当前能量恰是上一扫各时刻噪声的加权和。为控制噪声，向前回看 @@M@@d-1@@ 个方向：这些更新在两个对半内部独立进行，故一半内的流值与另一半伙伴位置是否空闲条件独立；配合随机表以高概率（Azuma–Hoeffding 集中）在两半各留固定比例空位，得标量递推，能量几何衰减为 @@M@@(31/32)^{t-2d}@@ 加指数小项。最后用逐张序列比较引理与 Cauchy–Schwarz 不等式，得 @@M@@200d@@ 次后随机表联合位置平均以 @@M@@O(n^{-5/2})@@ 接近均匀注入分布。
第二阶段把缺掉的八分之一的依赖关系补回全群。把标签分成八块，由平均值论证可选定一个确定性划分，使八个补集边际——等价于相应块子群左陪集（coset）的分布——总误差 @@M@@o(1)@@；删去超重陪集得到公共的邻近律 @@M@@\nu@@，其八个陪集系质量都被均匀值的四倍封顶。再把 @@M@@S_n@@ 的不可约表示 @@M@@\rho@@（维数 @@M@@D@@）限制到八个块子群之积上：每个张量分量必有某因子维数不超过 @@M@@D^{1/8}@@，而单个向量在该块子群轨道下张成的空间维数不超过小因子维数的平方之和——关键在于多重性不放大轨道维数，因为群作用经由一个维数 @@M@@a^2@@ 的矩阵空间实现；再用钩长公式（hook-length formula）初等证明的互逆维数和 @@M@@\sum_\lambda(f^\lambda)^{-1}\le C_1@@ 控制，得 Fourier 算子范数 @@M@@\|\widehat\nu(\rho)\|_{\mathrm{op}}\le AD^{-5/16}@@。收尾用 Diaconis–Shahshahani 的 Plancherel 上界：八个因子的非平凡、非符号贡献以 @@M@@\sum D^{-3}@@ 计趋于零；符号表示单独处理——固定最后一步洗牌的其余硬币，翻动最后一枚等价于复合对换（transposition），故符号均值为零。把八个独立的 @@M@@200d@@ 时间块换回原律即得 @@M@@q_d^{*(1600d)}@@ 的收敛。
本文是 OpenAI 手稿，主结果尚未形式化；按 OpenAI 官方声明”未经形式化的结果可能有问题”，请以社区核验为准。本篇证明自包含：坐标收缩与八块传递均在内文完成，未引用任何姊妹篇；姊妹篇”随机坐标架”用随机方向序列独立证得 @@M@@32800d@@ 的收敛，”Fourier 传递”篇则把第二阶段的表示论提升抽象为一般定理，三者在 @@M@@\Theta(d)@@ 这一结论上互相印证。下界 @@M@@2d-O(1)@@ 是初等支撑计数，各篇独立推导一致。
问 1：证明中最关键也最脆弱的一步是什么？
（答：单扫能量恒等式与跨半独立的组合。中心化流满足 @@M@@w_{s+1}=A_{i_s}w_s+\xi_s@@，@@M@@d@@ 个坐标平均算子之积湮灭均值为零的向量，故当前能量恰是上一扫噪声的加权和 @@M@@E_t=\sum_j2^{-j}b_{t-j}@@；再利用间隔的 @@M@@d-1@@ 次更新在两个对半内部独立进行，把 @@M@@b_s@@ 压成 @@M@@(1-\beta)E_s+\eta@@。跨半条件独立性这一步若不严——论文坦承例外事件可与能量相关、只能靠 @@M@@E_s\le1@@ 兲底——几何衰减 @@M@@(31/32)^{t-2d}@@ 就立不住。）
问 2：牌数必须是 @@M@@2^d@@ 吗？
（答：本文是。位置等同于 @@M@@\mathbb F_2^d@@ 顶点、坐标循环开关整套论证依赖立方体结构，论文明言”任意偶数牌数的最优阶问题未由这里的立方体论证处理”。对固定 @@M@@d@@ 收敛性存在（边对换生成全群），但 @@M@@1600d@@ 的数值界只在 @@M@@d\to\infty@@ 时成立。）
问 3：与 Morris 等前人相比真正的新意是什么？
（答：此前最好结果是 Morris 相对熵方法的 @@M@@O(d^3)@@，更早有 @@M@@O(d^{44})@@、@@M@@O(d^{29})@@；对数阶是 Jonasson 笔记中悬置的目标。本文首次达到 @@M@@\Theta(d)@@ 并配同阶下界，方法全新：一扫记忆的条件流给出 @@M@@7n/8@@ 张牌的平均边际，八块传递把边际误差提升为整个置换群的 Fourier 算子界 @@M@@AD^{-5/16}@@。）
问 4：符号表示为什么必须单独处理？
（答：@@M@@\nu@@ 是对 @@M@@\mu@@ 删去超重陪集后的条件律，破坏了 @@M@@\mu@@ 的结构。原始块律 @@M@@\mu@@ 的符号期望为零——固定最后一次洗牌的其余硬币、翻动最后一枚等价于复合一个对换——但 @@M@@\nu=\mu\mathbf 1_E/M@@ 只剩 @@M@@|\widehat\nu(\mathrm{sgn})|\le(1-M)/M@@，好在其趋于零，八因子卷积后仍收敛。）
问 5：这类结果最可能以什么模式出错？
（答：三处高危。”随机表使 @@M@@B_a@@ 无条件为均匀子集”的论证只在平均意义下成立，条件集中并不成立，混淆两者是致命的；轨道维数估计 @@M@@\dim W_a\le C_1D^{3/8}@@ 依赖”多重性不放大维数”（经 @@M@@\operatorname{End}(V_\pi)@@ 映像实现），重数处理稍有不慎即放大；互逆维数和 @@M@@\sum(f^\lambda)^{-1}\le C_1@@ 的初等证明分了多个形状区间，漏一档即不闭合。）
问 6：下界 @@M@@2d-O(1)@@ 与上界 @@M@@1600d@@ 之间差了 800 倍，这意味着什么？
（答：本文只定阶不定常数；领先常数与切断现象（cutoff）均为公开问题。下界是纯支撑计数，上界的损耗集中在八块分解与 @@M@@31/32@@ 的衰减率，两侧都有大量改进空间。）
问 7：下游谁会用到？
（答：附带的比特复杂度结论——@@M@@O(n\log n)@@ 个公平比特生成近似均匀随机排列且为该构造必需——直接服务于小域加密（Thorp 型洗牌是 swap-or-not 类加密方案的原型，承接 Morris–Rogaway–Stegers 路线）；混合阶本身也是马尔可夫链收敛理论中”对数混合”范例。）
总评
这是悬置多年的对数阶混合问题的完整解答，上界自包含、下界初等而干净，与三篇姊妹篇互相独立又互相印证，分量很重；最大风险在跨半独立性与重数控制这类”平均意义成立、条件意义不成立”的精细步骤，恰是机器证明易失手之处。