4
$\begingroup$

The following problem arises in the analysis of Bloom filters.

Consider $m$ bins and $N=nk$ balls placed uniformly at random into the bins. A query chooses $k$ bins uniformly at random and asks if they are all non-empty.

The main questions asked are "What is the probability that all $k$ bins in the query are non-empty?" and from there "For what $k$ is this probability minimized?". It is assumed that $k$ should be a function of $m$ and $n$.

The standard version of the analysis taught the world over and reproduced in the wikipedia page linked above contains a "now the magic occurs" step which ignores the non-independence of the bins.

Is there a clean and rigorous way of doing this analysis correctly?

Improve this question
$\endgroup$
5
  • $\begingroup$ Just to confirm, the $k$ query bins are not uniformly chosen from the $m \choose k$ subsets, they don't have to be distinct, correct? $\endgroup$ – Douglas Zare May 21 '13 at 9:18
  • $\begingroup$ That is correct. $\endgroup$ – navid May 21 '13 at 9:30
  • $\begingroup$ Just a comment to say the current non-proven answer to the second question is $k \approx \frac{m}{n} \ln{2}$ (from the wiki link). Given how well used and known Bloom filters are I would guess this is in fact approximately correct. $\endgroup$ – user32786 May 22 '13 at 15:13
  • $\begingroup$ It looks like pages 110-111 of books.google.co.uk/… has an answer. Unfortunately the relevant results it relies on aren't provided by Google as far as I can see. $\endgroup$ – user32786 May 28 '13 at 17:38
  • $\begingroup$ The question was cross-posted to math.stackexchange.com/questions/402210/… . $\endgroup$ – user32786 May 28 '13 at 18:08
2
$\begingroup$

UPDATE: As Algernon points out, the following analysis is actually wrong, but it's worth trying to spot the error on your own before reading his comment. :)

Let $B_i$ denote whether the $i$th randomly selected bin is nonempty. Then the probabilty we seek is $$ \mathrm{Pr}(B_i=1, \forall i) =\mathrm{Pr}(B_i=1)^k. $$ To determine $\mathrm{Pr}(B_i=1)$, it is natural to condition on the random number $X$ of nonempty bins: $$ \mathrm{Pr}(B_i=1) =\sum_{x=1}^m\mathrm{Pr}(B_i=1|X=x)\mathrm{Pr}(X=x) =\sum_{x=1}^m\frac{x}{m}\mathrm{Pr}(X=x) =\frac{1}{m}\mathbb{E}[X]. $$ Let $X_p$ denote the random number of nonempty bins after $p$ balls. Then $$ \mathbb{E}[X_{p+1}|X_p] =X_p\frac{X_p}{m}+(X_p+1)\frac{m-X_p}{m} =\Big(1-\frac{1}{m}\Big)X_p+1. $$ From this, the law of total expectation gives a recursion: $$ \mathbb{E}[X_{p+1}] =\mathbb{E}[\mathbb{E}[X_{p+1}|X_p]] =\Big(1-\frac{1}{m}\Big)\mathbb{E}[X_p]+1. $$ The following formula solves this recursion (you can verify it by induction): $$ \mathbb{E}[X_p]=m\bigg(1-\Big(1-\frac{1}{m}\Big)^p\bigg). $$ Considering $X=X_{kn}$, we can put everything together: $$ \mathrm{Pr}(B_i=1, \forall i) =\mathrm{Pr}(B_i=1)^k =\Big(\frac{1}{m}\mathbb{E}[X_{kn}]\Big)^k =\bigg(1-\Big(1-\frac{1}{m}\Big)^{kn}\bigg)^k. $$ Surprisingly, this is identical to the answer you get assuming independence. (!)

Improve this answer
$\endgroup$
10
  • $\begingroup$ However, the k bins are not distinct, so I think your first inequality does not take that into account. Gerhard "Ask Me About System Design" Paseman, 2013.05.21 $\endgroup$ – Gerhard Paseman May 21 '13 at 23:05
  • $\begingroup$ Excuse, I mean the first equality between probabilities. Gerhard "Ask Me About System Design" Paseman, 2013.05.21 $\endgroup$ – Gerhard Paseman May 21 '13 at 23:06
  • $\begingroup$ @Gerhard: Based on Douglas Zare's clarification, the bins are not selected uniformly from the $\binom{m}{k}$ subsets, so I'm assuming that the bins are drawn independently. How are you interpreting the problem? $\endgroup$ – Dustin G. Mixon May 21 '13 at 23:09
  • $\begingroup$ I think I am interpreting it the same way, but drawing a different (and possibly incorrect) conclusion. To clarify, one of the possibilities is that bin 1 is chosen 3 times, and bin 2 is chosen (k-3) times. My (possibly incorrect) conclusion is that the probability for k bins is not the kth power of the probability for 1 bin. When I have something more substantial I will post it here. Gerhard "Will Look At It More" Paseman, 2013.05.21 $\endgroup$ – Gerhard Paseman May 22 '13 at 0:06
  • 3
    $\begingroup$ @Dustin: The variables $B_i$ are not independent: $B_1,B_2,\ldots,B_{i-1}$ contain information about the distribution of the balls, which can be used to predict $B_i$. Consider, for example, the case $m=2$ and $N$ large. If we know that $B_1=0$, it means that the balls are all in one bin, increasing the chance of $B_2=0$ from $\sim 0$ to $1/2$. $\endgroup$ – Algernon May 22 '13 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.