An urn contains 2n 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 < α < 1,

To verify the preceding formula, let M_k denote the number of pairs withdrawn in the first k selections, k = 1, . . . , n.

(a) Argue that when n is large, M_k can be regarded as the number of successes in k (approximately) independent trials.

(b) Approximate P{M_k = 0} when n is large.

(c) Write the event {T > αn} in terms of the value of one of the variables M_k.

(d) Verify the limiting probability given for P{T > αn}.

Transcribed Image Text:

lim P{T > an} = e-a/2