要素の重みを持つリストから無作為にk個の要素を選択する。

質問

重みのない（確率が等しい）選択は、美しく表現されています。 ここで .

この方法を重み付けに変換する方法はないかと考えていました。

また、他のアプローチにも興味があります。

更新：サンプリング を使わずに 置換

どのように解決するのですか？

これはとても古い質問ですが、ちょっとした計算を適用すれば、O(n)時間でこれを行うための巧妙なトリックがあると思います

は 指数分布 には2つの非常に便利な性質があります。

1. 異なる率パラメータを持つ異なる指数分布から n 個のサンプルが与えられると、与えられたサンプルが最小である確率は、その率パラメータをすべての率パラメータの合計で割ったものに等しくなります。

2. それは "メモリーレス" です。つまり、最小値をすでに知っている場合、残りの要素のどれかが 2 番目から最小値である確率は、真の最小値が削除された場合 (そして生成されなかった場合)、その要素が新しい最小値であった確率と同じになるのです。これは明白なことのように思えますが、いくつかの条件付き確率の問題があるため、他の分布では当てはまらないかもしれないと思います。

事実1を用いると、1つの要素を選ぶには、この指数分布のサンプルを重みと同じ割合のパラメータで生成し、最小値のものを選べばよいことがわかります。

事実2を用いると、指数分布のサンプルを生成し直す必要がないことがわかります。代わりに、各要素について1つずつ生成し、最小のサンプルを持つk個の要素を取るだけです。

最小のkを見つけることは、O(n)で行うことができます。以下のように クイックセレクト アルゴリズムを使用して k 番目の要素を見つけ、次にすべての要素をもう一回通過させて k 番目より小さいものをすべて出力するだけです。

便利なメモ：もし指数分布のサンプルを生成するライブラリにすぐにアクセスできない場合は、以下の方法で簡単に行うことができます。 -ln(rand())/weight