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

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

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 $kth$boy has chosen $ith$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.

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

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 ni=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}$

Final answer

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

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 ni=1Gi)$be the probability that no couples are formed.

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