Probability of having a girlfriend in a school with groups

Question

A school has $r$ groups. Each group has $n$ girls and $n$ boys. Any boy and girl know each other with probability $p$ if they belong to the same group, and with probability $q$ if they belong to different groups. In random order, a boy marries a girl to whom he is connected to by an edge (if they know each other). If is the turn of a guy who knows no girl or all the girls he knows are taken, he remains alone.

What is the probability that a guy will actually stay single?

The answer is similar to the one of a random bipartite graph admitting a perfect matching, and to the answer in this thread. The best answer will be awarded 100 bounty points, which I cannot add before 2 days.

Answer 1

Assuming a particular boy is being discussed. Following solution involves basic principles of probability and properties of the Bernoulli distribution.

If the boy knows certain h girls from his group and certain (g - h) from other groups,

1. • Probability that the boy knows h girls from his group (using Bernoulli distribution) =

   P1 : $\left(\begin{array}{c}n\\ h\end{array}\right)p^h(1-p)^{n-h}$

   • Similarly for (g - h) girls of other group =

   P2 : $\left(\begin{array}{c}n(r-1)\\ g-h\end{array}\right)q^{g-h}(1-q)^{n(r-1)-(g-h)}$

2. Probability that boy knows total g girls i.e. h + (g - h) = $\sum_{h=0}^g$ P1 × P2 =

   P3 : $\sum_{h=0}^g\left(\left(\begin{array}{c}n\\ h\end{array}\right)p^h(1-p)^{n-h}\right)\times\left(\left(\begin{array}{c}n(r-1)\\ g-h\end{array}\right)q^{g-h}(1-q)^{n(r-1)-(g-h)}\right)$

Let probability that boy (or girl since it's symmetric) is single = $X$

3. Probability that the certain g girls are not single (complimentary event) =

   P4 : $(1-X)^g$

4. Probability that the boy knows g girls and none is single = P3 X P4 =

   P5 : $(1-X)^g\times\sum_{h=0}^g\left(\left(\begin{array}{c}n\\ h\end{array}\right)p^h(1-p)^{n-h}\right)\times\left(\left(\begin{array}{c}n(r-1)\\ g-h\end{array}\right)q^{g-h}(1-q)^{n(r-1)-(g-h)}\right)$

5. Probability that the boy knows (maybe $0$ ) girls and none is single = $\sum_{g=0}^{n\times r}$ P5 =

   P6 : $\sum_{g=0}^{n\times r}(1-X)^g\times\sum_{h=0}^g\left(\left(\begin{array}{c}n\\ h\end{array}\right)p^h(1-p)^{n-h}\right)\times\left(\left(\begin{array}{c}n(r-1)\\ g-h\end{array}\right)q^{g-h}(1-q)^{n(r-1)-(g-h)}\right)$

Probability that the boy is single = P6 =

$X$ = $\sum_{g=0}^{n\times r}(1-X)^g\times\sum_{h=0}^g\left(\left(\begin{array}{c}n\\ h\end{array}\right)p^h(1-p)^{n-h}\right)\times\left(\left(\begin{array}{c}n(r-1)\\ g-h\end{array}\right)q^{g-h}(1-q)^{n(r-1)-(g-h)}\right)$

Note that value of $X$ evaluated from above expression will be independent of g and h.