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 ⁡ 2How can I find the k value that minimizes the false positive function ?

Question

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:&quot;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:&quot;  k  =      m    n    ln  ⁡  2How can I find the   k value that minimizes the false positive function ?

treccinair · Accepted Answer

Let   f  (  k  )  =  (  1  −      e                  −        k        n            m            )    k    =  (  1  −      e          a      k            )    k   where   a  =  −  n  /  mThen                              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 · Accepted Answer

You helped me with the same problem, thanks!

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

Answered question

Answer & Explanation

New Questions in College Statistics