n 個の要素、m=2n、および k があります。ここで、K はハッシュ関数の数、m はビット配列のサイズ、n は要素の数です。偽陽性を得る確率が最大で 1/n になるような k の値は?
私は、偽陽性確率がせいぜい1/nになるようなkの値を見つける確率を見つけることに取り組んでいます。これまでに行ったことは次のとおりです。
Pr(ビット = 0) = 1-1/m == e^(-kn/m)
それから：
Pr(ビット = 1) = (1-e^(-kn/m))^k
今、私はこの時点で立ち往生しており、最大でも偽陽性確率が 1/n になる k の値を取得できません。
また、誰かが私がこれまでに行ったことを誤りだと考えている場合はお知らせください。