# Minimising a function related to a Bloom Filter

1. Apr 9, 2012

### delcypher

Minimising a function related to a "Bloom Filter"

1. The problem statement, all variables and given/known data
I'm looking at a problem that requires me to find $k$ that minimises the function $f$. Where $n,m$ are to be treated as constants.

Although not needed for this problem the context is that the function $f$ approximately describes the probability of "finding a false positive" when using the bloom filter data structure (computer science). See http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives

2. Relevant equations

$f(k) = (1 - e^{\frac{-kn}{m}})^k$

I already know what the answer should be. Which is the $k$ that minimises $f$ is given by
$k_{\text{min}} = \frac{m}{n} \ln(2)$

What I want to find out is a good way of getting there. I found a way but it is incomplete because it requires me to know the form of the answer and to use observation to solve for a particular value. So what I'd like to know is

• Is there a way of completing my proof given later that doesn't require me to use observation (to find $j$)?
• Is there a better way of approaching the problem? I may of gone the long way round proving this.

3. The attempt at a solution
My plan is to differentiate $f$ with respect to $k$ and set to 0 and then solve for $k$.

Firstly I rewrite $f$.
$f = e^{k \ln{\left(1 - e^{\frac{-kn}{m}}\right) }}$

$\ln{f} = k \ln{ ( 1 - e^{\frac{-kn}{m}}) }$

and observe that minimising $f$ is equivalent to minimising $\ln{f}$

Now via the product rules and chain rule...
$\frac{d \ln{f}}{dk} = \ln{(1 - e^{\frac{-kn}{m}} )} + \frac{kn e^{ \frac{-kn}{m} } }{m (1 - e^{\frac{-kn}{m}}) } =0$

I now make the following substitution to make the equations easier to write
$a = \frac{kn}{m}$

so...

$\frac{d \ln{f}}{dk} = \ln{(1 - e^{-a} )} + \frac{a e^{-a} }{(1 - e^{-a}) } =0$

So now I'm solving for a. I now rewrite the second term using the following...
$\frac{a e^{-a} }{(1 - e^{-a}) } = \ln{(e^{ \frac{a e^{-a} }{(1 - e^{-a}) } } )}$

To give...
$\ln{ \left( (1 - e^{-a} ) e^{ \frac{a e^{-a} }{(1 - e^{-a}) } } \right) } = 0$

Now re-arranging...
$(1 - e^{-a} ) e^{ \frac{a e^{-a} }{(1 - e^{-a}) } } = 1$

Now because I know what the answer is supposed to be it hints to me that I should try a form of $a$ such that $a = \ln{j}$ where $j$ is to be found which would give a solution of
$k_{\text{min}} = \frac{m}{n} \ln{j}$

Substituting that in and rearranging gives
$( 1 - \frac{1}{j}) j^{\frac{1}{j-1}} = 1$

This is where I get stuck. I can't think of a way to solve the above equation for $j$. By observation I can see that $j = 2$ solves it as expected but I don't know how to show that. I can see by plotting it (via GnuPlot) that $j=2$ is the only solution. I also found that "Wolfram Alpha" was able to solve the equation although it wouldn't explain to me how it did so.

Any ideas?

2. Apr 10, 2012

### delcypher

Re: Minimising a function related to a "Bloom Filter"

I received a reply from QuarkCharmer. For some reason it isn't shown here. It was
I appreciate the reply but the suggestion does not work. If I take logarithms of both sides I get
$\ln{ \left( ( 1 - \frac{1}{j}) j^{\frac{1}{j-1}} \right)} = 0$

From this it is not possible to get to
$\frac{1}{j-1} \ln{ \left( ( 1 - \frac{1}{j}) j\right)} = 0$
(which would lead to your suggestion) because only $j$ is to the power of $\frac{1}{j-1}$ and not $( 1 - \frac{1}{j}) j$

If I take the logarithm of both sides what I actually end up with is
$\ln{(1 - \frac{1}{j})} - \frac{1}{j-1} \ln{(j)} = 0$
which is no easier to solve in my opinion.

3. Apr 10, 2012

### chiro

Re: Minimising a function related to a "Bloom Filter"

Hey delcypher.