# Probability $k$ bins are non-empty.

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?

• 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? – Douglas Zare May 21 '13 at 9:18
• That is correct. – navid May 21 '13 at 9:30
• 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. – user32786 May 22 '13 at 15:13
• 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. – user32786 May 28 '13 at 17:38
• The question was cross-posted to math.stackexchange.com/questions/402210/… . – user32786 May 28 '13 at 18:08

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. (!)
• @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? – Dustin G. Mixon May 21 '13 at 23:09
• @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$. – Algernon May 22 '13 at 7:55