TITLE: Probability of having a girlfriend in a school with groups
QUESTION [3 upvotes]: 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.

REPLY [0 votes]: 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,


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


Probability that the certain g girls are not single (complimentary event) =
P4 : $(1-X)^g$
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)$
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.
{"set_name": "stack_exchange", "score": 3, "question_id": 2789829}