antennense

antennense

Answered

2022-07-11

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 .

Do you have a similar question?

Recalculate according to your conditions!

Answer & Explanation

Mateo Carson

Mateo Carson

Expert

2022-07-12Added 15 answers

Knowing that
(1) ( 1 1 m ) m e 1
it'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 .

Still Have Questions?

Ask Your Question

Free Math Solver

Help you to address certain mathematical problems

Try Free Math SolverMath Solver Robot

Ask your question.
Get your answer.

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

Didn't find what you were looking for?