Simplification step by step (exponential and logarithm) - regarding BLOOM FILTER - FALSE POSITIVE probability ( 1 − 1 m ) k n ≈ e − k n / m I don't get how to reach e − k n / m from ( 1 − 1 m ) k n I have reviewed logarithm and exponent rules but I always get stuck, here is what I have tried; Starting from ( 1 − 1 m ) k n , I can write:- e ( l n ( 1 − 1 m ) k n ) - e ( k n × l n ( 1 − 1 m ) ) Or the other way around: l n ( e ( 1 − 1 m ) k n ) l n ( e ( 1 − 1 m ) × k n ) l n ( e ( 1 − 1 m ) ) + l n ( k n ) ( 1 − 1 m ) + l n ( k n )After few steps I fall in an unsolvable loop hole playing with l n and e trying to reach e − k n / m .

Question

Simplification step by step (exponential and logarithm) - regarding BLOOM FILTER - FALSE POSITIVE probability  (  1  −      1    m        )          k      n        ≈      e          −      k      n          /      m      I don&#039;t get how to reach       e          −      k      n          /      m       from   (  1  −      1    m        )          k      n      I have reviewed logarithm and exponent rules but I always get stuck, here is what I have tried; Starting from   (  1  −      1    m        )          k      n      , I can write:-       e          (      l      n      (      1      −              1        m                    )                  k          n                    )      -       e          (      k      n      ×      l      n      (      1      −              1        m            )      )      Or the other way around:  l  n  (      e          (      1      −              1        m                    )                  k          n                      )  l  n  (      e          (      1      −              1        m            )      ×              k        n              )  l  n  (      e          (      1      −              1        m            )        )  +  l  n  (      k    n    )  (  1  −      1    m    )  +  l  n  (  k  n  )After few steps I fall in an unsolvable loop hole playing with   l  n and   e trying to reach       e          −      k      n          /      m      .

Mateo Carson · Accepted Answer

Knowing that                    (1)                                          (            1            −                          1              m                        )                    m                →                  e                      −            1                              it&#039;s as simple as                    (2)                                          (            1            −                          1              m                        )                                k            n                          =                              (                                          (                1                −                                  1                  m                                )                            m                        )                                k            n                      /            m                          ≈                              (                          e                              −                1                                      )                                k            n                      /            m                          =                  e                      −            k            n                      /            m                              The first formula is a simple variation of             (      1      +              1        m            )        m    →  e, which is a well known limit.As pointed out in a comment, this derivation does not specify how the parameters   n,   m,   k, should be related for the asymptotics to hold. A simple requirement would be that   m  →  ∞ and   k  n  /  m tends to some positive constant. But this might be unrealistic. A better derivation would use            (      1      −              1        m            )        m    =      e          −      1            (    1    +    O    (    1      /    m    )    )  hence            (      1      −              1        m            )              k      n        =      e          −      k      n          /      m        (  1  +  O  (  1  /  m  )      )          k      n          /      m      This shows that, for the approximation to hold, it is sufficient that   m  ≫  1 and             k      n              m      2        ≪  1, or, equivalently, that      m    2    ≫  k  n  .

Simplification step by step (exponential and logarithm) - regarding BLOOM FILTER - FALSE POSITIVE pr

Answered question

Answer & Explanation

New Questions in College Statistics