Probstat/birthday practice

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
This is part of probstat.

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 be 1 if ball i and ball j land into the same bin.

2.