私の質問は、このリンクの「アルゴリズム R」セクションのサンプル コードに関連しています https://en.m.wikipedia.org/wiki/Reservoir_sampling
そのセクションから以下のコード スニペットをコピーしました。このコードが要素を徐々に減少する確率で置き換えているのはなぜですか? 問題によると、入力の各項目は同じ確率になるはずですよね?
for i = k+1 to n
j := random(1, i)
if j <= k
R[j] := S[i]
たとえば、以下の 3 つの入力に対するランダム関数呼び出しを、リザーバー サイズ 10 と比較します。
- random (1,15) 10 未満の乱数を取得する可能性が高い
- ランダム (1, 100) 10 未満の乱数を取得する可能性は非常に低い
- ランダム (1, 1000) 10 未満の乱数を取得する可能性は非常に低い
したがって、入力が増加するにつれて、アイテムを置き換える可能性は非常に低くなります。では、リザーバー サンプリング アルゴリズムが、各アイテムで等しい確率でランダムなサンプルを選択するためのソリューションであるとどのように言えますか? 説明してください。