If m is the number of bits in the array, k is the number of hash functions and we have

rmd1228887e

rmd1228887e

Answered question

2022-07-02

If m is the number of bits in the array, k is the number of hash functions and we have n entries, then the false positive probability upper bound can be approximated as:
( 1 e k n m ) k
It further states in the wiki article that:
"The number of hash functions, k, must be a positive integer. Putting this constraint aside, for a given m and n, the value of k that minimizes the false positive probability is:"
k = m n ln 2
How can I find the k value that minimizes the false positive function ?

Answer & Explanation

treccinair

treccinair

Beginner2022-07-03Added 18 answers

Let f ( k ) = ( 1 e k n m ) k = ( 1 e a k ) k where a = n / m
Then
f ( k ) = ( ( 1 e a k ) k ) = ( e k ln ( 1 e a k ) ) = ( k ln ( 1 e a k ) ) ( e k ln ( 1 e a k ) ) since  ( e g ( k ) ) = g ( k ) e g ( k ) = ( ln ( 1 e a k ) + k ( ln ( 1 e a k ) ) ) ( e k ln ( 1 e a k ) ) = ( ln ( 1 e a k ) + k ( 1 e a k ) 1 e a k ) ( 1 e a k ) k since  ( ln ( g ) ) = g g = ( ln ( 1 e a k ) + k a e a k 1 e a k ) ( 1 e a k ) k = ln ( 1 e a k ) ( 1 e a k ) k a e a k 1 e a k ( 1 e a k ) k = 0 when  ( 1 e a k ) ln ( 1 e a k ) = k a e a k
Let 1 e a k = y, so k = ln ( 1 y ) / a.
Then ( 1 e a k ) ln ( 1 e a k ) = k a e a k becomes y ln ( y ) = ( ln ( 1 y ) / a ) ( 1 y ) or y y = ( 1 y ) ( 1 y ) / a .
Ryan Robertson

Ryan Robertson

Beginner2022-07-04Added 3 answers

You helped me with the same problem, thanks!

Do you have a similar question?

Recalculate according to your conditions!

New Questions in College Statistics

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?