从洗牌问题说起

Table of Contents

关于洗牌有一个个著名的论断: 七次洗牌才能将一副牌洗均匀. 这句话的描述非常含糊, 我们可以如此定义这个问题: 在初始状态任意的情况下, 我们希望经过一个洗牌算法的操作之后, 牌面是一个均匀分布(处于任何状态的概率均为 \(1/n!\) ),或者接近均匀分布。由于无法在所有状态空间中采样,所以借用马尔科夫链的思想, 把洗牌看作是在马尔科夫链中行走. 所以我们希望由一个初始状态出发,经过一定数量的转移(对应于我们的洗牌过程)之后,状态的分布接近于均匀分布,这个算法叫做 Markov Chain Monte Carlo(MCMC), 需要的转移次数的期望称为 mixing time。对应于洗牌问题的 mixing time 在 n=52 时为 7.

基于停时的分析

以下内容整理自 Proofs from THE BOOK (来自天书的证明):

书中使用了 total variance ( 变差距 )来衡量两个分布之间距离, 分析每次操作之后变差距的大小是一件很头疼的事情(可以使用 Markov 链的相关理论分析,不过殊途同归), 于是引入了" 停时 "的概念(这是整个证明中最精妙的部分), 计算与停时相关的概率可以给出变差距的上界.

最后用这个方法对于两种洗牌模型进行分析,分别规约到了两个简单的经典概率问题: 赠券收集生日问题, 通过简单的计算给出了两种洗牌模型达到足够随机需要次数的一个粗糙的界.

定义

变差距

考虑两个概率分布 \(Q_1, Q_2:S_n\rightarrow [0,1]\) (其中 \(S_n\) 为 \([n]\) 的置换群), 它们的变差距定义为: \[ \lVert Q_1 - Q_2 \rVert = \frac{1}{2} \sum_{\pi \in S_n} |Q_1(\pi) - Q_2(\pi)| \]

即标准化之后的函数距离. 由于概率分布满足的性质 \(\sum\limits_{\pi \in S_n} Q(\pi) = 1\) , 上式可被替代为: \[ \lVert Q_1 - Q_2 \rVert = \max_{S\subseteq S_n} |Q_1(S) - Q_2(S)| \]

假设一副牌的初始置换为 \(id\) , 那么对应的初始分布 \(E(\pi) = [\pi = id]\) , 而均匀分布 \(U\) 满足 \(U(\pi)=\frac{1}{n!}\) .

这样的话一副牌的初始分布与均匀分布的变差距为 \(\lVert E - U \rVert = 1 - \frac{1}{n!} \approx 1\) .

洗牌的目的在于在有限数目的操作之后, 一副牌的分布与均匀分布的变差距接近于 \(0\) .

停止规则

一个停止规则可以当作一个函数, 自变量是从开始到当前每次操作之后的牌面 \(X_1, X_2, \cdots, X_i\) , 因变量为 \(0\) (继续)或者 \(1\) (停止), 从开始到停止经历的操作数称为"停时": \(T\) , 是一个随机变量.

  • 强一致停止规则

    如果一个停止规则满足: \[ \forall k\geq 0,\forall \pi \in S_n,P(X_k=\pi\mid T = k) = \frac{1}{n!} \]

    则称这个停止规则是"强一致"的.

  • 变差距的上界

    令 \(Q:S_n\rightarrow \mathbb{R}\) 为初始概率分布, \(Q^{k}\) 为洗牌 \(k\) 次之后的概率分布, 且该洗牌规则具有强一致的停止规则, 停时为 \(T\) , 那么有如下不等式: \[ \lVert Q^k - U \rVert \leq P(T>k) \]

    证明:

    对于任意 \(S\subseteq S_n\) , \[ \begin{eqnarray*}Q^k(S) & = & P(X_k \in S) \\ & = & \sum_{i=0}^{k} P(X_k \in S | T = i)P(T = i) + P(X_k \in S | T > k)P(T>k) \\ & = & \sum_{i=0}^{k} U(S)P(T = i) + P(X_k \in S | T > k)P(T>k) \\ & = & U(S)(1 - P(T > k)) + P(X_k \in S | T > k)P(T>k) \\ & = & U(S) + (P(X_k \in S | T > k) - U(S))P(T>k)\end{eqnarray*} \]

    由此易得 \(\lVert Q^k - U \rVert \leq P(T>k)\) . 证明的思路大概是这样: 由于 \(T\leq k\) 时, \(Q^k=U\) , 对 \(\lVert Q^k-U\rVert\) 没有贡献, 而 \(T > k\) 时, \(\lVert Q^k-U\rVert \leq 1\) , 做了一些微小的贡献.

    \(P(T>k)\) 可能是容易计算的, 由此可以得到变差距的估计(上界).

不同洗牌方法的分析

顶牌随机插入

操作:每次取顶部的一张牌, 然后随机插入到一个位置.

为了确定强一致停止规则, 我们假设整个操作过程中所有牌的顺序都是可见的, 初始顺序为 \(1,2,3,\cdots, n\) (从上到下), 然后考虑最后一张牌 \(n\) , 停止规则为: \(n\) 到顶端时再操作一步之后停止.

top-in-at-random.png

考虑在整个过程中 \(n\) 下方的牌, 它们的顺序是完全随机的, 最后一步相当于把 \(n\) 插入到一堆随机的牌的某个位置, 之后整副牌都是完全随机的(这样的解释不够严谨, 但是我目前还没有发现非常严谨的解释).

下面考虑如何计算 \(P(T>k)\) , \(E(T)\) 是可以计算的, 设 \(T_i\) 为 \(n\) 下方有 \(i\) 张牌的初始时间, 有 \(T_{i+1} > T_{i}(T_0=0)\) , \[ E(T) = 1 + \sum_{i = 1}^{n-1}E(T_{i} - T_{i - 1}) \]

这个问题与经典的赠券收集问题相对应: 有 \(n\) 种卡片, 每种等概率出现, 问集齐 \(n\) 张卡片所需要的时间. 计算 \(E(T)\) 相当于倒序的赠券收集问题, \(T_{i} - T_{i - 1}\) 满足几何分布. \[ E(T_{i} - T_{i - 1}) = \frac{n}{i} \]

\[ E(T) = \sum_{i=1}^{n} \frac{n}{i} \approx n \log n \] 有 Markov 不等式可以得到 \(P(T>k) < \frac{n \log n}{k}\) , 这个界非常大(计算出方差后用 Chebyshev 不等式可以得到强得多的界), 不过针对具体问题有更紧的分析:

考虑经典的赠卡收集问题(这里直接考虑洗牌问题比较繁), 令 \(A_i\) 为第 \(i\) 张卡一直没有被收集到的概率. \[ P(T>k) = P(\bigcup_{i=1}^{n}A_i) \leq \sum_{i=1}^{n}P(A_i) = n(1-\frac{1}{n})^k < ne^{-\frac{k}{n}} \] 设 \(k = n\log n + cn\) , 则 \(P(T>k) < n e^{-(\log n + c)} = e^{-c}\) 当 \(k > n\log n\) 时, 变差距以指数速度收敛到 \(0\) .

因此用顶牌随机插入洗牌时, \(n\) 张牌需要 \(O(n\log n)\) 次洗牌才能接近均匀.

流插式洗牌

操作:每次将牌分成两部分, 然后随机地合并(保持两部分的相对次序).

riffle-shuffle.png

这种洗牌是比较符合 convention 的洗牌方式, 当然它也有漂亮的数学模型.

直接分析流插式洗牌并不方便, 所以考虑逆流插洗牌: 从牌中选一个子集的卡片, 再放到剩余卡片的上方.

rev-riffle-shuffle.png

假设 k 次流插式洗牌后牌面的概率分布为 \(Rif^k\) , $k$次逆流插洗牌后概率分布为 \(\overline{Rif}^k\) , 由 \(Rif(\pi) = \overline{Rif}(\pi^{-1})\) 可以得到: \[ \lVert Rif^k - U \rVert = \lVert \overline{Rif}^k - U \rVert \]

这说明了我们只需要分析 \(\overline{Rif}^k\) 的变差距就可以得到 \(Rif^k\) 的变差距.

在逆流插式洗牌的第 \(i\) 次操作中, 给被选出的牌 \(c\) 编号 \(s_i(c)=0\) , 没被选出的牌编号 \(s_i(c)=1\) , 这样经历过 \(i\) 次洗牌后, 从上到下每张牌的 \(s_i(c)s_{i-1}(c)\cdots s_{1}(c)\) (将其设为 \(a(c)\) )为从小到大的顺序.

shfl-coding.png

停止规则: 当所有牌 \(c\) 的 \(a(c)\) 两两不同时, 停止.

由于每张牌 \(c\) 的 \(a(c)\) 完全随机, 两两不同时, 每张牌的位置已经完全被编号确定, 故这个停止规则是强一致的.

下面计算 \(P(T>k)\) :

操作 \(k\) 次之后, 每张牌 \(c\) 的总编号 \(a(c)\) 都是一个 \(0\) 到 \(2^k-1\) 的随机变量(均匀分布),

\[ P(T>k) = 1 - \prod_{i=0}^{n-1}\left(1-\frac{i}{2^k}\right) \]

其中 \(\left(1-\frac{i}{2^k}\right)\) 可以用 \(e^{-\frac{i}{2^k}}\) 来估计, 因此 \(P(T>k) \approx 1 - e^{-\frac{n(n-1)}{2^k}}\) .

当 \(k > 2\log(n)\) 后, 变差距接近于零.

因此 \(n\) 张牌需要 \(O(\log(n))\) 次流插式洗牌才能够接近均匀. 当 \(n=52\) 时, 需要 \(2\log(52)>8\) 次洗牌会接近均匀.

以上的分析运用了一些近似, 更精确的计算和分析表明, \(7\) 次流插洗牌足够将一副牌变得足够均匀.

应用

考虑这样一个问题, 假设需要 shuffle 一个 1TB 的文件, 而内存只有 1GB, 硬盘有 3GB 的可用空间.

用上文中提到的方法, 可以设计一个类似于洗牌的算法:

  1. 假设待 shuffle 的文件为 A, 有两个临时文件 B, C(初始为空).
  2. 每读取一个 A 的元素, 以 \(1/2\) 的概率加到 B 的结尾, \(1/2\) 的概率放到 C 结尾.
  3. 把 B 的内容写到 A 中, 然后把 C 中的元素写到 A 的结尾.

以上即是一个洗牌的过程, 如果想达到均匀需要 \(O(\log n)\) 轮。如果你有一个集群,可以在多台机器上进行 push/pull 的操作,相应的收敛性分析将更为复杂,搜索关键字 Distributed Shuffling 可以找到不少近年来的工作。

Author: expye(Zihao Ye)

Email: expye@outlook.com

Date: 2016-06-15

Last modified: 2020-07-30 Thu 01:44

Licensed under CC BY-NC 4.0