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

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)才能正确地洗牌。

- nonopolarity

---

为什么你在下面的评论中要求“非数学答案”，当算法是通过数学来解释的？ - ephemient

第二个也是错误的：它永远无法在第一个位置生成第一个元素，因此具有偏见。您需要使 $j = rand($i, 51)。此外，缺少分号。 - Svante

以下是一个没有这个问题的洗牌样例 https://dev59.com/8X_aa4cB1Zd3GeqPyhML#23292532 ，即从一端开始，选择一个随机元素后不再操作它们，这样可供选择的元素数量会越来越少。 - Peter Lawrey

Answer 1

看这里：
天真的危险 (编程恐慌)

以您的三张牌组为例。使用三张牌组，洗牌后只有6种可能的顺序: 123, 132, 213, 231, 312, 321.

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

使用第二种算法，有6个可能的结果与6个可能的“实际”洗牌结果完全对应，并且它们应该平均分布。

这很重要，因为第一种算法中过度表示的桶并不随机。选择偏差的桶是可重复和可预测的。因此，如果您正在构建在线扑克游戏并使用第一种算法，黑客可以发现您使用了天真的排序，从而得出某些牌组合比其他牌组合更有可能发生的结论。然后他们可以相应地下注。他们会输一些，但他们会赢得比输的多，并迅速让您破产。

- Joel Coehoorn

---

虽然我非常尊重数学，但是我认为“因为不可整除”这个解释有点“事后诸葛亮”。如果对某些n是可整除的，那么这是否意味着它不会偏倚？否则是否有其他的解释 - 比如在三张牌的情况下，为什么某张牌更容易出现在特定位置。 - nonopolarity

27个结果中的每一个都没有偏见。这些结果中的每一个也恰好对应着6个“真实”结果中的一个。由于6不能被27整除，因此一些真实结果必须有所偏向，以使其发生的概率更高。 - Joel Coehoorn

如果我们看一个简单的例子：假设我们有27000002滴水，要将它们分配到5个桶中。我们将第一滴水放入第一个桶中，第二滴水放入第二个桶中，以此类推，最后，我们也可以“使用数学”来说明它们不可被整除，因此它们不是均匀分布的。虽然它们不是均匀分布的，但它们非常接近。那么对于像洗牌算法中使用的数学解释，为什么结果不能“足够接近”呢？ - nonopolarity

你的前提有误。如果你从1到5生成一个真正随机的数字，那么水滴将平均分配给五个桶。这更像是从1到6生成一个随机数，并且对于5个桶总是将“6”放在第1个桶中。随着时间的推移，第1个桶将会得到更多的关注，而破解者知道如何利用这一点。 - Joel Coehoorn

这个答案是正确的，它解释了为什么你不能得到“均匀分布”，但这并不是全部的故事：糟糕的算法不仅仅是“不均匀”，实际上它与均匀相去甚远。例如，当n=4时，4^4=256种可能性可以映射到4!=24个排列中的每一个10或11次，并且接近均匀分布，但实际上每个排列的计数从8到15都有。对于n=6，你从32到159不等——某些排列几乎比其他排列更有可能出现，这比通过除法推理所暗示的变化还要大。 - ShreevatsaR

Answer 2

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

假设您从序列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

因此，尽管这个答案确实是正确的，但它并不是一个纯数学的答案，你只需要评估随机函数可能走的所有可能路径，并查看最终输出。

- Lasse V. Karlsen

Answer 3

从您在其他答案中的评论来看，似乎您不仅想要解释为什么分布不是均匀分布（对于这个问题，可除性的答案很简单），而且还想要一种“直观”的解释为什么它实际上远非均匀分布。

以下是一种解释方式。假设您从初始数组[1, 2, ..., n]（其中n可能是3、52或其他数字）开始，然后应用其中一种算法。如果所有排列都是等可能的，则1保留在第一个位置的概率应该是1/n。实际上，在第二个（正确的）算法中，它确实是1/n，因为如果1没有被交换，则它会保持在原位，即当且仅当对rand(0,n-1)的初始调用返回0时。
然而，在第一个（错误的）算法中，只有当1既没有在第一次被交换，也没有在任何其他时间被交换时，它才保持不变——也就是说，只有当第一个rand返回0并且没有其他rand返回0时，其概率为（1/n）*（1-1/n）^(n-1) ≈ 1/(ne) ≈ 0.37/n，而不是1/n。

这就是“直观”的解释：在您的第一个算法中，较早的项被替换位置的可能性比后来的项更大，因此您得到的排列偏向于那些早期项目不在它们的原始位置上的模式。

（这比较微妙，例如1可以被交换到更靠后的位置，然后通过一系列复杂的交换又被交换回来，但这些概率相对较小。）

- ShreevatsaR

Answer 4

这种现象最好的解释来自Jeff Atwood在他的 CodingHorror 博客（The Danger of Naïveté）中。

使用这段代码模拟三张随机洗牌...

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来正确（随机地）洗牌。

- Robert Cartaino

---

你确定那不是“卡尔达诺”吗？ ;) - erickson

有没有非数学答案？请查看Joel Coehoorn的回答下面的评论。 - nonopolarity

Answer 5

这里有另一个直觉：单次洗牌交换无法在不至少存在2路对称性的情况下创建占据位置的概率对称性。将三个位置分别称为A、B和C。现在假设a是卡片2位于位置A的概率，b是其位于位置B的概率，c是其位于位置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的概率是它一开始就在那里的概率乘以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与其他卡片之一交换开始的。在这种情况下，在交换之前存在两种对称性，因为A和C位置上的卡片1的概率相等。所以实际上，卡片1可能具有对称概率，并且最终以相等概率出现在三个位置上。这对所有后续交换都成立。但是卡片2在第一次交换后以概率(1/3,2/3,0)出现在三个位置上，同样地，卡片3以概率(1/3,0,2/3)出现在三个位置上。因此，无论我们进行多少次后续交换，卡片2或3永远不可能具有完全相同的在三个位置上占据的概率。

- dewtell

Answer 6

请见Coding Horror的文章《The Danger of Naïveté》（链接：https://blog.codinghorror.com/the-danger-of-naivete/）。简单来说（假设有3张牌）：天真洗牌会得到33（27）种可能的牌堆组合。这很奇怪，因为数学告诉我们，一个由3张牌组成的牌堆只有3！或6种可能的组合方式。在KFY洗牌中，我们从初始顺序开始，先从第三个位置和其中一张牌交换，然后再从第二个位置和剩下两张牌交换。

- eKek0

Answer 7

简单来说，该算法有52^52种可能的运行方式，但只有52！种52张卡牌的排列方式。为了使算法公平，它需要等概率地产生每个排列。52^52不是52!的整数倍，因此某些排列比其他排列更可能出现。

- user44511

Answer 8

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

1）只考虑3张牌。

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

3）因此，如果我们看第二个算法：

“1” 最终出现在 a[0] 的概率： 当生成的随机数为 0 时，有 1 种情况是 (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的概率出现在任何插槽中。

- nonopolarity

Answer 9

虽然不需要另一个答案，但我认为值得尝试去弄清楚Fisher-Yates算法为什么是均匀的。

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

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

通过条件概率来分解，项目i最终落在插槽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 / N-j。

请注意，在第一个术语中，所有分子都会取消后续的分母（即N-1取消，N-2取消，一直到N-j+1取消，只剩下N-j / N）。

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

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

如预期。

为了更加普及“简单洗牌”，它缺少的特定属性被称为可交换性。由于洗牌方式的“路径依赖性”（即创建输出时遵循的27条路径之一），您无法将不同的分量随机变量视为可以以任何顺序出现。实际上，这可能是随机抽样中为什么可交换性很重要的动机示例。

- ely

Answer 10

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个桶中，无论你怎么做，一些桶里都会有比其他桶更多的弹珠，你能达到的最好结果是1号到6号桶依次放4、4、4、5、5、5个弹珠。

朴素洗牌的根本问题在于交换次数太多，要完全洗牌3张牌，只需要进行2次交换，第二次交换只需要在前两张牌中进行，因为第三张牌已经有1/3的机会被交换。继续交换牌将增加某张牌被交换的机会，而这些机会只有在你的总交换组合数可被6整除时才会平均到1/3、1/3、1/3。

- Atilio Jobson