一副牌的概率
for(i=1;i<=n;i++)
{
pick a random index j between 1 and n inclusive;
swap card[i] and card[j];
}
对于上面的代码，我试图找到原始 card[k] 卷入插槽 n 的概率是 1/n？我猜是(n-1)/n * 1/(n-1)=1/n。但你能帮我证明这一点吗？
for(i=1;i<=n;i++)
{
pick a random index j between 1 and n inclusive;
swap card[i] and card[j];
}
for the above code am trying to find the probability of original card[k] winding up in slot n is 1/n? I guess it's (n-1)/n * 1/(n-1)=1/n. But can u help me proving this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
第 k 卡最终出现在插槽 n 中的概率为 1/n 的原因是因为第 n 迭代完全决定了哪张卡最终进入插槽 n！ （<--- 这是一个感叹号，而不是阶乘:-)。
想一想。在循环的最后一次迭代中，您有一些随机排列......并且第 kth 卡位于某个插槽中。它移入插槽 n 的概率就是您随机选择第 kth 卡的概率。假设您以同等概率挑选牌，该概率为 1/n。
希望这有帮助。
-Tom
更新
你可能认为我做了一个错误的假设。也就是说，您可能想知道...如果第 kth 卡最终以不同的概率出现在不同的插槽中怎么办？如果“随机洗牌”不是真正随机的怎么办？这就是为什么只有最后一次迭代很重要：
让 pi 表示第 kth 卡在 n-1 次迭代中位于插槽 i 中的概率（即 - 它位于插槽 i 就在结束之前）。
那么卡 k 最终进入插槽 n 的概率（在第 nth 次迭代中）为：
(1/n)p1 + (1/n)p2 + ... + (1/n)pn
但请注意，我们可以因式分解 (1/n)，因此我们有：
(1/n)(p1 + p2 + ... + pn)
因为这些是概率，所以显然 p 的总和i（i = 1 到 n）必须等于 1。因此我们只剩下 (1/n)。
这只是更正式一点，以表明第 nth 迭代之前事态的随机性实际上并不重要。
The reason the probability that the kth card will end up in slot n is 1/n is because the nth iteration completely determines what card ends up in slot n! (<--- that's an exclamation point, not a factorial :-).
Think about it. On the last iteration of the loop, you have some random permutation... and the kth card is sitting in some slot. The probability it moves into slot n is just the probability that you pick that kth card at random. Assuming you pick cards with equally likely probability, that probability is 1/n.
Hope this helps.
-Tom
UPDATE
You might be thinking I made a faulty assumption. Namely, you might be wondering... what if the kth card can end up in different slots with different probabilities? What if the "random shuffling" isn't really random? This is why only the last iteration matters:
Let pi denote the probability that the kth card is in slot i on the n-1 iteration (ie - it is in slot i right before the end).
Then the probability that card k ends up in slot n (on the nth iteration) is:
(1/n)p1 + (1/n)p2 + ... + (1/n)pn
But notice we can factor the (1/n), so we have:
(1/n)(p1 + p2 + ... + pn)
And because these are probabilities, it should be obvious that the sum of the pi's (i = 1 to n) must equal 1. So we are left with just (1/n).
That is just being a bit more formal to show that the randomness of the state of affairs before the nth iteration really does not matter.