1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Minimising a function related to a Bloom Filter

  1. Apr 9, 2012 #1
    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 [itex]k[/itex] that minimises the function [itex]f[/itex]. Where [itex]n,m[/itex] are to be treated as constants.

    Although not needed for this problem the context is that the function [itex]f[/itex] 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

    [itex]f(k) = (1 - e^{\frac{-kn}{m}})^k[/itex]

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

    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 [itex]j[/itex])?
    • 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 [itex]f[/itex] with respect to [itex]k[/itex] and set to 0 and then solve for [itex]k[/itex].

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

    [itex] \ln{f} = k \ln{ ( 1 - e^{\frac{-kn}{m}}) }[/itex]

    and observe that minimising [itex]f[/itex] is equivalent to minimising [itex]\ln{f}[/itex]

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

    I now make the following substitution to make the equations easier to write
    [itex] a = \frac{kn}{m} [/itex]


    [itex] \frac{d \ln{f}}{dk} =
    \ln{(1 - e^{-a} )} +
    \frac{a e^{-a} }{(1 - e^{-a}) }

    So now I'm solving for a. I now rewrite the second term using the following...
    [itex] \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...
    [itex] (1 - e^{-a} ) e^{ \frac{a e^{-a} }{(1 - e^{-a}) } } = 1 [/itex]

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

    Substituting that in and rearranging gives
    [itex] ( 1 - \frac{1}{j}) j^{\frac{1}{j-1}} = 1 [/itex]

    This is where I get stuck. I can't think of a way to solve the above equation for [itex]j[/itex]. By observation I can see that [itex]j = 2[/itex] solves it as expected but I don't know how to show that. I can see by plotting it (via GnuPlot) that [itex]j=2[/itex] 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. jcsd
  3. Apr 10, 2012 #2
    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 [itex]j[/itex] is to the power of [itex]\frac{1}{j-1}[/itex] and not [itex]( 1 - \frac{1}{j}) j[/itex]

    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.
  4. Apr 10, 2012 #3


    User Avatar
    Science Advisor

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

    Hey delcypher.

    I would take QuarkCharmers advice.

    The logarithm function is unique for all valid values.

    Basically what happens is that (1 - 1/j)j^(1/(j-1)) = 1. Now lets get it in terms of one log term which gives us:

    (2-j)/(j-1)ln(j) + ln(j-1) = 0

    Now j > 1 since ln(j-1) is only defined when this is the case. Now (2-j)/(j-1) is monotonic increasing for j <= 2. Now RHS is also monotonically increasing as well for j > 1.

    From the equation you can see that j = 2 is one solution, but to show it's the only solution you should show what the turning points of this function are and that using various theorems like say the mean-value theorem you can show that it is the only root if this is the case (I haven't checked, but I would basically do what I said above).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook