Question

1. Consider an infinite sequence of independent experiments, where in each experiment we take k balls, labeled 1 to k, and randomly place them into k slots, also labeled 1 to k, so that there is exactly one ball in each slot. For the nth experiment, let Xn be the number of balls whose label matches the slot label of the slot into which it is placed. So X1, X2, . . . is an infinite sequence of independent and identically distributed random variables.

   1. (a) Find the expected value and variance of Xn.

   2. (b) Use the central limit theorem to approximate the probability that in the first 40 experiments

      the total number of balls whose label matches their slot label is greater than 40 (this means find

      an approximation to P (?40 Xn > 40) using the central limit theorem.)n=1

Answer 1

Let the event be the event that th slot has the ball labelled . There are ways.

Then
a)S Let be the indicator random variable of the event then

So

Now probability that both i-th and j-th slots get their own matching balls is

Now the expectation,

Hence,

The number of slots that gets matching balls in terms of the indicator random variables is

c) Using linearity of expectation,

Now,

Using linearity of expectation,

b) Define the new random variable .

Now

The probability,