Simplification step by step (exponential and logarithm) - regarding BLOOM FILTER - FALSE POSITIVE probability
I don't get how to reach from
I have reviewed logarithm and exponent rules but I always get stuck, here is what I have tried; Starting from , I can write:
Or the other way around:
After few steps I fall in an unsolvable loop hole playing with and trying to reach .
Answer & Explanation
it's as simple as
The first formula is a simple variation of , which is a well known limit.
As pointed out in a comment, this derivation does not specify how the parameters , , , should be related for the asymptotics to hold. A simple requirement would be that and tends to some positive constant. But this might be unrealistic. A better derivation would use
This shows that, for the approximation to hold, it is sufficient that and , or, equivalently, that
Most Popular Questions