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)$.

Short 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-by-step solution

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$.

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.

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)$