为什么这个简单的洗牌算法会产生有偏差的结果？

Question

看来这个简单的洗牌算法会产生有偏差的结果：

# suppose $arr is filled with 1 to 52

for ($i < 0; $i < 52; $i++) { 
  $j = rand(0, 51);

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

你可以尝试一下......而不是使用 52，使用 3（假设只使用 3 张牌），并运行它 10,000 次并统计结果，你会看到结果偏向于某些模式...

问题是...对于为什么会发生这种情况有什么简单的解释？

正确的解决方案是使用类似的方法

for ($i < 0; $i < 51; $i++) {  # last card need not swap 
  $j = rand($i, 51);        # don't touch the cards that already "settled"

  # swap the items

  $tmp = $arr[j];
  $arr[j] = $arr[i];
  $arr[i] = $tmp;
}

但问题是......为什么第一种方法看似完全随机，却使结果产生偏差？

更新1：感谢这里的人们指出它需要是 rand($i, 51) 才能正确洗牌。

Answer 1

并不是说需要另一个答案，但我发现尝试弄清楚为什么 Fisher-Yates 是统一的是值得的。

如果我们谈论的是有 N 个项目的牌组，那么这个问题是：我们如何证明

Pr(Item i ends up in slot j) = 1/N?

用条件概率将其分解，Pr(item i end up at slot j) 等于

Pr(item i ends up at slot j | item i was not chosen in the first j-1 draws)
* Pr(item i was not chosen in the first j-1 draws).

并且来自在那里它递归地扩展到第一次绘制。

现在，第一次绘制时元素i 未绘制的概率为N-1 / N。 第二次抽奖时未抽奖的概率以第一次抽奖时未抽奖为条件为N-2 / N-1，依此类推。

因此，我们得到元素 i 在第一个 j-1 绘制中未绘制的概率：

(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)

当然我们知道它在第 j-1 轮绘制的概率 < code>j 以之前未绘制为条件只是1 / Nj。

请注意，在第一项中，分子全部抵消了后续分母（即 N-1 抵消、N-2 抵消，一直到 N-j +1 取消，只剩下 Nj / N）。

因此元素i出现在槽j中的总体概率为：

[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j)
= 1/N

正如预期的那样。

为了更笼统地了解“简单随机播放”，它所缺少的特定属性称为可交换性 。 由于创建洗牌方式的“路径依赖性”（即遵循 27 条路径中的哪一条来创建输出），您无法将不同的组件随机变量视为可以以任何顺序出现。 事实上，这也许是解释为什么可交换性在随机抽样中很重要的一个例子。

Answer 2

显示第一个算法失败的最清晰答案是将所讨论的算法视为 n 个图上的 n 个步骤的马尔可夫链！ n 个自然数的所有排列的顶点。 该算法以转移概率从一个顶点跳到另一个顶点。 第一个算法给出每一跳的转移概率为1/n。 有 n^n 条路径，每条路径的概率为 1/n^n。 假设降落在每个顶点上的最终概率是1/n!，这是一个约简分数。 要实现这一点，必须有 m 条路径具有相同的最终顶点，对于某个自然数，m/n^n=1/n! 或 n^n = mn! m，或者 n^n 能被 n! 整除。 但这是不可能的。 否则，n 必须能被 n-1 整除，这只有在 n=2 时才有可能。 我们有矛盾。

Answer 3

Naive 算法如下选择 n 的值：

n = rand(3)

n = rand(3)

n = rand(3)

的可能组合

3^3 n 1,1,1, 1,1,2... .3,3,2 3,3,3（27种组合）lassevk的答案显示了这些组合的卡片之间的分布。

更好的算法是：

n = rand(3)

n = rand(2)

n！ n 1,1, 1,2, 2,1 2,2 3,1 3,2 的可能组合

（6 种组合，所有组合都给出不同的结果）

正如其他答案中提到的，如果您尝试 27 次才能得到6 个结果，你不可能获得均匀分布的 6 个结果，因为 27 不能被 6 整除。将 27 个弹珠放入 6 个桶中，无论你做什么，有些桶会比其他桶有更多的弹珠，你能做的最好的就是4,4,4,5,5,5 个弹珠用于桶 1 到 6。

天真的洗牌的根本问题是交换太多次，要完全洗 3 张牌，你只需要进行 2 次交换，第二次交换需要只能在前两张牌中，因为第三张牌已经有 1/3 的机会被交换。 继续交换卡将增加给定卡被交换的机会，并且如果您的总交换组合可以被 6 整除，则这些机会只会均匀为 1/3、1/3、1/3。

Answer 4

一个说明性的方法可能是这样的：

1）仅考虑 3 张牌。

2) 为了使算法给出均匀分布的结果，“1”最终成为 a[0] 的机会必须是 1/3，“2”最终成为 a[1] 的机会也必须是 1/3 ，等等。

3）所以如果我们看第二个算法：

“1”最终出现在 a[0] 处的概率：
当0为生成的随机数时，
所以 (0,1,2) 中有 1 种情况，因此，
是 3 中的 1 = 1/3

“2”最终出现在 a[1] 的概率：
当它没有被交换到a[0]时
第一次，没换过
第二次到a[2]：2/3 * 1/2 =
1/3

“3”最终出现在 a[2] 的概率：
当它没有被交换到a[0]时
第一次，没换过
第二次到a[1]：2/3 * 1/2 =
1/3

它们都是完美的 1/3，而我们
这里没有看到任何错误。

4）如果我们尝试计算第一个算法中“1”最终成为a[0]的概率，计算会有点长，但正如lassevk的答案中的插图所示，它是9/27 = 1 /3，但“2”最终成为 a[1] 的几率为 8/27，而“3”最终成为 a[2] 的几率为 9/27 = 1/3。

因此，“2”最终作为 a[1] 不是 1/3，因此该算法将产生相当倾斜的结果（大约 3.7% 的错误，而不是任何可忽略的情况，例如 3/10000000000000 = 0.00000000003%）

5 ）Joel Coehoorn 的证据，实际上可以证明有些案例会被过度代表。 我认为为什么是n^n的解释是这样的：在每次迭代时，随机数有n种可能性，因此在n次迭代之后，可以有n^n个情况= 27。这个数字不能整除在 n = 3 的情况下，排列数 (n!= 3!= 6) 均匀，因此某些结果被过度表示。 他们的代表性过高，不是出现 4 次，而是出现 5 次，因此，如果您从最初的 1 到 52 顺序洗牌数百万次，那么代表性过高的案例将显示 500 万次次与400万次相比，差距相当大。

6）我认为存在过度代表性，但是“为什么”会发生过度代表性？

7) 算法正确性的最终测试是任何数字都有 1/n 的概率出现在任何位置。

Answer 5

简单的答案是，这个算法有 52^52 种可能的运行方式，但只有 52 种！ 52 张牌的可能排列。 为了使算法公平，它需要以同等的可能性产生这些排列。 52^52 不是 52! 的整数倍。 因此，某些安排必定比其他安排更有可能发生。

Answer 6

请参阅编码恐怖文章天真的危险。

基本上（假设有3张牌）：

天真的洗牌结果为 33 (27)
可能的甲板组合。 那是
奇怪，因为数学告诉我们
真的只有3个！ 或 6
3 张牌的可能组合
甲板。 在KFY洗牌中，我们开始
通过初始订单，从
三者中的任何一个都处于第三位
卡，然后从第二张开始再次交换
与剩余两张牌的位置。

Answer 7

这是另一个直觉：除非至少已经存在双向对称性，否则单次洗牌交换无法在占据位置的概率上创建对称性。 称这三个位置为 A、B 和 C。现在设 a 为卡 2 位于位置 A 的概率，b 为卡 2 位于位置 B 的概率，c 为卡 2 位于位置 C 的概率，先验进行交换移动。 假设没有两个概率相同：a!=b、b!=c、c!=a。 现在计算交换后卡处于这三个位置的概率 a'、b' 和 c'。 假设此交换移动由位置 C 与三个位置之一随机交换组成。 那么：

a' = a*2/3 + c*1/3
b' = b*2/3 + c*1/3
c' = 1/3.

也就是说，卡片最终出现在位置 A 的概率是它已经在位置 A 的概率乘以位置 A 不参与交换的时间的 2/3，加上它在位置 C 的概率乘以C 与 A 交换的 1/3 概率，等等。现在减去前两个方程，我们得到：

a' - b' = (a - b)*2/3

这意味着因为我们假设 a!=b，则 a'!=b' （尽管随着时间的推移，差异将接近 0 ，给予足够的交换）。 但由于a'+b'+c'=1，如果a'！=b'，那么两者都不可能等于c'，即1/3。 因此，如果这三个概率在交换之前开始时全部不同，那么在交换之后它们也将全部不同。 无论交换哪个位置，这都会成立 - 我们只是交换上面变量的角色。

现在，第一次交换开始于将位置 A 的卡 1 与其他卡交换。 在这种情况下，交换之前存在双向对称性，因为卡 1 在位置 B 的概率 = 卡 1 在位置 C 的概率 = 0。所以事实上，卡 1 可以以对称概率结束，并且最终会出现三个位置中的每一个都有相同的概率。 这对于所有后续交换都是如此。 但是卡 2 在第一次交换后以概率 (1/3, 2/3, 0) 出现在三个位置上，同样，卡 3 以概率 (1/3, 0, 2/3) 出现在三个位置上。 因此，无论我们进行多少次后续交换，我们都不会最终得到卡 2 或 3 拥有完全相同的占据所有三个位置的概率。

Answer 8

从您对其他答案的评论来看，您似乎不仅在寻找解释为什么分布不是均匀分布（对于它的整除性答案是一个简单的），而且还在寻找“直观”解释了为什么它实际上远非统一。

这是一种看待它的方法。 假设您从初始数组 [1, 2, ..., n]（其中 n 可能是 3、52 或其他）开始，并应用两种算法之一。 如果所有排列的可能性一致，则 1 保留在第一个位置的概率应为 1/n。 事实上，在第二个（正确的）算法中，它是 1/n，因为当且仅当它第一次没有被交换时 1 才会保留在它的位置，即当且仅当对 rand(0,n-1) 的初始调用返回 0。
然而，在第一个（错误的）算法中，只有在第一次和都没有被交换，或者任何其他时间都没有被交换的情况下，1才保持不变——即，只有当第一个< code>rand 返回 0，并且其他 rand 没有一个返回 0，其概率为 (1/n) * (1-1/n )^(n-1) ≈ 1/(ne) ≈ 0.37/n，而不是 1/n。

这就是“直观”的解释：在您的第一个算法中，较早的项目比较晚的项目更有可能被替换，因此您获得的排列偏向于早期项目的模式 不在原来的位置。

（比这更微妙，例如 1 可以交换到稍后的位置，但最终仍然通过一系列复杂的交换交换回原来的位置，但是那些概率相对较小。）

Answer 9

我见过的对此效果的最佳解释来自 Jeff Atwood 在他的 CodingHorror 博客 (天真的危险）。

使用此代码模拟 3 张牌随机洗牌...

for (int i = 0; i < cards.Length; i++)
{
    int n = rand.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

...您将得到此分布。

_{（来源：typepad.com）}

随机播放代码（上图）产生 3^3 (27) 种可能的牌组组合。 但数学告诉我们，实际上只有 3 个！ 或 3 张牌的 6 种可能组合。 因此，某些组合的代表性过高。

您需要使用 Fisher-Yates shuffle 来正确（随机） ）洗一副牌。

Answer 10

请参阅此：
天真的危险（编码恐怖）

让我们看看你的三张牌：一个例子。 使用 3 张牌的牌组，洗牌后该牌组只有 6 种可能的顺序：123、132、213、231、312、321。

使用第一个算法，有 27 种可能的路径（结果）对于代码，取决于 rand() 函数在不同点的结果。 这些结果中的每一个都是同等可能的（无偏见的）。 这些结果中的每一个都将映射到上面 6 个可能的“真实”洗牌结果列表中的相同单个结果。 我们现在有 27 个项目和 6 个桶来放入它们。由于 27 不能被 6 整除，因此这 6 个组合中的某些组合必须被过度表示。

对于第二种算法，有 6 种可能的结果与 6 种可能的“真实”洗牌结果精确映射，并且随着时间的推移，它们都应该被平等地表示。

这很重要，因为第一个算法中过多表示的桶不是随机的。 为偏差选择的存储桶是可重复且可预测的。因此，如果您正在构建在线扑克游戏并使用第一种算法，黑客可能会发现您使用了朴素排序，并从中计算出某些甲板布置比其他布置更有可能发生。 然后他们就可以相应地下注。 他们会失去一些，但他们赢得的会比失去的多得多，并且很快就会让你破产。

Answer 11

这是这些替换的完整概率树。

假设您从序列 123 开始，然后我们将枚举使用相关代码生成随机结果的所有各种方法。

123
 +- 123          - swap 1 and 1 (these are positions,
 |   +- 213      - swap 2 and 1  not numbers)
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 123      - swap 2 and 2
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 132      - swap 2 and 3
 |       +- 231  - swap 3 and 1
 |       +- 123  - swap 3 and 2
 |       +- 132  - swap 3 and 3
 +- 213          - swap 1 and 2
 |   +- 123      - swap 2 and 1
 |   |   +- 321  - swap 3 and 1
 |   |   +- 132  - swap 3 and 2
 |   |   +- 123  - swap 3 and 3
 |   +- 213      - swap 2 and 2
 |   |   +- 312  - swap 3 and 1
 |   |   +- 231  - swap 3 and 2
 |   |   +- 213  - swap 3 and 3
 |   +- 231      - swap 2 and 3
 |       +- 132  - swap 3 and 1
 |       +- 213  - swap 3 and 2
 |       +- 231  - swap 3 and 3
 +- 321          - swap 1 and 3
     +- 231      - swap 2 and 1
     |   +- 132  - swap 3 and 1
     |   +- 213  - swap 3 and 2
     |   +- 231  - swap 3 and 3
     +- 321      - swap 2 and 2
     |   +- 123  - swap 3 and 1
     |   +- 312  - swap 3 and 2
     |   +- 321  - swap 3 and 3
     +- 312      - swap 2 and 3
         +- 213  - swap 3 and 1
         +- 321  - swap 3 and 2
         +- 312  - swap 3 and 3

现在，第四列数字，即交换信息之前的数字，包含最终结果，有 27 种可能的结果。

让我们计算一下每种模式出现的次数：

123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
     27 times total

如果您运行随机交换的代码无限次，则模式 132、213 和 231 会比模式 123、312 和 321 更频繁地出现，原因很简单：代码交换使得这种情况更有可能发生。

当然，现在您可以说，如果您运行代码 30 次 (27 + 3)，则最终所有模式可能会出现 5 次，但是在处理统计数据时，您必须着眼于长期趋势。

下面是探索每种可能模式之一的随机性的 C# 代码：

class Program
{
    static void Main(string[] args)
    {
        Dictionary<String, Int32> occurances = new Dictionary<String, Int32>
        {
            { "123", 0 },
            { "132", 0 },
            { "213", 0 },
            { "231", 0 },
            { "312", 0 },
            { "321", 0 }
        };

        Char[] digits = new[] { '1', '2', '3' };
        Func<Char[], Int32, Int32, Char[]> swap = delegate(Char[] input, Int32 pos1, Int32 pos2)
        {
            Char[] result = new Char[] { input[0], input[1], input[2] };
            Char temp = result[pos1];
            result[pos1] = result[pos2];
            result[pos2] = temp;
            return result;
        };

        for (Int32 index1 = 0; index1 < 3; index1++)
        {
            Char[] level1 = swap(digits, 0, index1);
            for (Int32 index2 = 0; index2 < 3; index2++)
            {
                Char[] level2 = swap(level1, 1, index2);
                for (Int32 index3 = 0; index3 < 3; index3++)
                {
                    Char[] level3 = swap(level2, 2, index3);
                    String output = new String(level3);
                    occurances[output]++;
                }
            }
        }

        foreach (var kvp in occurances)
        {
            Console.Out.WriteLine(kvp.Key + ": " + kvp.Value);
        }
    }
}

输出：

123: 4
132: 5
213: 5
231: 5
312: 4
321: 4

因此，虽然这个答案实际上很重要，但它不是一个纯粹的数学答案，您只需评估随机函数的所有可能方式，然后查看最终输出。