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