明確にするために、次の質問があります。
不確定な長さの入力ストリームが与えられた場合、一定数以上の入力を格納することは許可されておらず、通過することしかできない場合、そのストリームのランダムなメンバーを (それぞれの確率で) どのように返すのですか?入力を一度
この問題の解決策は Reservoir Sampling であると思われ、以下に記載されています。「最初に、1,000 要素のリザーバー (配列) を作成し、ストリーム内の最初の 1,000 要素で埋めます。そうすれば、正確に 1,000 要素がある場合、アルゴリズムは機能します。これが基本ケースです。
次に、i 番目の要素 (i = 1,001 から開始) を処理して、そのステップの処理の最後に、リザーバー内の 1,000 要素が、これまでに見た i 要素の中からランダムにサンプリングされるようにします。どうすればこれを行うことができますか？i = 1,001 から始めます。1001 番目のステップの後、要素 1,001 (またはその要素) が 1,000 個の要素のセットに含まれる確率はどれくらいですか? 答えは簡単です。1,000/1,001 です。」
最後の文「答えは簡単です: 1,000/1,001」が理解できません。1001 要素の配列で 1 つの要素を見つける確率は、1000/1001 ではなく 1/1001 であってはなりませんか? Sample space は 1001 に等しく、結果の好ましい数は 1 に等しくありませんか?