問題タブ [reservoir-sampling]

貯水池サンプリングに関連する確率を理解するのに苦労しています。以下は、ほぼすべての場所で使用されているサンプル コードです。

私の理解は正しいですか(?): k=3 と入力 = [100, 200, 300, 400, 500] があり、i が現在 500 インデックスにあるとします。リザーバー内の 300 を 500 で置き換える確率 (サイズは 3) = リザーバー内で 300 が選択される確率 * 500 が選択される確率。 5 つの選択肢 = 1/3 * 3/5 = 1/5

私の質問は、このリンクの「アルゴリズム R」セクションのサンプル コードに関連しています https://en.m.wikipedia.org/wiki/Reservoir_sampling

そのセクションから以下のコード スニペットをコピーしました。このコードが要素を徐々に減少する確率で置き換えているのはなぜですか? 問題によると、入力の各項目は同じ確率になるはずですよね?

たとえば、以下の 3 つの入力に対するランダム関数呼び出しを、リザーバー サイズ 10 と比較します。

• random (1,15) 10 未満の乱数を取得する可能性が高い
• ランダム (1, 100) 10 未満の乱数を取得する可能性は非常に低い
• ランダム (1, 1000) 10 未満の乱数を取得する可能性は非常に低い

したがって、入力が増加するにつれて、アイテムを置き換える可能性は非常に低くなります。では、リザーバー サンプリング アルゴリズムが、各アイテムで等しい確率でランダムなサンプルを選択するためのソリューションであるとどのように言えますか? 説明してください。

https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chaoに示すように、加重貯留層サンプリングの A-Chao バージョンを実装しようとしています。

しかし、特に初期化部分で、wiki に記述されている疑似コードが間違っているように見えることがわかりました。論文を読みましたが、重み付けされたデータポイントを処理する必要があると書かれていますが、正しく初期化する方法がわかりません。

私の理解では、初期化ステップで、選択されたすべての初期データポイントが同じ確率*重みを持つようにしたいと考えています。ただし、加重ポイントがそれとどのように関連しているかはわかりません。

wikiに従って実装したコードですが、結果は正しくないことを示しています。