# Empty bins

Suppose that $m=cn$ balls,  where $c>0$ is a constant, are thrown sequentially to $n$ bins, all of which are initially empty. Let $X(i)$ be the number of empty bins after we have thrown $i=0,\ldots,m$ balls. Clearly, $n=X(0)>X(1)\geq X(2) \ldots \geq X(m)$. Let’s see how we can understand this sequence of random variables. When we move from step $i$ to $i+1$ we throw a ball. It either falls in an empty bin or not. We quantify this by an indicator random variable $Y_{i+1}$ which takes the value 1 if the $i+1$ ball falls in an empty bin, 0 otherwise. Notice that $Prob(Y_{i+1}=1) = \frac{X(i)}{n}$. We obtain:
$X(i+1) = X(i) - Y_{i+1}$ and by taking expectations, $E[X(i+1)-X(i)] = -\frac{ X(i)}{n}$.
We now introduce a linear time scaling for this process. In particular, we define $x(t) =\frac{1}{n} X(tn)$. In particular we map the $i$-th step of the process to time $i/n$. Our difference equation becomes $x(t+1/n)-x(t) = - Y_{t+1}$. By taking the limit  we obtain the differential equation $dx/dt=-x$. This implies $x(t)=Ce^{-t}$ and since $x(0)=1$ we get $x(t) = e^{-t}$.
This implies that after throwing $tn$ balls, the expected fraction of empty bins is $e^{-t}$. In particular after throwing $i$ balls, we expect the number of empty bins to be really close to $ne^{-i/n}$. Using Azuma’s  inequality one can further prove a concentration result. This is a simple sketch of how the differential equations method is used to analyze discrete random processes. For those interested in finding out more, please  take a look at Nick Wormald’s expository paper “The differential equation method for random graph processes and greedy algorithms“.