Question

Use simulations to analyze the behavior of hashing with chaining using the
balls-and-bins simulations. Assume being given n balls and m bins, and you are throwing n balls uniformly randomly
into m bins. You need to answer the following questions for various combinations of values of n and m:

After throwing n balls into m bins:

1) How many (what fraction of m) of bins were empty? (MIN,MAX and AVERAGE --- explanation below)
2) How many bins (what percentage of m) had more than average (n/m) number of balls, how many had more than twice the average (2n/m) number of balls?
3) How full was the fullest bin? (What percentage of n balls did the fullest bin contain).

You need to answer and plot the answers for each one of these questions for the following values of n and m:
n=16, m=16
n=128, m=128
n=1024, m=1024
n=2^14, m=2^14

n=32, m=8
n=1024, m=128
n=2^14, m=2^10

In order to get a fairly reliable statistic, each one of these experiments should be run 50 times. So the answers you are reporting
need to be the average of those 50 runs. For example, say you are running an experiment for n=16,m=16.

To answer Question 1, you will run the experiment 50 times, and for each time, you will record the number of empty bins. The number
you report will be the minimum number of empty bins that occurred, the maximum number of empty bins that occurred, and the average over the 50 values.

To answer Question 2, you will record the average number (of 50 runs) of the bins that had more than average, and also for more than twice the average number of balls.

To answer Question 3, you will record the average number (over 50 times) of how full was the fullest bin.

PLEASE NOTE:
The solution needs to be in plain text (do it in a MS Word or some other editor and paste the answer))You need to submit three things
- submit the code
- submit the data you obtained from the experiments
- submit your report that contains the results (numbers and plots) as well as YOUR ANALYSIS of the results you got.

Answer 1

You want to use what are called indicator variables. To see how this works, let's take your first problem. Let YY be the number of bins that are empty. You want E[Y]E[Y]. Now define the indicator variables XiXi so that XiXi is 11 if bin ii is empty and 00 otherwise. Then we have

Y=X1+X2+⋯+Xn.Y=X1+X2+⋯+Xn.

By linearity of expectation,

E[Y]=E[X1]+E[X2]+⋯+E[Xn].E[Y]=E[X1]+E[X2]+⋯+E[Xn].

So now the problem reduces to calculating the E[Xi]E[Xi] for each ii. But this is fairly easy, as

E[Xi]=1P(Xi=1)+0P(Xi=0)=P(Xi=1)=P(bin i is empty)=(1−1n)m,E[Xi]=1P(Xi=1)+0P(Xi=0)=P(Xi=1)=P(bin i is empty)=(1−1n)m,

where the last equality is because balls 1,2,…,m1,2,…,m must all go in a bin other than ii, each with probability 1−1n1−1n.

Therefore,

E[Y]=n(1−1n)m.E[Y]=n(1−1n)m.

Your second problem can be worked in a similar fashion. Let YY be the number of bins that have exactly 11 ball. Let XiXi be 11 if bin ii has exactly one ball and 00 otherwise. Then all that's left is to figure out E[Xi]E[Xi], which is the probability that a given bin has exactly 11 ball, and go from there. Since this is homework,

• I didn't quite follow how you got the (1-1/n) term and why you raise it to power m? – Hristo Mar 25 '11 at 3:51

• So I explained to myself the (1-1/n) term but I'm still confused on why its raised to power m... – Hristo Mar 25 '11 at 3:58

• 6

  @Hristo: The probability that the first ball goes into bin ii is 1/n1/n, so the probability that the first ball goes into a bin other than ii is 1−1/n1−1/n. The probability that the second ball goes into a bin other than ii is also 1−1/n1−1/n. The same is true for the third, and so forth. In order for bin ii to be empty, ball 11 and ball 22 and ball 33 and so forth must all be in bins other than ii. That means you have to multiply 1−1/n1−1/n by 1−1/n1−1/n by 1−1/n1−1/n, etc., with a factor of 1−1/n1−1/n for each of the mm balls. That's (1−1/n)m(1−1/n)m. – Mike Spivey Mar 25 '11 at 3:59

• Got it. That makes sense. Now why is that whole thing multiplied by n? Is it because this (1-1/n)^m term can happen for each bin? Since there are n bins, then each has (1-1/n)^m probability to be empty, so you get n*(1-1/n)^m? – Hristo Mar 25 '11 at 4:06

• @Hristo: Yes. Go back to the E[Y]=E[X1]+E[X2]+⋯E[Xn]E[Y]=E[X1]+E[X2]+⋯E[Xn] equation. Since, for each ii, E[Xi]=(1−1/n)mE[Xi]=(1−1/n)m, we have E[Y]=(1−1/n)m+(1−1/n)m+⋯+(1−1/n)m=n(1−1/n)mE[Y]=(1−1/n)m+(1−1/n)m+⋯+(1−1/n)m=n(1−1/n)m. – Mike Spivey Mar 25 '11 at 4:22

Let's work out the probability there are kk balls (out of mm) in the first bin (out of nn). This is a simple binomial probability with p=1/np=1/n and 1−p=(n−1)/n1−p=(n−1)/n so the probability is (mk)(n−1)m−knm(mk)(n−1)m−knm.

The expected number of times the first bin has kk balls is the same, so the expected number of bins with kk balls is nn times this, i.e.

(mk)(n−1)m−knm−1