問題タブ [universal-hashing]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
24 問題
0
投票する
0
に答える
48
参照
algorithm - 偽陽性の確率が最大で 1/n になるように K ハッシュ関数の値
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 の値を取得できません。
また、誰かが私がこれまでに行ったことを誤りだと考えている場合はお知らせください。