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]巻き込まれる確率を見つけようとしていますか？私はそれだと思います。しかし、私がこれを証明するのを手伝ってもらえますか？n1/n(n-1)/n * 1/(n-1)=1/n

score 3 · Accepted Answer

^k番目のカードがスロット n に配置される確率が 1/n である理由は、n^番目の反復によってスロット n に配置されるカードが完全に決定されるためです。(<--- これは階乗ではなく感嘆符です :-)。

考えてみてください。ループの最後の繰り返しでは、いくつかのランダムな順列があります...そして k^番目のカードがいくつかのスロットに座っています。^{それがスロット n に移動する確率は、その k番目}のカードを無作為に選ぶ確率です。同じ確率でカードを選ぶと仮定すると、その確率は 1/n です。

お役に立てれば。

-トム

アップデート

あなたは、私が間違った仮定をしたと思っているかもしれません。つまり、疑問に思うかもしれません... k^番目のカードが異なる確率で異なるスロットに配置されるとしたらどうでしょうか? 「ランダムシャッフル」が本当にランダムでない場合はどうなりますか? これが、最後の反復のみが重要な理由です。

p _{iは、n-1 回の繰り返しで k}^番目のカードがスロット 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番目}の反復の前の状態のランダム性が実際には問題にならないことを示すために、もう少し形式的なものです。

1 に答える 1