Chapter 4, Problem 4.23TE

An urn contains 2 n balls, of which 2 are numbered 1, 2 are numbered 2, .. ,, and 2 are numbered n. Balls are successively withdrawn 2 at a time without replacement. Let T denote the first selection in which the balls withdrawn have the same number (and let it equal infinity if none of the pairs withdrawn has the same number). We want to show that, for $0<\alpha <1$, $\underset{n}{\lim }P\left\{T>an\right\}=e^{-\frac{\alpha }{2}}$. To verify the preceding formula, let Mk denote the number of pairs withdrawn in the first k selections, k = 1.. .. n. Argue that when n is large, Mk can be regarded as the number of successes in k (approximately) independent trials.

a. Approximate $P\left\{M_k=0\right\}$ when ii. is large.

b. Write the event $\left\{T>an\right\}$ in terms of the value of one of the variables Mk.

c. Verify the limiting probability given for $P\left\{T>an\right\}$.