probability - 一副纸牌的概率

Question

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。但是你能帮我证明这一点吗？

Answer 1

第 k张卡最终在插槽 n 中的概率是 1/n 的原因是因为第 n^次迭代^完全确定了哪张卡最终在插槽 n 中！（<---这是一个感叹号，而不是阶乘:-)。

想想看。在循环的最后一次迭代中，您有一些随机排列......并且第 k^张卡位于某个插槽中。^{它进入插槽n}的概率就是你随机选择第 k张牌的概率。假设您选择概率相同的牌，则该概率为 1/n。

希望这可以帮助。

-汤姆

更新

你可能会认为我做了一个错误的假设。也就是说，您可能想知道……如果第 k^张卡最终以不同的概率出现在不同的插槽中怎么办？如果“随机洗牌”不是真的随机怎么办？这就是为什么只有最后一次迭代很重要：

令 p _i表示第 k 张卡在 n-1 次迭代中位于插槽 i 中的概率^（即 - 它在结束前位于插槽 i 中）。

那么卡片 k 出现在插槽 n 中（在第 n^次迭代中）的概率为：

(1/n)p ₁ + (1/n)p ₂ + ... + (1/n)p _n

但请注意，我们可以分解 (1/n)，所以我们有：

(1/n)(p ₁ + p ₂ + ... + p _n )

因为这些是概率，很明显 p _i的总和（i = 1 到 n）必须等于 1。所以我们只剩下 (1/n)。

这只是更正式地表明在第 n^次迭代之前事态的随机性确实无关紧要。