# 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

## 1 Answer

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. (!)

-
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 – Gerhard Paseman May 21 '13 at 23:05
Excuse, I mean the first equality between probabilities. Gerhard "Ask Me About System Design" Paseman, 2013.05.21 – Gerhard Paseman May 21 '13 at 23:06
@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
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 – Gerhard Paseman May 22 '13 at 0:06
@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