Q.4.16 - A First Course in Probability

Question

Each of $n$ boys and$n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let $G_i$ be the event that girl number $i$is part of a couple. Let $P_0=1-P\left({\cup }_{i=1}^n{G}_i\right)$ be the probability that no couples are formed.

(a) What is $P\left(G_i\right)$?

(b) What is $P\left(G_i\mid G_j\right)$ ?

(c) When $n$ is large, approximate $P_0$.

(d) When $n$is large, approximate $P_k$, the probability that exactly $k$ couples are formed.

(e) Use the inclusion-exclusion identity to evaluate $P_0$.

Step-by-Step Solution

Answer

(a) $P\left(G_i\right)=\frac{1}{n}$

(b) $P\left(G_i\mid G_j\right)=\frac{1}{n-1}$

(c) $P_0\approx P(X=0)=e^{-1}$

(d) $P_k\approx P(X=k)=\frac{1^k}{k!}{e}^{-1}=\frac{1}{k!·e}$

(e) $P_0=1-\left(1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+\cdots +\frac{(-1{)}^{n+1}}{n!}\right)$

Step 1:Given information

Each of $n$ boys and$n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let $G_i$ be the event that girl number $i$ is part of a couple. Let $P_0=1-P\left({\cup }_{i=1}^n{G}_i\right)$ be the probability that no couples are formed.

Step 2:Explanation

We have that,

$P\left(G_i\right)=\sum _{k=1}^{n}P\left(G_i\mid i\right.$ th girl chooses kth boy $) P(i$ th girl chooses kth boy $)$

$=\sum _{k=1}^n\frac{1}{n}·\frac{1}{n}=n·\frac{1}{n^2}=\frac{1}{n}$

We know that$P\left(G_i\mid \right.$$i$th girl chooses kth boy $)=\frac{1}{n}$ since if $ith$ girl chooses kth boy $)=\frac{1}{n}$since if $ith$girl chooses $kth$ boy, they will become a couple if any only if $k th$ boy has chosen $i th$ girl and probability for that is$1 / n.$

Step 3:Final answer

$P\left(G_i\right)=$$\frac{1}{n}$

Step 4:Given information(part b)

Each of $n$ boys and $n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let$G_i$ be the event that girl number $i$ is part of a couple. Let $P_0=1-P\left({\cup }_{i=1}^n{G}_i\right)$ be the probability that no couples are formed.

Step 5: Explanation

If we are given that $j$ girl is in a couple with some boy, we can exclude them from the story. So, we remain with $n-1$ boys and $n-1$ girls. Here we can repeat the story from part (a), so the required probability is

$P\left(G_i\mid G_j\right)=\frac{1}{n-1}$

Step 6:Final answer

The required probability is

$P\left(G_i\mid G_j\right)=\frac{1}{n-1}$

Step 7: Given information(part c)

Each of $n$ boys and $n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let$Gi$ be the event that girl number $i$is part of a couple. Let $P0 = 1 - P(\cup n i=1Gi)$ be the probability that no couples are formed. 

Step 8:Explanation

Define random variable $X$ that counts how many of events $G_i$ are active. The average number of active events is 1 since we have that each of $G_i$ is active with the probability $1 / n$. So, we can approximate $X~$ Pois $\left(1\right)$. Hence

$P_0\approx P(X=0)=e^{-1}$

Step 9: Final answer

$P_0\approx P(X=0)=e^{-1}$

Step 10: Given information(part d)

Each of $n$boys and $n$girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let $Gi$ be the event that girl number$i$is part of a couple. Let$P0 = 1 - P(\cup n i=1Gi)$be the probability that no couples are formed. 

Step 11: Explanation

Using the same notation and idea from part (c), we get

$P_k\approx P(X=k)=\frac{1^k}{k!}{e}^{-1}=\frac{1}{k!·e}$

Step 12:Final answer

$P_k\approx P(X=k)=\frac{1^k}{k!}{e}^{-1}=\frac{1}{k!·e}$

Step 13:Given information(part e)

Each of $n$boys and $n$ girls, independently and randomly, chooses a member of the other sex. If a boy and girl choose each other, they become a couple. Number the girls, and let$Gi$ be the event that girl number $i$ is part of a couple. Let $P0 = 1 - P(\cup n i=1Gi)$ be the probability that no couples are formed. 

Step 14:Explanation

Use inclusion-exclusion formula to obtain that

$P\left({\cup }_{i=1}^n{G}_i\right)=\sum _{i_1}P\left(G_{i_1}\right)-\sum _{i_1<i_2}P\left(G_{i_1},G_{i_2}\right)+\cdots +(-1{)}^{k+1}$

$\sum _{i_1<i_2<\cdots <i_k}P\left(G_{i_1},G_{i_2},\dots ,G_{i_k}\right)+\cdots +(-1{)}^{n+1}P\left(G_1,G_2,\dots ,G_n\right)$

$=n·P\left(G_1\right)-\left(\begin{array}{l}n\\ 2\end{array}\right)P\left(G_1,G_2\right)+\left(\begin{array}{l}n\\ 3\end{array}\right)P\left(G_1,G_2,G_3\right)$

$-\cdots +(-1{)}^{n+1}P\left(G_1,G_2,\dots ,G_n\right)$

$=n·\frac{1}{n}-\frac{n(n-1)}{2}·\frac{1}{n(n-1)}+\frac{n(n-1)(n-2)}{3!}·\frac{1}{n(n-1)(n-2)}-\dots$

$=1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+\cdots +\frac{(-1{)}^{n+1}}{n!}$

The probability $P\left(G_{i_{1}}, G_{i_{2}}, \ldots, G_{i_{k}}\right)$ can be obtained using the similar argument as in part (b). Finally, we have that

$P_0=1-\left(1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+\cdots +\frac{(-1{)}^{n+1}}{n!}\right)$

Step 15:Final answer

$P_0=1-\left(1-\frac{1}{2}+\frac{1}{3!}-\frac{1}{4!}+\cdots +\frac{(-1{)}^{n+1}}{n!}\right)$