ML Interview Q Series: Random Boy-Girl Matching: Probability of No Couples via Inclusion-Exclusion.

Browse all the Probability Interview Questions here.

In a group of n boys and n girls, each boy chooses at random a girl and each girl chooses at random a boy. The choices of the boys and girls are independent of each other. If a boy and a girl have chosen each other, they form a couple. What is the probability that no couple will be formed?

Short Compact solution

Define A_i as the event that the i-th boy becomes part of a couple. Then the probability that no couple forms is 1 - P(A₁ ∪ A₂ ∪ ... ∪ A_n).

For any fixed i:

P(A_i) = n × n^(2n - 2) / n^(2n) = n / n^2 = 1/n

For i ≠ j:

P(A_i ∩ A_j) = n × (n - 1) × n^(2n - 4) / n^(2n) = n(n - 1)/n^4

Continuing similarly and using the principle of inclusion-exclusion:

Hence, the probability that no couple is formed is

1 − P(A₁ ∪ ... ∪ A_n) = 1 − [the above sum].

Comprehensive Explanation

Basic Setup and Notation

We have n boys and n girls. Each boy independently picks one of the n girls uniformly at random. Simultaneously, each girl independently picks one of the n boys uniformly at random. If boy B_i and girl G_j happen to choose each other, they form what we call a “couple.”

We want the probability that no such mutual choice occurs, i.e., no (boy, girl) pair has chosen each other.

Defining Events

Let A_i be the event that the i-th boy is part of at least one couple. Equivalently, A_i is the event “boy i and some girl have chosen each other.” Then:

• The probability that no couple forms is the complement of the probability that at least one of the boys ends up in a couple:

  no couple formed = 1 − P(A₁ ∪ A₂ ∪ ... ∪ A_n).

We use the principle of inclusion-exclusion to handle P(A₁ ∪ ... ∪ A_n).

Computing P(A_i)

To find P(A_i), we need the probability that the i-th boy forms a mutual choice with exactly one girl among the n girls. Breaking it down:

1. Boy i chooses a particular girl G_k. This happens with probability 1/n.

2. That chosen girl G_k must in turn choose boy i. This again has probability 1/n.

But since there are n possible girls G₁, ..., G_n that could end up being the mutual choice for boy i, you multiply by n. Formally:

• There are n ways to pick which girl might mutually choose the i-th boy.

• Probability that the i-th boy picks that specific girl is 1/n.

• Probability that the girl picks the i-th boy is 1/n.

Hence:

P(A_i) = n × (1/n) × (1/n) = n / n² = 1/n.

This matches the expression n × n^(2n - 2) / n^(2n) in the short solution.

Computing P(A_i ∩ A_j) for i ≠ j

Here, we want the probability that both boy i and boy j are part of a couple. This involves:

• Boy i forms a mutual pairing with some girl G_k.

• Boy j forms a mutual pairing with some (other) girl G_m, with m ≠ k to ensure they are distinct couples.

One finds:

• Probability that boy i and girl G_k choose each other is (1/n) × (1/n).

• Probability that boy j and girl G_m choose each other is again (1/n) × (1/n).

• There are n choices for G_k and (n - 1) choices for G_m once G_k is picked.

So:

P(A_i ∩ A_j) = (n × (n-1)) × (1/n) × (1/n) × (1/n) × (1/n) = n(n-1)/n^4.

Principle of Inclusion-Exclusion

The probability P(A₁ ∪ A₂ ∪ ... ∪ A_n) can be expanded using the standard inclusion-exclusion formula:

P(A₁ ∪ ... ∪ A_n) = Σ P(A_i) − Σ P(A_i ∩ A_j) + Σ P(A_i ∩ A_j ∩ A_k) − ...

Following this logic all the way to A₁ ∩ ... ∩ A_n, we end up with:

Here, (n choose k) is the number of ways to pick exactly k distinct boys out of n. For each chosen set of k boys, there are k distinct girls (out of n) who pair up with them in exactly one-to-one fashion. The factor n(n-1)...(n-k+1) in the numerator accounts for the ways to pick k distinct girls for those k boys (each boy in that set has exactly one designated girl). The division by n^(2k) accounts for the mutual-choice probabilities: each of those k boys picks the designated girl (probability 1/n each) and each of those k girls picks the designated boy (probability 1/n each).

Final Probability

The probability that no couple is formed is therefore:

no couple = 1 − P(A₁ ∪ ... ∪ A_n)

= 1 − [that entire inclusion-exclusion sum above].

Hence the final closed-form result is:

1 − Σ_{k=1 to n} [ (−1)^k+1 (n choose k) (n(n−1)...(n−k+1)) / n^2k ].

A Small Simulation in Python

Below is a quick simulation approach (for moderate n) that empirically estimates the probability that no couple is formed:

import random
import numpy as np

def estimate_no_couple_probability(n, trials=10_000_00):
    count_no_couple = 0
    for _ in range(trials):
        # Each boy picks a girl randomly
        boy_choices = [random.randint(0, n-1) for _ in range(n)]
        # Each girl picks a boy randomly
        girl_choices = [random.randint(0, n-1) for _ in range(n)]

        # Check for couples
        any_couple = False
        for i in range(n):
            chosen_girl = boy_choices[i]
            # If that chosen girl picks boy i back, we have a couple
            if girl_choices[chosen_girl] == i:
                any_couple = True
                break
        if not any_couple:
            count_no_couple += 1
    return count_no_couple / trials

for test_n in [2, 3, 4, 5]:
    prob_est = estimate_no_couple_probability(test_n, 100000)
    print(f"n={test_n}, Estimated Probability that no couple forms: {prob_est:.5f}")

This simulation loops over a number of trials where each boy and girl chooses at random, then checks if at least one couple is formed. It counts how often no couple is found.

Follow-up question 1: How does this probability behave for large n?

As n grows, the probability that no mutual pairing occurs tends to decrease. Indeed, with large n, the chance of at least one pair among n boys and n girls choosing each other becomes quite high. One can show through more advanced probabilistic arguments (involving Poisson approximations) that the probability goes to a constant times e^-1-like factor, but the exact limiting behavior would require a deeper asymptotic expansion of the inclusion-exclusion sum.

Follow-up question 2: Why does principle of inclusion-exclusion appear naturally here?

Inclusion-exclusion is the standard combinatorial tool for computing the probability of “at least one” event among many overlapping events. Here, the overlapping events are “boy i forms a couple” for i in {1,...,n}. These events overlap because more than one boy can form a couple simultaneously, making them not mutually exclusive. Hence, to avoid over-counting, inclusion-exclusion is necessary.

Follow-up question 3: Could we simplify the product n(n−1)...(n−k+1)?

This product is the falling factorial expression n_(k) = n × (n−1) × ... × (n−k+1). Sometimes written as P(n, k) = n! / (n−k)!. Using factorial notation, it can be rewritten as n! / (n−k)!. However, leaving it in the falling-product form is quite standard in inclusion-exclusion problems.

Follow-up question 4: Are there alternative ways to interpret the final summation?

Yes. One can interpret the terms as counting the ways to form exactly k couples among a chosen set of k boys and k girls. For each of the k boys (and k girls), the correct probability factor is (1/n)^k for the boys choosing those k girls, and (1/n)^k for those k girls choosing those k boys. The sign (−1)^k+1 arises because of the alternating sum in inclusion-exclusion.

Follow-up question 5: How would you handle any partial constraints, such as only some of the boys and girls being able to choose from a smaller subset?

If each boy or girl can only choose from a specific subset of potential partners (e.g., some constraints or preferences), you would need to adjust the probability terms accordingly. Instead of each choice having probability 1/n, you would use the fraction 1/(size of that subset). The principle of inclusion-exclusion would still hold, but each P(A_i) and P(A_i ∩ A_j) etc., would need to be recalculated carefully.

These discussions illustrate how to extend the same fundamental reasoning to more complex scenarios.

Below are additional follow-up questions

How can we extend the analysis if there are more girls than boys (or vice versa)?

One potential scenario is when the group sizes differ, say we have n boys and m girls with m > n. In that case, each boy picks one girl from the m available, and each girl picks one boy from the n available. The event “a boy B_i forms a mutual couple” still requires that B_i picks some girl G_k and G_k also picks B_i. However, because there are now more girls than boys (or more boys than girls), the counting and probability factors in the principle of inclusion-exclusion change. Specifically:

• Each boy still has probability 1/m of choosing a given girl, and each girl has probability 1/n of choosing a given boy.

• The combinatorial factor when we try to account for k specific couples becomes more involved, since the subset of k boys can match with a subset of k out of m girls (and similarly for the girls choosing those k boys back).

A subtlety arises in ensuring that we carefully track how many ways to select these k distinct girl-boy pairs. The principle of inclusion-exclusion still applies, but each term in the sum will have a slightly different multiplicative factor for counting which subsets of girls can simultaneously form couples with a chosen subset of boys.

A pitfall here is incorrectly scaling the probabilities when the group sizes differ. It can be tempting to assume the same form n(n−1)... is still in the numerator, whereas the correct count might be adjusted to reflect the difference in total group size.

Is there a way to use generating functions or exponential generating functions to handle this problem?

Yes, generating functions (especially exponential generating functions) are often powerful tools for problems involving permutations, matchings, or mutual selections. Here:

1. Each mutual choice can be viewed as an “edge” in a bipartite graph between a boy and a girl.

2. We are interested in the probability of having zero edges that are mutual.

One might set up an exponential generating function that counts the ways to pair i distinct boy-girl pairs. Each pair has a probability factor (1/n)(1/n) = 1/n² in the classical n vs. n scenario. Then the inclusion-exclusion structure sometimes emerges naturally from the logarithm of a generating function.

A potential pitfall is that generating functions can become quite intricate. An incorrectly applied combinatorial argument or an overlooked detail in the bipartite graph interpretation can lead to double counting or miscounting. So careful checking of each coefficient in the generating function is necessary.

How could we compute the distribution of the total number of couples formed, not just the probability of zero couples?

To find the probability that exactly r couples are formed, one can again rely on an inclusion-exclusion style approach:

• For exactly r couples, we choose which r boy-girl pairs out of the possible n×n pairs are going to be the mutual ones.

• We then ensure no other pairs outside those chosen r occur simultaneously.

• There is a combinatorial count of ways for each set of r designated pairs to actually form.

Such computations get more elaborate, because you have to ensure no overlap among couples (each boy can only be in at most one couple, each girl can only be in at most one couple), which restricts which sets of r boy-girl pairs are even possible.

The main pitfall is failing to account for the constraint that a single boy (or girl) cannot appear in two different mutual pairs. This means not all subsets of r pairs are valid. You must only count subsets that match distinct boys to distinct girls.

If the selections are not independent among boys (or among girls), how does this change the analysis?

The independence assumption is crucial in the original model. If, for instance, the boys can “coordinate” or communicate to avoid picking the same girl, the distribution over choices changes drastically. The probability that any particular boy i picks a particular girl G_k is no longer 1/n. For example, you might have:

• Boys choose distinct girls on purpose (to maximize the chance of no collisions).

• Girls might do something similar or might also correlate their choices.

In principle, one could still set up an event A_i = “boy i is in a mutual pairing.” But P(A_i) would become more complicated. You’d need the joint distribution of picks to compute these terms. Inclusion-exclusion remains valid as a combinatorial principle, but each probability P(A_i ∩ A_j ∩ ... ) would require you to consider the correlated nature of how those i, j, ... boys and their chosen girls coordinate their picks.

A common pitfall is to assume that the correlations will not affect the main structure. In reality, even slight correlation can significantly alter the resulting probabilities and make a purely closed-form expression much more difficult to derive.

Could there be floating-point or numerical stability issues when we try to compute these probabilities for large n in an actual implementation?

Yes. Directly computing n(n−1)(n−2)...(n−k+1) or n! can become very large, leading to potential overflow in floating-point representations if n is big. Similarly, raising n to 2k or other large exponents can also create very large numbers. Meanwhile, the resulting probability might be quite small, so you might lose precision if you subtract two nearly equal, large terms.

Strategies to mitigate these pitfalls include:

• Using logarithms of probabilities instead of probabilities themselves to handle multiplications and divisions in log-space, which can reduce overflow/underflow problems.

• Using arbitrary-precision libraries or rational arithmetic if an exact fraction is feasible for smaller n.

• Employing advanced asymptotic approximations (e.g., using expansions or approximating via e⁻¹-like terms) for large n rather than calculating the exact inclusion-exclusion sum.

What if each boy picks a girl uniformly at random, but each girl has a different distribution over the boys?

Suppose every boy still picks uniformly among the n girls, but each girl G_k picks boy B_i with some probability p_k,i that depends on k and i. Those probabilities must sum to 1 for each girl k (so Σ_i=1..n p_k,i = 1). Now the probability P(A_i) = “boy i is in a mutual pairing” changes because the chance that boy i’s chosen girl G_k reciprocates is no longer 1/n but is p_k,i.

Similarly, P(A_i ∩ A_j) or any intersection event requires factoring in the distinct p_k,i for the relevant girls. The principle of inclusion-exclusion still holds, but each term’s computation is unique to the chosen distributions. A big subtlety is that you must keep track of which girl is chosen by boy i and which boy is chosen by that girl.

A pitfall is to assume the final form is a simple adaptation of 1/n → p_k,i. In practice, you must sum over many possible ways that boy i picks some girl G_k while G_k picks i back with probability p_k,i. And you must do so for all relevant boys and girls in each intersection event. The complexity can grow quite fast for large n.

How could we simulate scenarios where we want to see if mutual choices form “clusters” or “groupings” beyond just single pairs?

Sometimes you might wonder if there are patterns such as cycles of length > 2 (e.g., boy1 ↔ girl2, boy2 ↔ girl3, boy3 ↔ girl1). While such cycles aren’t single “couples,” they can be interesting in certain real-world scenarios (though they do not count as couples in the original problem). You could use graph-based interpretations:

• Construct a bipartite directed graph from the random choices: each boy i has an arrow to the chosen girl, and each girl j has an arrow to the chosen boy.

• A mutual couple is precisely a 2-cycle in this directed graph.

• But you could also look for 3-cycles, 4-cycles, etc.

Studying the distribution of these longer cycles involves more intricate graph-theoretic arguments. A typical pitfall is to double-count or misunderstand the difference between 2-cycles (mutual couples) and larger directed cycles. Each type has its own probability structure. If your ultimate goal is just to avoid or detect any mutual pairs, you still focus on 2-cycles. But if the question changes to “What is the probability that the entire group forms disjoint cycles?,” that is a completely different counting problem (and relates to random permutations on bipartite sets).