Suppose that balls, where is a constant, are thrown sequentially to bins, all of which are initially empty. Let be the number of empty bins after we have thrown balls. Clearly, . Let’s see how we can understand this sequence of random variables. When we move from step to we throw a ball. It either falls in an empty bin or not. We quantify this by an indicator random variable which takes the value 1 if the ball falls in an empty bin, 0 otherwise. Notice that . We obtain:

and by taking expectations, .

We now introduce a linear time scaling for this process. In particular, we define . In particular we map the -th step of the process to time . Our difference equation becomes . By taking the limit we obtain the differential equation . This implies and since we get .

This implies that after throwing balls, the expected fraction of empty bins is . In particular after throwing balls, we expect the number of empty bins to be really close to . 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“.

# Empty bins

Advertisements