22

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

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

4

12 回答 12

38

看到这个：
天真的危险（编码恐怖）

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

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

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

这很重要，因为在第一个算法中过度表示的桶不是随机的。为偏差选择的桶是可重复和可预测的。 因此，如果您正在构建一个在线扑克游戏并使用第一种算法，那么黑客可能会发现您使用的是幼稚排序，并由此得出某些牌组安排比其他牌组更有可能发生。然后他们可以相应地下注。他们会失去一些，但他们会赢得比失去更多的东西，并很快让你破产。

于 2009-05-13T17:21:00.213 回答
26

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

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

所以虽然这个答案确实很重要，但它不是一个纯粹的数学答案，你只需要评估随机函数可以走的所有可能方式，并查看最终输出。

于 2009-05-13T20:18:27.660 回答
22

从您对其他答案的评论来看，您似乎不仅在寻找关于为什么分布不是均匀分布的解释（为此，可分性答案很简单），而且还在寻找对它为什么的“直观”解释其实离制服还差得很远。

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

这就是“直观”的解释：在您的第一个算法中，较早的项目比后来的项目更容易被交换，因此您得到的排列偏向于早期项目不在其原始位置的模式。

（比这更微妙一些，例如 1 可以被交换到后面的位置，但最终仍会通过一系列复杂的交换被交换回原位，但这些概率相对不那么重要。）

于 2009-05-13T20:52:10.693 回答
15

我看到的关于这种效果的最佳解释来自 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]);
}

...你得到这个分布。

3张牌洗牌分配

洗牌代码（上图）产生 3^3 (27) 种可能的牌组组合。但数学告诉我们，真的只有 3 个！或 3 张牌组的 6 种可能组合。所以一些组合被过度代表了。

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

于 2009-05-13T17:21:53.440 回答
3

这是另一种直觉：除非至少已经存在 2 向对称性，否则单次 shuffle 交换不能在占据位置的概率上创建对称性。调用三个位置 A、B 和 C。现在让 a 是卡片 2 在位置 A 的概率，b 是卡片 2 在位置 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 结束的概率是它已经在那里的概率乘以位置 A 不参与交换的时间的 2/3，再加上它在位置 C 的概率乘以 1 /3 C 与 A 交换的概率，等等。现在减去前两个方程，我们得到：

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 占据所有三个位置的概率完全相同。

于 2009-05-13T20:48:32.730 回答
2

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

基本上（假设 3 张牌）：

天真的洗牌会产生 33 (27) 种可能的牌组组合。这很奇怪，因为数学告诉我们实际上只有 3 个！或 3 张牌组的 6 种可能组合。在 KFY 洗牌中，我们从初始顺序开始，从第三个位置与三张牌中的任何一张交换，然后从第二个位置再次与剩余的两张牌交换。

于 2009-05-13T17:34:56.693 回答
1

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

于 2009-05-15T01:40:42.427 回答
1

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

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，但以 a[1] 结尾的“2”有 8/27 的机会，而以 a[2] 结尾的“3”有 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 的概率最终出现在任何插槽中。

于 2009-05-18T09:12:49.100 回答
0

这是对洗牌马尔可夫链的一个很好的分析。哦，等等，这都是数学。对不起。:)

于 2009-05-13T23:50:01.277 回答
0

Naive 算法选择 n 的值，如下所示：

n = 兰德(3)

n = 兰德(3)

n = 兰德(3)

3^3 种可能的 n 组合

1,1,1, 1,1,2....3,3,2 3,3,3（27 种组合）lassevk 的答案显示了这些组合的牌之间的分布情况。

更好的算法：

n = 兰德(3)

n = 兰德(2)

嗯！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。

于 2009-05-18T16:43:33.823 回答
0

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

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

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

用条件概率分解它，Pr(item i ends 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 / 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

正如预期的那样。

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

于 2014-10-31T13:26:13.567 回答
0

The clearest answer to show the first algorithm fails is to view the algorithm in question as a Markov chain of n steps on the graph of n! vertices of all the permutation of n natural numbers. The algorithm hops from one vertex to another with a transition probability. The first algorithm gives the transition probability of 1/n for each hop. There are n^n paths the probability of each of which is 1/n^n. Suppose the final probability of landing on each vertex is 1/n! which is a reduced fraction. To achieve that there must be m paths with the same final vertex such that m/n^n=1/n! or n^n = mn! for some natural number m, or that n^n is divisible by n!. But that is impossible. Otherwise, n has to be divisible by n-1 which is only possible when n=2. We have contradiction.

于 2018-06-27T21:39:45.830 回答