Q.4.22 - A First Course in Probability

Question

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<\alpha <1$

$\underset{n}{\lim }P\{T>\alpha n\}=e^{-\alpha /2}$

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

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

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

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

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

Step-by-Step Solution

Answer

1. $n\to \infty \frac{1}{2n-3}\approx \frac{1}{2n-3}$ here there are n number of pairs and the probability of success remains constant and the trials are almost independent.
2. When $n$ is large, the approximate$P\left(M_k=0\right)$$=e^{\frac{1}{2n-1}}$
3. The event $[T>an]$ in terms of the  value of one of the variable $Mk$  is$P\left(\right\{T>\alpha n\left\}\right)=P\left(M_{an}=0\right)$

      d.  The limiting probability $P\{T>\alpha n\}=e^{\frac{-a}{2}}$is verified

Step 1: Given Information (Part-a)

Binomial distribution:

If X is a random variable then its probability mass function is given by

$P\left(x\right)=\left(\begin{array}{l}n\\ x\end{array}\right)p^x(1-p{)}^{n-x}$.

Poison distribution:

If X is a random variable then its probability mass function is given by

$P\left(x\right)=\frac{e^{-\lambda }{\lambda }^x}{x!},x=0,1,2,\dots$

Step 2: Explanation (Part-a)

Here the number of balls in the urn are $2n$numbered with 1 to n ( each number twice). This means there are n number of pairs of balls. In every draw two balls are drawn at a time from the urn without replacement.

Let $M_k$ denote the number of correct pairs withdrawn in the first k selection, k=1,2,.... n.

If the number of balls n is large, which means  $n\to \infty$then $2n\to \infty$

The probability of drawing a success ( drawing of two balls with same number) in the first trial is,

           $=\frac{\left(\begin{array}{l}2\\ 2\end{array}\right)\left(n\right)}{\left(\begin{array}{l}2n\\ 2\end{array}\right)}$

           $=\frac{n(2!)(2n-2)!}{\left(2n\right)(2n-1)(2n-2)!}$

            $=\frac{1}{2n-1}$ 

since, $n\to \infty ,\frac{1}{2n-3}\approx \frac{1}{2n-3}$

Step 3:Final Answer (Part-a)

The answer is $n\to \infty ,\frac{1}{2n-3}\approx \frac{1}{2n-3}$here there are n number of pairs and the probability of success remains constant and the trials are almost independent.

Step 4:Given Information (Part-b)

Here there are n pairs, and$M_k$ denote the number of correct pairs in k trails.

The number of successes follows approximately binomial distribution.

But as$n\to \infty$ , the number of success follows poison distribution ( when probability of $n\to \infty$

success or failure is very small (i.e probability of success or failure tends to zero).

Step 5 :Explanation (Part-b)

The average number of success in k selections is $=\frac{1}{2n-1}\left(k\right)$

.Therefore the number of correct pairs follow poison distribution with parameter 

$\frac{k}{2n-1}$.

Therefore, $\left.P\left(M_i=0\right)=\frac{e^{\frac{i}{2n-1}}{\left(\frac{k}{2n-1}\right)}^0}{0!} P\left(M_i=k\right)=\frac{e^{\frac{1}{2n-1}}{\left(\frac{k}{2n-1}\right)}^x}{x!}\right)$

                 $=e^{\frac{1}{2n-1}}$

Step 6:Final Answer (Part-b)

The answer is $P\left(M_k=0\right)$$=e^{\frac{1}{2n-1}}$

Step 7: Given Information (Part-c)

Given, $0<\alpha <1$ denote the first selection in which the balls withdrawn have the same number.

Step 8:Explanation (Part-c)

 The event $\{T>\alpha n\}$means in the first selection the balls withdrawn have the same number. This means the number of correct pairs is zero.

Therfore it is  $P\left(\right\{T>\alpha n\left\}\right)=P\left(M_{an}=0\right)$

Step 9:Final Answer(Part-c)

The answer is $P\left(\right\{T>\alpha n\left\}\right)=P\left(M_{an}=0\right)$

Step 10 :Given Information (Part-d)

The limiting probability given  for $P\{T>\alpha n\}$is $\underset{n\to \infty }{\lim }P\{T>\alpha n\}=\underset{n\to \infty }{\lim }P\left(M_{an}=0\right)$

Step 11:Explanation (Part-d)

$\underset{n\to \infty }{\lim }P\{T>\alpha n\}=\underset{n\to \infty }{\lim }P\left(M_{an}=0\right)$

                         $=\underset{n\to \infty }{\lim }{e}^{\frac{-an}{2n-1}}$

                           $=\underset{n\to \infty }{\lim }{e}^{\frac{-a}{2-\frac{1}{n}}}$

                         $=e^{\frac{-a}{2}}$

Step 12:Final Answer(Part-d)

The answer is$P\{T>\alpha n\}=e^{\frac{-a}{2}}$ Is verified