Q.4.62 - A First Course in Probability

Question

Consider n independent trials, each of which results in one of the outcomes $1, ... , k$ with respective probabilities $p_1,\dots ,p_k, \sum _{i=1}^k{p}_i=1$Show that if all the $pi$ are small, then the probability that no trial outcome occurs more than once is approximately equal to$\exp (-n(n-1)\sum _i{p}_i^2/2)$. 

Step-by-Step Solution

Answer

The probability that there will not be such a pair is $\exp \left(-\frac{n(n-1)}{2}·\sum _{j=1}^k{p}_j^2\right)$.

Step 1: Given information

Consider $n$ independent trials, each of which results in one of the outcomes $1, ... , k$ with respective probabilities $p_1,\dots ,p_k, \sum _{i=1}^k{p}_i=1$.

Step 2: Explanation

For the opening, consider only two trials. Because of the independence, the probability that in these two trials we will get the exact results is simply

$p=\sum _{j=1}^k{p}_j^2$

Now, let's look at all possible pairs of $n$ trials. There exist $\left(\begin{array}{l}n\\ 2\end{array}\right)=\frac{n(n-1)}{2}$ such combinations.

The probability that each pair has the property that they have the same outcome is $p$.

Define $X$ as the random variable that marks the number of pairs that have the same outcome. Use the Poisson property to obtain that $X$ has approximately $Pois\left(\lambda \right)$ distribution, where

$\lambda =\left(\begin{array}{l}n\\ 2\end{array}\right)\times p=\frac{n(n-1)}{2}·\sum _{j=1}^k{p}_j^2$

Hence, the probability that there will not be such a pair is

$P(X=0)=\exp (-\lambda )=\exp \left(-\frac{n(n-1)}{2}·\sum _{j=1}^k{p}_j^2\right)$

Which had to be shown.

Step 3: Final answer

The probability that there will not be such a pair is $P(X=0)=\exp (-\lambda )=\exp \left(-\frac{n(n-1)}{2}·\sum _{j=1}^k{p}_j^2\right)$