Probstat/birthday practice

This is part of probstat and Probstat/week6 practice 2.

Please watch the clips (part 1, part 2) first, and think about how to use the balls-and-bins experiment to analyze the birthday problem before you continue.

We shall indirectly analyze the birthday problem. Instead of thinking about the event that some pair of balls lands into the same bin, we shall try to count the expected number of pairs of balls that land into the same bin. (Can you imagine why this is our choice? What is hard about thinking the former approach?)

To illustrate what we are trying to count, let's consider the sample outcome of throwing 6 balls into 3 bins:

bin 1: 1, 3
bin 2: 4, 5, 6
bin 3: 2

In this sample, there are 4 pairs of balls that land into the same bin: (1-3), (4-5), (5-6), and (4-6).

Let's define our experiment: We throw k balls into n bins uniformly independently at random.

Let random variable X be the number of pairs of balls that fall into the same bin.

1. Find E[X].

Hint: Maybe this definition is useful: For each pair of different balls i and j, let random variable $X_{ij}$ be 1 if ball i and ball j land into the same bin.

2. Find the minimum value of k as a function of n such that E[X] = 1. (This is the number of balls such that we expect to see one collision.)

3. Let n = 365, use your answer in 2, to find k. Compare this value to 23.

4. If we want no two balls to land in the same bin, can we use this analysis to give you a hint on the upperbound on k?