it seems that this simple shuffle algorithm will produce biased results:
似乎这个简单的shuffle算法会产生偏差的结果:
# 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;
}
you can try it... instead of using 52, use 3 (suppose only 3 cards are used), and run it 10,000 times and tally up the results, you will see that the results are skewed towards certain patterns...
你可以尝试...而不是使用52,使用3(假设只使用3张卡),并运行10,000次并计算结果,你会看到结果偏向某些模式......
the question is... what is a simple explanation that it will happen?
问题是......它会发生什么简单的解释?
the correct solution is to use something like
正确的解决方案是使用类似的东西
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;
}
but the question is... why the first method, seemingly also totally random, will make the results biased?
但问题是......为什么第一种方法,似乎也是完全随机的,会使结果产生偏差?
Update 1: thanks for folks here pointing out that it needs to be rand($i, 51) for it to shuffle correctly.
更新1:感谢这里的人们指出它需要rand($ i,51)才能正确地进行洗牌。
12 个解决方案
#1
Here's the complete probability tree for these replacements.
这是这些替换的完整概率树。
Let's assume that you start with the sequence 123, and then we'll enumerate all the various ways to produce random results with the code in question.
让我们假设您从序列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
Now, the fourth column of numbers, the one before the swap information, contains the final outcome, with 27 possible outcomes.
现在,第四列数字,即交换信息之前的数字,包含最终结果,有27种可能的结果。
Let's count how many times each pattern occurs:
让我们计算每个模式出现的次数:
123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
27 times total
If you run the code that swaps at random for an infinite number of times, the patterns 132, 213 and 231 will occur more often than the patterns 123, 312, and 321, simply because the way the code swaps makes that more likely to occur.
如果运行随机交换无限次的代码,则模式132,213和231将比模式123,312和321更频繁地发生,这仅仅是因为代码交换的方式使得更可能发生。
Now, of course, you can say that if you run the code 30 times (27 + 3), you could end up with all the patterns occuring 5 times, but when dealing with statistics you have to look at the long term trend.
现在,当然,你可以说,如果你运行代码30次(27 + 3),你最终可能会出现5次所有模式,但在处理统计数据时,你必须看看长期趋势。
Here's C# code that explores the randomness for one of each possible pattern:
这是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);
}
}
}
This outputs:
123: 4
132: 5
213: 5
231: 5
312: 4
321: 4
So while this answer does in fact count, it's not a purely mathematical answer, you just have to evaluate all possible ways the random function can go, and look at the final outputs.
因此,虽然这个答案确实可以计算,但这不是一个纯数学答案,你只需要评估随机函数可以采用的所有可能方法,并查看最终输出。
#2
See this:
The Danger of Naïveté (Coding Horror)
看到:Naïveté的危险(编码恐怖)
Let's look at your three card deck as an example. Using a 3 card deck, there are only 6 possible orders for the deck after a shuffle: 123, 132, 213, 231, 312, 321.
让我们看一下你的三张牌组。使用3张牌组,洗牌后甲板上只有6种可能的订单:123,132,213,231,312,321。
With your 1st algorithm there are 27 possible paths (outcomes) for the code, depending on the results of the rand()
function at different points. Each of these outcomes are equally likely (unbiased). Each of these outcomes will map to the same single result from the list of 6 possible "real" shuffle results above. We now have 27 items and 6 buckets to put them in. Since 27 is not evenly divisible by 6, some of those 6 combinations must be over-represented.
使用第一个算法,代码有27种可能的路径(结果),具体取决于不同点的rand()函数的结果。这些结果中的每一个都是同等可能的(无偏见的)。这些结果中的每一个都将映射到上面6个可能的“真实”混洗结果列表中的相同单个结果。我们现在有27个项目和6个桶用于放入它们。由于27个不能被6整除,因此这6个组合中的一些必须过度表示。
With the 2nd algorithm there are 6 possible outcomes that map exactly to the 6 possible "real" shuffle results, and they should all be represented equally over time.
使用第二种算法,有6种可能的结果可以准确地映射到6种可能的“真实”混洗结果,并且它们应该随时间平均表示。
This is important because the buckets that are over-represented in the first algorithm are not random. The buckets selected for the bias are repeatable and predictable. So if you're building an online poker game and use the 1st algorithm a hacker could figure out you used the naive sort and from that work out that certain deck arrangements are much more likely to occur than others. Then they can place bets accordingly. They'll lose some, but they'll win much more than they lose and quickly put you out of business.
这很重要,因为在第一个算法中过度表示的桶不是随机的。为偏差选择的桶是可重复且可预测的。因此,如果你正在建立一个在线扑克游戏并使用第一种算法,那么黑客可能会发现你使用了天真的排序,并且从那项工作中可以看出某些甲板安排比其他人更容易发生。然后他们可以相应地下注。他们会失去一些,但他们会赢得比失败更多的东西,并迅速让你破产。
#3
From your comments on the other answers, it seems that you are looking not just for an explanation of why the distribution is not the uniform distribution (for which the divisibility answer is a simple one) but also an "intuitive" explanation of why it is actually far from uniform.
根据您对其他答案的评论,您似乎不仅仅想要解释为什么分布不是均匀分布(对于哪个分布是简单的分布),而是对其原因的“直观”解释。实际上远非均匀。
Here's one way of looking at it. Suppose you start with the initial array [1, 2, ..., n]
(where n might be 3, or 52, or whatever) and apply one of the two algorithms. If all permutations are uniformly likely, then the probability that 1 remains in the first position should be 1/n
. And indeed, in the second (correct) algorithm, it is 1/n
, as 1 stays in its place if and only if it is not swapped the first time, i.e. iff the initial call to rand(0,n-1)
returns 0.
However, in the first (wrong) algorithm, 1 remains untouched only if it is neither swapped the first time nor any other time — i.e., only if the first rand
returns 0 and none of the other rand
s returns 0, the probability of which is (1/n) * (1-1/n)^(n-1) ≈ 1/(ne) ≈ 0.37/n, not 1/n.
这是一种看待它的方式。假设您从初始数组[1,2,...,n](其中n可能是3或52或其他)开始,并应用这两种算法中的一种。如果所有排列均匀可能,则1保持在第一位置的概率应为1 / n。事实上,在第二个(正确的)算法中,它是1 / n,当且仅当它第一次没有交换时,1保持在其位置,即iff对rand(0,n-1)的初始调用返回但是,在第一个(错误的)算法中,1只有在第一次或任何其他时间都没有交换时仍然保持不变 - 即,只有当第一个兰特返回0并且其他任何一个都没有返回0时,概率为0这是(1 / n)*(1-1 / n)^(n-1)≈1/(ne)≈0.37/ n,而不是1 / n。
And that's the "intuitive" explanation: in your first algorithm, earlier items are much more likely to be swapped out of place than later items, so the permutations you get are skewed towards patterns in which the early items are not in their original places.
这就是“直观”的解释:在你的第一个算法中,早期的项目比后面的项目更有可能被替换掉,所以你得到的排列倾向于早期项目不在原始位置的模式。
(It's a bit more subtle than that, e.g. 1 can get swapped into a later position and still end up getting swapped back into place through a complicated series of swaps, but those probabilities are relatively less significant.)
(它比这更微妙,例如1可以换成后来的位置,并且最终通过一系列复杂的掉期交换回来,但这些概率相对不太重要。)
#4
The best explanation I've seen for this effect was from Jeff Atwood on his CodingHorror blog (The Danger of Naïveté).
我见过这个效果的最佳解释来自Jeff Atwood的CodingHorror博客(Naïveté的危险)。
Using this code to simulate a 3-card random shuffle...
使用此代码模拟3张牌随机随机播放......
for (int i = 0; i < cards.Length; i++)
{
int n = rand.Next(cards.Length);
Swap(ref cards[i], ref cards[n]);
}
...you get this distribution.
...你得到这个发行版。
The shuffle code (above) results in 3^3 (27) possible deck combinations. But the mathematics tell us that there are really only 3! or 6 possible combinations of a 3 card deck. So some of the combinations are over-represented.
随机码(上图)导致3 ^ 3(27)个可能的卡组合。但是数学告诉我们真的只有3个!或3张牌组的6种可能组合。所以有些组合过度代表了。
You would need to use a Fisher-Yates shuffle to properly (randomly) shuffle a deck of cards.
你需要使用Fisher-Yates shuffle来正确地(随机地)洗牌一副纸牌。
#5
Here's another intuition: the single shuffle swap can't create symmetry in the probability of occupying a position unless at least 2-way symmetry already exists. Call the three positions A, B, and C. Now let a be the probability of card 2 being in position A, b be the probability of card 2 being in position B, and c be the probability of it being in position C, prior to a swap move. Assume that no two probabilities are the same: a!=b, b!=c, c!=a. Now compute the probabilities a', b', and c' of the card being in these three positions following a swap. Let's say that this swap move consists of position C being swapped with one of the three positions at random. Then:
这是另一种直觉:单一的随机交换不能在占据位置的概率中产生对称性,除非至少已经存在双向对称。调用三个位置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.
That is, the probability that the card winds up in position A is the probability it was already there times the 2/3 of the time position A isn't involved in the swap, plus the probability that it was in position C times the 1/3 probability that C swapped with A, etc. Now subtracting the first two equations, we get:
也就是说,卡在位置A结束的概率是它已经存在的概率,即时间位置A的2/3没有参与交换,加上它在位置C乘以1的概率。 / 3与A交换的概率等等。现在减去前两个方程,我们得到:
a' - b' = (a - b)*2/3
which means that because we assumed a!=b, then a'!=b' (though the difference will approach 0 over time, given enough swaps). But since a'+b'+c'=1, if a'!=b', then neither can be equal to c' either, which is 1/3. So if the three probabilities start off all different before a swap, they will also all be different after a swap. And this would hold no matter which position was swapped - we just interchange the roles of the variables in the above.
这意味着因为我们假设了一个!= b,然后是'!= b'(尽管差异将随时间推移接近0,给定足够的交换)。但由于'+ b'+ c'= 1,如果是'!= b',那么两者都不能等于c',即1/3。因此,如果三个概率在交换之前开始全部不同,那么在交换之后它们也将是不同的。无论交换哪个位置,这都会成立 - 我们只是在上面交换变量的作用。
Now the very first swap started by swapping card 1 in position A with one of the others. In this case, there was two way symmetry before the swap, because the probability of card 1 in position B = probability of card 1 in position C = 0. So in fact, card 1 can wind up with symmetric probabilities and it does end up in each of the three positions with equal probability. This remains true for all subsequent swaps. But card 2 winds up in the three positions after the first swap with probability (1/3, 2/3, 0), and likewise card 3 winds up in the three positions with probability (1/3, 0, 2/3). So no matter how many subsequent swaps we do, we will never wind up with card 2 or 3 having exactly the same probability of occupying all three positions.
现在,第一次交换开始于将卡1换成位置A与其他一个。在这种情况下,在交换之前存在双向对称,因为位置B中的卡1的概率=卡1在位置C = 0的概率。因此实际上,卡1可以结束对称概率并且它最终结束在三个位置中的每个位置具有相同的概率。所有后续掉期都是如此。但是卡片2在第一次交换之后在三个位置卷起概率(1 / 3,2 / 3,0),同样卡3在三个位置卷起概率(1 / 3,0,2 / 3) 。因此,无论我们进行多少次后续交换,我们都不会因为卡2或3具有完全相同的占据所有三个位置的概率而结束。
#6
See the Coding Horror post The Danger of Naïveté.
参见Naïveté的危险编码恐怖片。
Basically (suposing 3 cards):
基本上(附3张卡):
The naive shuffle results in 33 (27) possible deck combinations. That's odd, because the mathematics tell us that there are really only 3! or 6 possible combinations of a 3 card deck. In the KFY shuffle, we start with an initial order, swap from the third position with any of the three cards, then swap again from the second position with the remaining two cards.
天真的洗牌导致33(27)种可能的套牌组合。这很奇怪,因为数学告诉我们真的只有3个!或3张牌组的6种可能组合。在KFY shuffle中,我们从初始订单开始,从第三个位置与三个卡中的任何一个交换,然后从第二个位置再次与剩余的两个卡交换。
#7
The simple answer is that there are 52^52 possible ways for this algorithm to run, but there are only 52! possible arrangements of 52 cards. For the algorithm to be fair, it needs to produce each of these arrangements equally likely. 52^52 is not an integer multiple of 52!. Therefore, some arrangements must be more likely than others.
简单的答案是这种算法有52 ^ 52种可能的运行方式,但只有52种!可能安排52张卡。为了使算法公平,它需要同样可能产生这些安排中的每一个。 52 ^ 52不是52的整数倍!因此,某些安排必须比其他安排更可能。
#8
an illustrative approach might be this:
一个说明性的方法可能是:
1) consider only 3 cards.
1)只考虑3张牌。
2) for the algorithm to give evenly distributed results, the chance of "1" ending up as a[0] must be 1/3, and the chance of "2" ending up in a[1] must be 1/3 too, and so forth.
2)对于算法给出均匀分布的结果,“1”结束为[0]的几率必须为1/3,并且在[1]中结束的“2”的概率必须为1/3等等。
3) so if we look at the second algorithm:
3)所以如果我们看第二个算法:
probability that "1" ends up at a[0]: when 0 is the random number generated, so 1 case out of (0,1,2), therefore, is 1 out of 3 = 1/3
“1”在[0]处结束的概率:当0是生成的随机数时,因此,(0,1,2)中的1例是1 = 3 = 1/3
probability that "2" ends up at a[1]: when it didn't get swapped to a[0] the first time, and it didn't get swapped to a[2] the second time: 2/3 * 1/2 = 1/3
“2”在[1]处结束的概率:第一次没有交换到[0]时,第二次没有交换到[2]:2/3 * 1 / 2 = 1/3
probability that "3" ends up at a[2]: when it didn't get swapped to a[0] the first time, and it didn't get swapped to a[1] the second time: 2/3 * 1/2 = 1/3
“3”在[2]处结束的概率:第一次没有交换到[0]时,第二次没有交换到[1]:2/3 * 1 / 2 = 1/3
they are all perfectly 1/3, and we don't see any error here.
它们都是完美的1/3,我们在这里看不到任何错误。
4) if we try to calculate the probability of of "1" ending up as a[0] in the first algorithm, the calculation will be a bit long, but as the illustration in lassevk's answer shows, it is 9/27 = 1/3, but "2" ending up as a[1] has a chance of 8/27, and "3" ending up as a[2] has a chance of 9/27 = 1/3.
4)如果我们试图计算第一个算法中“1”结束为[0]的概率,计算会有点长,但正如lassevk的答案所示,它是9/27 = 1 / 3,但是作为[1]结束的“2”有8/27的机会,而结束为[2]的“3”有可能是9/27 = 1/3。
as a result, "2" ending up as a[1] is not 1/3 and therefore the algorithm will produce pretty skewed result (about 3.7% error, as opposed to any negligible case such as 3/10000000000000 = 0.00000000003%)
结果,结果为[1]的“2”不是1/3,因此算法会产生相当偏差的结果(大约3.7%的误差,而不是任何可忽略不计的情况,如3/10000000000000 = 0.00000000003%)
5) the proof that Joel Coehoorn has, actually can prove that some cases will be over-represented. I think the explanation that why it is n^n is this: at each iteration, there are n possibility that the random number can be, so after n iterations, there can be n^n cases = 27. This number doesn't divid the number of permuations (n! = 3! = 6) evenly in the case of n = 3, so some results are over-represented. they are over-represented in a way that instead of showing up 4 times, it shows up 5 times, so if you shuffle the cards millions of times from the initial order of 1 to 52, the over-represented case will show up 5 million times as opposed to 4 million times, which is quite big a difference.
5)Joel Coehoorn的证据,实际上可以证明某些案件的代表性过高。我认为为什么它是n ^ n的解释是这样的:在每次迭代时,随机数都有可能是,所以在n次迭代之后,可能有n ^ n个情况= 27.这个数字不是divid在n = 3的情况下,均匀的数量(n!= 3!= 6),因此一些结果被过度表示。它们的代表性过高,而不是出现4次,它会出现5次,所以如果你从最初的1到52的顺序洗牌数百万次,过度代表的案例将显示500万时间而不是400万次,这是相当大的差异。
6) i think the over-representation is shown, but "why" will the over-representation happen?
6)我认为过度表现会被显示出来,但过度表现的“为什么”会发生?
7) an ultimate test for the algorithm to be correct is that any number has a 1/n probability to end up at any slot.
7)算法正确的最终测试是任何数字在任何时隙都有1 / n概率结束。
#9
Here's a great analysis of a card shuffling Markov chains. Oh wait, that's all math. Sorry. :)
这是一张关于洗牌马尔可夫链的卡片的精彩分析。哦等等,这都是数学。抱歉。 :)
#10
The Naive algorithm picks the values of n like so:
朴素算法选择n的值,如下所示:
n = rand(3)
n =兰特(3)
n = rand(3)
n =兰特(3)
n = rand(3)
n =兰特(3)
3^3 possible combinations of n
n ^的3 ^ 3种可能的组合
1,1,1, 1,1,2....3,3,2 3,3,3 (27 combinations) lassevk's answer shows the distribution among the cards of these combinations.
1,1,1,1,1,2 ...... 3,3,2 3,3,3(27种组合)lassevk的答案显示了这些组合的卡片之间的分布。
the better algorithm does:
更好的算法:
n = rand(3)
n =兰特(3)
n = rand(2)
n =兰特(2)
n! possible combinations of n
N! n的可能组合
1,1, 1,2, 2,1 2,2 3,1 3,2 (6 combinations, all of them giving a different result)
1,1,1,2,2,1,2,2,3,3,2(6种组合,所有这些都给出了不同的结果)
As mentioned in the other answers, if you take 27 attempts to get 6 results, you cannot possibly attain the 6 results with even distribution, since 27 is not divisible by 6. Put 27 marbles into 6 buckets and no matter what you do, some buckets will have more marbles than others, the best you can do is 4,4,4,5,5,5 marbles for buckets 1 through 6.
正如其他答案中所提到的,如果你试图获得6次结果,你就不可能达到均匀分布的6个结果,因为27不能被6整除。将27个弹珠放入6个桶中,无论你做什么,一些水桶比其他水桶有更多的弹珠,你能做的最好的是水桶1到6的4,4,4,5,5,5弹珠。
the fundamental problem with the naive shuffle is that swaps too many times, to shuffle 3 cards completely, you need only do 2 swaps, and the second swap need only be among the first two cards, since the 3rd card already had a 1/3 chance of being swapped. to continue to swap cards will impart more chances that a given card will be swapped, and these chances will only even out to 1/3, 1/3, 1/3 if your total swap combinations is divisible by 6.
天真洗牌的根本问题在于交换太多次,完全洗牌3张牌,你只需要进行2次掉期,而第二次掉牌只需要在前两张牌中,因为第3张牌已经有1/3被交换的机会。继续交换卡片会给予更换一张特定卡片的机会,如果你的总交换组合可以被6整除,这些机会只会达到1 / 3,1 / 3,1 / 3。
#11
Not that another answer is needed, but I found it worthwhile to try to work out exactly why Fisher-Yates is uniform.
不是说需要另一个答案,但我发现值得尝试找出Fisher-Yates为什么是统一的。
If we are talking about a deck with N items, then this question is: how can we show that
如果我们谈论的是一个有N个项目的牌组,那么这个问题就是:我们怎么能表明这一点
Pr(Item i ends up in slot j) = 1/N?
Breaking it down with conditional probabilities, Pr(item i ends up at slot j)
is equal to
用条件概率将其分解,Pr(项目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).
and from there it expands recursively back to the first draw.
从那里它递归地扩展回第一次抽奖。
Now, the probability that element i
was not drawn on the first draw is N-1 / N
. And the probability that it was not drawn on the second draw conditional on the fact that it was not drawn on the first draw is N-2 / N-1
and so on.
现在,在第一次抽签中没有绘制元素i的概率是N-1 / N.并且在第二次抽签中没有绘制的概率条件是它没有在第一次抽签中绘制的概率是N-2 / N-1等。
So, we get for the probability that element i
was not drawn in the first j-1
draws:
所以,我们得到的元素i没有在第一个j-1绘制中绘制的概率:
(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)
and of course we know that the probability that it is drawn at round j
conditional on not having been drawn earlier is just 1 / N-j
.
当然,我们知道在没有先前绘制的条件下在第j轮绘制的概率仅为1 / N-j。
Notice that in the first term, the numerators all cancel the subsequent denominators (i.e. N-1
cancels, N-2
cancels, all the way to N-j+1
cancels, leaving just N-j / N
).
请注意,在第一项中,分子全部取消后续分母(即N-1取消,N-2取消,一直到N-j + 1取消,只留下N-j / N)。
So the overall probability of element i
appearing in slot j
is:
因此,元素i出现在插槽j中的总体概率为:
[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j)
= 1/N
as expected.
To get more general about the "simple shuffle", the particular property that it is lacking is called exchangeability. Because of the "path dependence" of the way the shuffle is created (i.e. which of the 27 paths is followed to create the output), you are not able to treat the different component-wise random variables as though they can appear in any order. In fact, this is perhaps the motivating example for why exchangeability matters in random sampling.
为了更加全面地了解“简单洗牌”,它缺乏的特殊属性称为可交换性。由于shuffle创建方式的“路径依赖性”(即,遵循27条路径中的哪条路径来创建输出),您无法将不同的分量随机变量视为可以按任何顺序出现。事实上,这可能是为什么可交换性在随机抽样中起作用的动机实例。
#12
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.
显示第一个算法失败的最明确答案是将所讨论的算法视为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时才可能。我们有矛盾。
#1
Here's the complete probability tree for these replacements.
这是这些替换的完整概率树。
Let's assume that you start with the sequence 123, and then we'll enumerate all the various ways to produce random results with the code in question.
让我们假设您从序列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
Now, the fourth column of numbers, the one before the swap information, contains the final outcome, with 27 possible outcomes.
现在,第四列数字,即交换信息之前的数字,包含最终结果,有27种可能的结果。
Let's count how many times each pattern occurs:
让我们计算每个模式出现的次数:
123 - 4 times
132 - 5 times
213 - 5 times
231 - 5 times
312 - 4 times
321 - 4 times
=============
27 times total
If you run the code that swaps at random for an infinite number of times, the patterns 132, 213 and 231 will occur more often than the patterns 123, 312, and 321, simply because the way the code swaps makes that more likely to occur.
如果运行随机交换无限次的代码,则模式132,213和231将比模式123,312和321更频繁地发生,这仅仅是因为代码交换的方式使得更可能发生。
Now, of course, you can say that if you run the code 30 times (27 + 3), you could end up with all the patterns occuring 5 times, but when dealing with statistics you have to look at the long term trend.
现在,当然,你可以说,如果你运行代码30次(27 + 3),你最终可能会出现5次所有模式,但在处理统计数据时,你必须看看长期趋势。
Here's C# code that explores the randomness for one of each possible pattern:
这是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);
}
}
}
This outputs:
123: 4
132: 5
213: 5
231: 5
312: 4
321: 4
So while this answer does in fact count, it's not a purely mathematical answer, you just have to evaluate all possible ways the random function can go, and look at the final outputs.
因此,虽然这个答案确实可以计算,但这不是一个纯数学答案,你只需要评估随机函数可以采用的所有可能方法,并查看最终输出。
#2
See this:
The Danger of Naïveté (Coding Horror)
看到:Naïveté的危险(编码恐怖)
Let's look at your three card deck as an example. Using a 3 card deck, there are only 6 possible orders for the deck after a shuffle: 123, 132, 213, 231, 312, 321.
让我们看一下你的三张牌组。使用3张牌组,洗牌后甲板上只有6种可能的订单:123,132,213,231,312,321。
With your 1st algorithm there are 27 possible paths (outcomes) for the code, depending on the results of the rand()
function at different points. Each of these outcomes are equally likely (unbiased). Each of these outcomes will map to the same single result from the list of 6 possible "real" shuffle results above. We now have 27 items and 6 buckets to put them in. Since 27 is not evenly divisible by 6, some of those 6 combinations must be over-represented.
使用第一个算法,代码有27种可能的路径(结果),具体取决于不同点的rand()函数的结果。这些结果中的每一个都是同等可能的(无偏见的)。这些结果中的每一个都将映射到上面6个可能的“真实”混洗结果列表中的相同单个结果。我们现在有27个项目和6个桶用于放入它们。由于27个不能被6整除,因此这6个组合中的一些必须过度表示。
With the 2nd algorithm there are 6 possible outcomes that map exactly to the 6 possible "real" shuffle results, and they should all be represented equally over time.
使用第二种算法,有6种可能的结果可以准确地映射到6种可能的“真实”混洗结果,并且它们应该随时间平均表示。
This is important because the buckets that are over-represented in the first algorithm are not random. The buckets selected for the bias are repeatable and predictable. So if you're building an online poker game and use the 1st algorithm a hacker could figure out you used the naive sort and from that work out that certain deck arrangements are much more likely to occur than others. Then they can place bets accordingly. They'll lose some, but they'll win much more than they lose and quickly put you out of business.
这很重要,因为在第一个算法中过度表示的桶不是随机的。为偏差选择的桶是可重复且可预测的。因此,如果你正在建立一个在线扑克游戏并使用第一种算法,那么黑客可能会发现你使用了天真的排序,并且从那项工作中可以看出某些甲板安排比其他人更容易发生。然后他们可以相应地下注。他们会失去一些,但他们会赢得比失败更多的东西,并迅速让你破产。
#3
From your comments on the other answers, it seems that you are looking not just for an explanation of why the distribution is not the uniform distribution (for which the divisibility answer is a simple one) but also an "intuitive" explanation of why it is actually far from uniform.
根据您对其他答案的评论,您似乎不仅仅想要解释为什么分布不是均匀分布(对于哪个分布是简单的分布),而是对其原因的“直观”解释。实际上远非均匀。
Here's one way of looking at it. Suppose you start with the initial array [1, 2, ..., n]
(where n might be 3, or 52, or whatever) and apply one of the two algorithms. If all permutations are uniformly likely, then the probability that 1 remains in the first position should be 1/n
. And indeed, in the second (correct) algorithm, it is 1/n
, as 1 stays in its place if and only if it is not swapped the first time, i.e. iff the initial call to rand(0,n-1)
returns 0.
However, in the first (wrong) algorithm, 1 remains untouched only if it is neither swapped the first time nor any other time — i.e., only if the first rand
returns 0 and none of the other rand
s returns 0, the probability of which is (1/n) * (1-1/n)^(n-1) ≈ 1/(ne) ≈ 0.37/n, not 1/n.
这是一种看待它的方式。假设您从初始数组[1,2,...,n](其中n可能是3或52或其他)开始,并应用这两种算法中的一种。如果所有排列均匀可能,则1保持在第一位置的概率应为1 / n。事实上,在第二个(正确的)算法中,它是1 / n,当且仅当它第一次没有交换时,1保持在其位置,即iff对rand(0,n-1)的初始调用返回但是,在第一个(错误的)算法中,1只有在第一次或任何其他时间都没有交换时仍然保持不变 - 即,只有当第一个兰特返回0并且其他任何一个都没有返回0时,概率为0这是(1 / n)*(1-1 / n)^(n-1)≈1/(ne)≈0.37/ n,而不是1 / n。
And that's the "intuitive" explanation: in your first algorithm, earlier items are much more likely to be swapped out of place than later items, so the permutations you get are skewed towards patterns in which the early items are not in their original places.
这就是“直观”的解释:在你的第一个算法中,早期的项目比后面的项目更有可能被替换掉,所以你得到的排列倾向于早期项目不在原始位置的模式。
(It's a bit more subtle than that, e.g. 1 can get swapped into a later position and still end up getting swapped back into place through a complicated series of swaps, but those probabilities are relatively less significant.)
(它比这更微妙,例如1可以换成后来的位置,并且最终通过一系列复杂的掉期交换回来,但这些概率相对不太重要。)
#4
The best explanation I've seen for this effect was from Jeff Atwood on his CodingHorror blog (The Danger of Naïveté).
我见过这个效果的最佳解释来自Jeff Atwood的CodingHorror博客(Naïveté的危险)。
Using this code to simulate a 3-card random shuffle...
使用此代码模拟3张牌随机随机播放......
for (int i = 0; i < cards.Length; i++)
{
int n = rand.Next(cards.Length);
Swap(ref cards[i], ref cards[n]);
}
...you get this distribution.
...你得到这个发行版。
The shuffle code (above) results in 3^3 (27) possible deck combinations. But the mathematics tell us that there are really only 3! or 6 possible combinations of a 3 card deck. So some of the combinations are over-represented.
随机码(上图)导致3 ^ 3(27)个可能的卡组合。但是数学告诉我们真的只有3个!或3张牌组的6种可能组合。所以有些组合过度代表了。
You would need to use a Fisher-Yates shuffle to properly (randomly) shuffle a deck of cards.
你需要使用Fisher-Yates shuffle来正确地(随机地)洗牌一副纸牌。
#5
Here's another intuition: the single shuffle swap can't create symmetry in the probability of occupying a position unless at least 2-way symmetry already exists. Call the three positions A, B, and C. Now let a be the probability of card 2 being in position A, b be the probability of card 2 being in position B, and c be the probability of it being in position C, prior to a swap move. Assume that no two probabilities are the same: a!=b, b!=c, c!=a. Now compute the probabilities a', b', and c' of the card being in these three positions following a swap. Let's say that this swap move consists of position C being swapped with one of the three positions at random. Then:
这是另一种直觉:单一的随机交换不能在占据位置的概率中产生对称性,除非至少已经存在双向对称。调用三个位置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.
That is, the probability that the card winds up in position A is the probability it was already there times the 2/3 of the time position A isn't involved in the swap, plus the probability that it was in position C times the 1/3 probability that C swapped with A, etc. Now subtracting the first two equations, we get:
也就是说,卡在位置A结束的概率是它已经存在的概率,即时间位置A的2/3没有参与交换,加上它在位置C乘以1的概率。 / 3与A交换的概率等等。现在减去前两个方程,我们得到:
a' - b' = (a - b)*2/3
which means that because we assumed a!=b, then a'!=b' (though the difference will approach 0 over time, given enough swaps). But since a'+b'+c'=1, if a'!=b', then neither can be equal to c' either, which is 1/3. So if the three probabilities start off all different before a swap, they will also all be different after a swap. And this would hold no matter which position was swapped - we just interchange the roles of the variables in the above.
这意味着因为我们假设了一个!= b,然后是'!= b'(尽管差异将随时间推移接近0,给定足够的交换)。但由于'+ b'+ c'= 1,如果是'!= b',那么两者都不能等于c',即1/3。因此,如果三个概率在交换之前开始全部不同,那么在交换之后它们也将是不同的。无论交换哪个位置,这都会成立 - 我们只是在上面交换变量的作用。
Now the very first swap started by swapping card 1 in position A with one of the others. In this case, there was two way symmetry before the swap, because the probability of card 1 in position B = probability of card 1 in position C = 0. So in fact, card 1 can wind up with symmetric probabilities and it does end up in each of the three positions with equal probability. This remains true for all subsequent swaps. But card 2 winds up in the three positions after the first swap with probability (1/3, 2/3, 0), and likewise card 3 winds up in the three positions with probability (1/3, 0, 2/3). So no matter how many subsequent swaps we do, we will never wind up with card 2 or 3 having exactly the same probability of occupying all three positions.
现在,第一次交换开始于将卡1换成位置A与其他一个。在这种情况下,在交换之前存在双向对称,因为位置B中的卡1的概率=卡1在位置C = 0的概率。因此实际上,卡1可以结束对称概率并且它最终结束在三个位置中的每个位置具有相同的概率。所有后续掉期都是如此。但是卡片2在第一次交换之后在三个位置卷起概率(1 / 3,2 / 3,0),同样卡3在三个位置卷起概率(1 / 3,0,2 / 3) 。因此,无论我们进行多少次后续交换,我们都不会因为卡2或3具有完全相同的占据所有三个位置的概率而结束。
#6
See the Coding Horror post The Danger of Naïveté.
参见Naïveté的危险编码恐怖片。
Basically (suposing 3 cards):
基本上(附3张卡):
The naive shuffle results in 33 (27) possible deck combinations. That's odd, because the mathematics tell us that there are really only 3! or 6 possible combinations of a 3 card deck. In the KFY shuffle, we start with an initial order, swap from the third position with any of the three cards, then swap again from the second position with the remaining two cards.
天真的洗牌导致33(27)种可能的套牌组合。这很奇怪,因为数学告诉我们真的只有3个!或3张牌组的6种可能组合。在KFY shuffle中,我们从初始订单开始,从第三个位置与三个卡中的任何一个交换,然后从第二个位置再次与剩余的两个卡交换。
#7
The simple answer is that there are 52^52 possible ways for this algorithm to run, but there are only 52! possible arrangements of 52 cards. For the algorithm to be fair, it needs to produce each of these arrangements equally likely. 52^52 is not an integer multiple of 52!. Therefore, some arrangements must be more likely than others.
简单的答案是这种算法有52 ^ 52种可能的运行方式,但只有52种!可能安排52张卡。为了使算法公平,它需要同样可能产生这些安排中的每一个。 52 ^ 52不是52的整数倍!因此,某些安排必须比其他安排更可能。
#8
an illustrative approach might be this:
一个说明性的方法可能是:
1) consider only 3 cards.
1)只考虑3张牌。
2) for the algorithm to give evenly distributed results, the chance of "1" ending up as a[0] must be 1/3, and the chance of "2" ending up in a[1] must be 1/3 too, and so forth.
2)对于算法给出均匀分布的结果,“1”结束为[0]的几率必须为1/3,并且在[1]中结束的“2”的概率必须为1/3等等。
3) so if we look at the second algorithm:
3)所以如果我们看第二个算法:
probability that "1" ends up at a[0]: when 0 is the random number generated, so 1 case out of (0,1,2), therefore, is 1 out of 3 = 1/3
“1”在[0]处结束的概率:当0是生成的随机数时,因此,(0,1,2)中的1例是1 = 3 = 1/3
probability that "2" ends up at a[1]: when it didn't get swapped to a[0] the first time, and it didn't get swapped to a[2] the second time: 2/3 * 1/2 = 1/3
“2”在[1]处结束的概率:第一次没有交换到[0]时,第二次没有交换到[2]:2/3 * 1 / 2 = 1/3
probability that "3" ends up at a[2]: when it didn't get swapped to a[0] the first time, and it didn't get swapped to a[1] the second time: 2/3 * 1/2 = 1/3
“3”在[2]处结束的概率:第一次没有交换到[0]时,第二次没有交换到[1]:2/3 * 1 / 2 = 1/3
they are all perfectly 1/3, and we don't see any error here.
它们都是完美的1/3,我们在这里看不到任何错误。
4) if we try to calculate the probability of of "1" ending up as a[0] in the first algorithm, the calculation will be a bit long, but as the illustration in lassevk's answer shows, it is 9/27 = 1/3, but "2" ending up as a[1] has a chance of 8/27, and "3" ending up as a[2] has a chance of 9/27 = 1/3.
4)如果我们试图计算第一个算法中“1”结束为[0]的概率,计算会有点长,但正如lassevk的答案所示,它是9/27 = 1 / 3,但是作为[1]结束的“2”有8/27的机会,而结束为[2]的“3”有可能是9/27 = 1/3。
as a result, "2" ending up as a[1] is not 1/3 and therefore the algorithm will produce pretty skewed result (about 3.7% error, as opposed to any negligible case such as 3/10000000000000 = 0.00000000003%)
结果,结果为[1]的“2”不是1/3,因此算法会产生相当偏差的结果(大约3.7%的误差,而不是任何可忽略不计的情况,如3/10000000000000 = 0.00000000003%)
5) the proof that Joel Coehoorn has, actually can prove that some cases will be over-represented. I think the explanation that why it is n^n is this: at each iteration, there are n possibility that the random number can be, so after n iterations, there can be n^n cases = 27. This number doesn't divid the number of permuations (n! = 3! = 6) evenly in the case of n = 3, so some results are over-represented. they are over-represented in a way that instead of showing up 4 times, it shows up 5 times, so if you shuffle the cards millions of times from the initial order of 1 to 52, the over-represented case will show up 5 million times as opposed to 4 million times, which is quite big a difference.
5)Joel Coehoorn的证据,实际上可以证明某些案件的代表性过高。我认为为什么它是n ^ n的解释是这样的:在每次迭代时,随机数都有可能是,所以在n次迭代之后,可能有n ^ n个情况= 27.这个数字不是divid在n = 3的情况下,均匀的数量(n!= 3!= 6),因此一些结果被过度表示。它们的代表性过高,而不是出现4次,它会出现5次,所以如果你从最初的1到52的顺序洗牌数百万次,过度代表的案例将显示500万时间而不是400万次,这是相当大的差异。
6) i think the over-representation is shown, but "why" will the over-representation happen?
6)我认为过度表现会被显示出来,但过度表现的“为什么”会发生?
7) an ultimate test for the algorithm to be correct is that any number has a 1/n probability to end up at any slot.
7)算法正确的最终测试是任何数字在任何时隙都有1 / n概率结束。
#9
Here's a great analysis of a card shuffling Markov chains. Oh wait, that's all math. Sorry. :)
这是一张关于洗牌马尔可夫链的卡片的精彩分析。哦等等,这都是数学。抱歉。 :)
#10
The Naive algorithm picks the values of n like so:
朴素算法选择n的值,如下所示:
n = rand(3)
n =兰特(3)
n = rand(3)
n =兰特(3)
n = rand(3)
n =兰特(3)
3^3 possible combinations of n
n ^的3 ^ 3种可能的组合
1,1,1, 1,1,2....3,3,2 3,3,3 (27 combinations) lassevk's answer shows the distribution among the cards of these combinations.
1,1,1,1,1,2 ...... 3,3,2 3,3,3(27种组合)lassevk的答案显示了这些组合的卡片之间的分布。
the better algorithm does:
更好的算法:
n = rand(3)
n =兰特(3)
n = rand(2)
n =兰特(2)
n! possible combinations of n
N! n的可能组合
1,1, 1,2, 2,1 2,2 3,1 3,2 (6 combinations, all of them giving a different result)
1,1,1,2,2,1,2,2,3,3,2(6种组合,所有这些都给出了不同的结果)
As mentioned in the other answers, if you take 27 attempts to get 6 results, you cannot possibly attain the 6 results with even distribution, since 27 is not divisible by 6. Put 27 marbles into 6 buckets and no matter what you do, some buckets will have more marbles than others, the best you can do is 4,4,4,5,5,5 marbles for buckets 1 through 6.
正如其他答案中所提到的,如果你试图获得6次结果,你就不可能达到均匀分布的6个结果,因为27不能被6整除。将27个弹珠放入6个桶中,无论你做什么,一些水桶比其他水桶有更多的弹珠,你能做的最好的是水桶1到6的4,4,4,5,5,5弹珠。
the fundamental problem with the naive shuffle is that swaps too many times, to shuffle 3 cards completely, you need only do 2 swaps, and the second swap need only be among the first two cards, since the 3rd card already had a 1/3 chance of being swapped. to continue to swap cards will impart more chances that a given card will be swapped, and these chances will only even out to 1/3, 1/3, 1/3 if your total swap combinations is divisible by 6.
天真洗牌的根本问题在于交换太多次,完全洗牌3张牌,你只需要进行2次掉期,而第二次掉牌只需要在前两张牌中,因为第3张牌已经有1/3被交换的机会。继续交换卡片会给予更换一张特定卡片的机会,如果你的总交换组合可以被6整除,这些机会只会达到1 / 3,1 / 3,1 / 3。
#11
Not that another answer is needed, but I found it worthwhile to try to work out exactly why Fisher-Yates is uniform.
不是说需要另一个答案,但我发现值得尝试找出Fisher-Yates为什么是统一的。
If we are talking about a deck with N items, then this question is: how can we show that
如果我们谈论的是一个有N个项目的牌组,那么这个问题就是:我们怎么能表明这一点
Pr(Item i ends up in slot j) = 1/N?
Breaking it down with conditional probabilities, Pr(item i ends up at slot j)
is equal to
用条件概率将其分解,Pr(项目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).
and from there it expands recursively back to the first draw.
从那里它递归地扩展回第一次抽奖。
Now, the probability that element i
was not drawn on the first draw is N-1 / N
. And the probability that it was not drawn on the second draw conditional on the fact that it was not drawn on the first draw is N-2 / N-1
and so on.
现在,在第一次抽签中没有绘制元素i的概率是N-1 / N.并且在第二次抽签中没有绘制的概率条件是它没有在第一次抽签中绘制的概率是N-2 / N-1等。
So, we get for the probability that element i
was not drawn in the first j-1
draws:
所以,我们得到的元素i没有在第一个j-1绘制中绘制的概率:
(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)
and of course we know that the probability that it is drawn at round j
conditional on not having been drawn earlier is just 1 / N-j
.
当然,我们知道在没有先前绘制的条件下在第j轮绘制的概率仅为1 / N-j。
Notice that in the first term, the numerators all cancel the subsequent denominators (i.e. N-1
cancels, N-2
cancels, all the way to N-j+1
cancels, leaving just N-j / N
).
请注意,在第一项中,分子全部取消后续分母(即N-1取消,N-2取消,一直到N-j + 1取消,只留下N-j / N)。
So the overall probability of element i
appearing in slot j
is:
因此,元素i出现在插槽j中的总体概率为:
[(N-1 / N) * (N-2 / N-1) * ... * (N-j / N-j+1)] * (1 / N-j)
= 1/N
as expected.
To get more general about the "simple shuffle", the particular property that it is lacking is called exchangeability. Because of the "path dependence" of the way the shuffle is created (i.e. which of the 27 paths is followed to create the output), you are not able to treat the different component-wise random variables as though they can appear in any order. In fact, this is perhaps the motivating example for why exchangeability matters in random sampling.
为了更加全面地了解“简单洗牌”,它缺乏的特殊属性称为可交换性。由于shuffle创建方式的“路径依赖性”(即,遵循27条路径中的哪条路径来创建输出),您无法将不同的分量随机变量视为可以按任何顺序出现。事实上,这可能是为什么可交换性在随机抽样中起作用的动机实例。
#12
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.
显示第一个算法失败的最明确答案是将所讨论的算法视为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时才可能。我们有矛盾。