無作為抽出のトリック

この記事で、「ある集合の上位 5% を 95% の確率で選択するためには、全体のデータ数によらず 59 件取得すれば十分である」という命題を使用しました。これを証明しましょう。

集合 U の部分集合 Q があり、 Q の要素数は U の要素数に対して割合が p だとします。このとき更に U の部分集合である P を考えます。P に Q の要素が全く含まれない確率は  (1- p)^{|P|} ですから、 P のうち少なくとも 1 つの要素が Q に含まれる確率は  {1 - (1 - p)^{|P|} } です。ここで

 {\eta = (1- p)^{|P|}}

とおくと

 {|P| = \log \eta / \log (1 - p) }

が得られます。このとき  {p = 0.05},  {1 - \eta = 0.95} とすると、  { 58 \lt \lceil \log 0.05 / \log 0.95 \rceil \lt 59 } です。つまり、ある集合から無作為に複数の要素を選択する際、ある 5% の要素を 95% の確率で選択するためには、 59 個の要素を選択すれば十分である、ということになります。

なんだか狐につままれたような気分になりますが「95% の確率で選択する」というところがミソですね。シンプルですがなかなか強力な技だと思います。

参考文献: A. J. Smola and B. Schölkopf, “Sparse Greedy Matrix Approximation for Machine Learning", inProceedings of 17th International Conference on Machine Learning, pp. 911-918, 200.