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.

  • 1
    $\begingroup$ In the regime where $p,q$ are constant, we can argue that the answer is $\Theta(\frac1{rn})$ in exactly the same way as before, replacing edge probabilities with $\max\{p,q\}$ or $\min\{p,q\}$ as appropriate. Are you interested in a different asymptotic behavior of $p,q$, greater precision, or both? $\endgroup$ – Misha Lavrov May 21 '18 at 15:32
  • $\begingroup$ I am looking to understand the probability that the greedy algorithm selects a perfect matching, both for $p,q$ constant or functions of $n$. I am also interested in the diameter of the corresponding graph, which has been suggested must be $\log n/ \log degree$ (proposition 4 people.fas.harvard.edu/~bgolub/papers/homophily.pdf) $\endgroup$ – fox Jun 1 '18 at 17:47
  • $\begingroup$ I think one can use the coupon colelctor problem, each man proposes to a girl at one step, the girl rejects him if she has a bette rpartner already, there are log(rn) proposals made in total, subject to a minor modification people.eecs.berkeley.edu/~jfc/cs174/lecs/lec7/lec7.pdf $\endgroup$ – fox Jun 1 '18 at 18:03

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

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

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

    P4 : $(1-X)^g$

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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.