为什么这个简单的洗牌algorithm产生有偏见的结果? 什么是一个简单的原因?

看来这个简单的洗牌algorithm会产生有偏见的结果:

# 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张卡被使用),并运行10000次,并计算结果,你会看到结果是倾向于某些模式…

问题是…它会发生什么简单的解释?

正确的解决scheme是使用类似的东西

 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:感谢这里的人们指出,它需要兰特($我,51),它正确洗牌。

这是这些replace的完全概率树。

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

所以,虽然这个答案其实并不算是一个纯粹的math答案,但你只需要评估随机函数可能发生的所有可能的方式,并看看最终的输出。

看到这个:
Naïveté(编码恐怖)的危险

让我们看看你的三张卡片组作为例子。 使用3张牌组后,洗牌后的牌组只有6个可能的订单: 123, 132, 213, 231, 312, 321.

使用第一种algorithm,代码中有27种可能的path(结果),这取决于rand()函数在不同点的结果。 这些结果中的每一个都是同样可能的(无偏见的)。 这些结果中的每一个将映射到来自以上6个可能的“真实”洗牌结果列表的相同的单个结果。 我们现在有27个项目和6个水桶。由于27不能被6整除,所以这6个组合中的一些必须被过度代表。

第二种algorithm有6种可能的结果,它们完全符合6种可能的“真实”洗牌结果,并且它们都应该随时间平均地表示。

这很重要,因为在第一个algorithm中过度表示的桶不是随机的。 select偏见的桶是可重复和可预测的。 所以,如果你正在build立在线扑克游戏,并使用第一种algorithm,黑客可能会发现你使用了天真的sorting,从这个工作出发,某些套牌安排比其他安排更有可能发生。 然后他们可以相应地下注。 他们会失去一些,但是他们会赢得比输的更多的东西,很快就会让你失去业务。

从你对其他答案的评论看来,你似乎在寻找的不仅仅是解释为什么分布不是均匀分布(可分解的答案是一个简单的分布),而且是为什么它是“直观的”解释实际上很不统一

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

这就是“直观”的解释:在你的第一个algorithm中,早期的项目比后面的项目更有可能被置换出来,所以你得到的排列倾向于早期项目不在原始位置的模式。

(比这更微妙一点,例如1可以交换到后面的位置,并且最终通过一系列复杂的掉期交换到位,但这些概率相对较不重要。)

我见过的最好的解释是来自Jeff Atwood在他的CodingHorror博客( Naïveté 的危险 )。

使用此代码来模拟3卡随机随机播放…

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

…你得到这个分配。

三卡洗牌的分配

混洗码(上面)导致3 ^ 3(27)可能的牌组合。 但math告诉我们,真的只有3! 或3张牌组合的6种可能的组合。 所以一些组合是过度代表。

您需要使用Fisher-Yates随机播放function来正确(随机)洗牌一副牌。

这里有另一个直觉:除非至less双向对称性已经存在,否则单个随机交换不能产生占据位置的概率的对称性。 调用三个位置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与A交换的概率等。现在减去前两个等式,我们得到:

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

这意味着因为我们假设a = b,那么a'!= b'(虽然在给定足够的掉期的情况下,差值将随着时间的推移接近0)。 但是,由于'+ b'+ c'= 1,如果a'!= b',那么两者都不能等于c',即1/3。 所以如果这三个概率在交换之前就开始了所有的不同,那么在交换之后它们也都是不同的。 而且不pipe哪个位置被交换,我们只是在上面交换variables的angular色。

现在,第一个交换是通过将位置A的卡1与其他卡之一交换来开始的。 在这种情况下,交换之前存在双向对称,因为位置B处的卡1的概率=位置C处的卡1的概率= 0.因此事实上,卡1可以以对称概率结束,并且它最终结束在三个位置中的每一个以相等的概率。 所有后续掉期都是如此。 但是卡片2在第一次交换之后以三次概率(1/3,2/3,0)卷绕在三个位置,同样卡片3以三次概率(1/3,0,2/3)卷绕在三个位置, 。 所以无论我们做了多less次后续掉期,我们都不会拿到第2张或第3张牌,这三张牌的占有率完全相同。

看编码恐怖的postNaïveté的危险 。

基本上(应付3张牌):

幼稚的洗牌导致33(27)个可能的套牌组合。 这很奇怪,因为math告诉我们真的只有3个! 或3张牌组合的6种可能的组合。 在KFY洗牌中,我们从最初的命令开始,从三张牌中的任何一张交换第三张牌,然后从剩下的两张牌再次从第二张换成另一张牌。

简单的答案是这个algorithm有52 ^ 52个可能的运行方式,但是只有52个! 可能安排52张牌。 为了algorithm是公平的,它需要同样地产生这些安排中的每一个。 52 ^ 52不是52的整数倍! 因此,一些安排必须比其他安排更可能。

说明性的方法可能是这样的:

1)只考虑3张牌。

2)对于algorithm给出均匀分布的结果,“1”结尾为[0]的机会必须是1/3,而结尾在[1]中的“2”的机会也必须是1/3等等。

3)所以如果我们看第二个algorithm:

“1”结束于a [0]的概率:当0是生成的随机数时,因此(0,1,2)中的1个,因此是3中的1个= 1/3

“2”结束于[1]的概率:第一次没有交换到[0],第二次没有交换到[2]时:2/3 * 1 / 2 = 1/3

“3”以“[2]”结尾的概率:第一次没有交换到[0]时,第二次没有交换到[1]:2/3 * 1 / 2 = 1/3

他们完全是三分之一,我们在这里没有看到任何错误。

4)如果我们试图计算在第一个algorithm中“1”结束为[0]的概率,计算会有点长,但是正如lassevk答案的例子所示,它是9/27 = 1 / 3,但结尾为[1]的“2”有8/27的机会,以“3”结尾的机会为9/27 = 1/3。

结果,作为[1]结束的“2”不是1/3,因此该algorithm将产生相当偏斜的结果(大约3.7%的误差,而不是可忽略的情况,例如3/10000000000000 = 0.00000000003%)。

5)Joel Coehoorn所拥有的certificate,实际上可以certificate有些案例会被过度代表。 我认为为什么它是n ^ n的解释是这样的:在每次迭代中,有n个可能性,随机数可以是,所以在n次迭代之后,可以有n ^ n个情况= 27。在n = 3的情况下均匀排列的数目(n!= 3!= 6),所以有些结果是过度表示的。 他们的代表性过高,而不是出现4次,而是出现了5次,所以如果从1到52的初始顺序洗牌数百万次,超出代表性的情况将显示500万而不是400万次,这是相当大的差距。

6)我认为过度表示被显示,但是“为什么”过度表示会发生?

7)algorithm的最终testing是正确的,即任何数字有1 / n的概率在任何时隙结束。

这是一个很好的卡洗牌马尔可夫链分析 。 哦,等等,这都是math。 抱歉。 🙂

Naivealgorithm如下所示选取n的值:

n = rand(3)

n = rand(3)

n = rand(3)

3 ^ 3个可能的组合

1,1,1,1,1,2 …. 3,3,2 3,3,3(27种组合)lassevk的答案显示了这些组合之间的分配。

更好的algorithm会:

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个桶,不pipe你做什么,有的水桶比其他水池的弹子数量要多,最好的办法是用4,4,4,5,5,5弹子桶1至6。

天真洗牌的根本问题是,掉换次数太多,完全洗牌3张牌,只需要做2次换牌,而第二次换牌只需要在前两张牌中,因为第三张牌已经有1/3被交换的机会。 继续换牌会给予给定的牌更换的机会,如果你的总换牌组合可以被6整除,这些机会将只会达到1/3,1/3,1/3。

并不需要另一个答案,但我觉得应该仔细研究为什么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). 

并从那里recursion地回到第一次绘制。

现在,元素i在第一次绘制时没有被绘制的概率是N-1 / N 在第二次抽签的时候没有画出来的概率是N-2 / N-1 ,依此类推。

所以,我们得到了i在第一个j-1抽签中没有得到的元素的概率:

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

当然我们知道在第j轮得到的条件是没有被提前绘制的概率就是1 / Nj

请注意,在第一项中,分子全部抵消后面的分母(即N-1抵消, N-2抵消,一直到N-j+1抵消,只留下Nj / N )。

所以元素i出现在时隙j的总体概率是:

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

如预期。

为了对“简单洗牌”做更多的概括,它所缺乏的特定属性被称为可交换性 。 由于创build混洗方式的“path依赖性”(即27个path中的哪一个被创build输出),所以不能将不同的分量随机variables视为可以以任何顺序出现。 事实上,这也许为什么随机抽样中的可交换性很重要动机。