为什么这个简单的混洗算法会产生有偏差的结果？一个简单的原因是什么？
这个简单的混洗算法似乎会产生有偏差的结果：
# 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:感谢这里的人们指出它需要是兰特($i，51)才能正确地洗牌。
回答 12
Stack Overflow用户
发布于 2009-05-13 20:18:28
这是这些替换的完整概率树。
让我们假设您从序列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所以，虽然这个答案实际上很重要，但它不是一个纯粹的数学答案，你只需要评估随机函数可以达到的所有可能的方式，并查看最终的输出。
Stack Overflow用户
发布于 2009-05-13 17:21:00
请看以下内容：
The Danger of Naïveté (Coding Horror)
让我们以三张纸牌为例来看一下。使用3张牌组，洗牌后只有6种可能的牌组顺序：123, 132, 213, 231, 312, 321.
使用您的第一个算法，代码有27个可能的路径(结果)，这取决于rand()函数在不同点的结果。每一种结果的可能性都是相等的(无偏见)。这些结果中的每一个都将映射到上面列出的6个可能的“真正”洗牌结果中的同一个结果。我们现在有27件物品和6个桶来放它们。由于27不能被6整除，因此这6个组合中的一些组合必须过度表示。
对于第二种算法，有6种可能的结果精确地映射到6种可能的“真实”洗牌结果，并且随着时间的推移，它们都应该被平等地表示。
这一点很重要，因为在第一个算法中过度表示的存储桶不是随机的。为偏差选择的桶是可重复和可预测的。因此，如果你正在构建一个在线扑克游戏，并使用第一种算法，黑客可能会发现你使用了朴素的排序，并由此得出某些牌面排列比其他牌组更有可能发生。然后，他们可以相应地下注。他们会失去一些，但他们会赢得比失去的多得多，很快就会让你破产。
Stack Overflow用户
发布于 2009-05-13 20:52:11
从你对其他答案的评论中，似乎你不仅想要一个解释为什么分布不是均匀分布的解释(对于这个均匀分布，可除性答案是一个简单的)，而且还想要一个“直观”的解释，为什么它实际上是远离均匀分布()。
这是一种看待它的方式。假设您从初始数组[1, 2, ..., n] (其中n可能是3、52或其他任何值)开始，并应用两种算法中的一种。如果所有的排列都是均匀可能的，那么1留在第一个位置的概率应该是1/n。事实上，在第二个(正确的)算法中，它是1/n，因为当且仅当它没有第一次被交换时，1才会留在它的位置上，即，如果对rand(0,n-1)的初始调用返回0。
然而，在第一(错误)算法中，仅当第一次或任何其他时间- i.e都没有交换时，1才保持不变，仅当第一个rand返回0并且其他rands都没有返回0，其概率是( 1/n ) * (1-1/n)^(n-1)≈1/(ne)≈0.37/n，而不是1/n。
这就是“直观”的解释:在你的第一个算法中，较早的项目比较晚的项目更有可能被交换到不合适的位置，所以你得到的排列偏向于这样的模式，即较早的项目在其原始位置是而不是。
(这比这更微妙，例如，1可以被交换到更晚的位置，但通过一系列复杂的交换，最终仍然被交换回原来的位置，但这些概率相对较小。)
https://stackoverflow.com/questions/859253
复制相似问题
腾讯云开发者
