Match Maker

Relevant wiki: Expected Value - Problem Solving

We'll be for a bumpy ride, involving expected value of something seemingly unrelated and the fundamental theorem of algebra.

---

Let $p(n,k)$ be the probability that if we take a random permutation of $n$ elements, then exactly $k$ of them are on their original positions. We can prove that $p(n,k) = \frac{D_{n-k}}{k!(n-k)!}$ where $D_k$ is the number of derangements of $k$ elements, but it's not important. The only important fact is that $\displaystyle \sum_{k=0}^n p(n,k) = 1$ , because they are mutually exclusive and exhaustive: any permutation of $n$ elements must have some amount $k$ of them in their original positions, and this $k$ must satisfy $0 \le k \le n$ .

Lemma 1: $\displaystyle \sum_{k=0}^n p(n,k) \cdot k = 1$ .

To prove this, we will use double counting. Suppose we take a random permutation of $n$ elements. What is the expected number of elements that are in their original positions?

On one hand, this can be computed as $\sum ((\text{probability of \$k\$ fixed elements}) \cdot k)$ ; this is the formula for expected value, where you multiply each value with the probability of getting it, and then sum over all possible values. But we know that the only possible values are $0, 1, 2, \ldots, n$ , and the probability of having $k$ fixed elements is $p(n,k)$ by definition. Thus we obtain $\displaystyle \sum_{k=0}^n p(n,k) \cdot k$ , which is the left hand side of the equation.

On the other hand, we can use linearity of expectation to compute this value. Note that any particular element will be in its original position exactly $\frac{1}{n}$ of the time, so the expected value of this particular element being in its original position is $\frac{1}{n}$ . Because expectation is linear even if it's not independent, we can sum over all $n$ elements; the expected number of elements that are in their original positions is $n \cdot \frac{1}{n} = 1$ , the right hand side of the equation.

But these two methods compute the same number, so they must be equal. This completes the proof of the lemma.

---

Now, we will go to the actual problem. Let $E(n)$ be the expected number of attempts, given there are $n$ men and $n$ women.

Claim: $E(n) = n$ for all $n$ .

We will prove this by strong induction on $n$ . The base case is $n = 0$ , where we don't have anyone; then we don't need to do anything at all.

Now, we have the following recurrence relation:

$\displaystyle E(n) = 1 + \sum_{k=0}^n p(n,k) \cdot E(n-k)$

The idea is that we may assume the men to be positions, and the women to be elements; now, pairing them randomly is equivalent to taking a random permutation. A man and a woman make a couple exactly when an element is in its original position. Thus, the probability that we will get exactly $k$ couples correct is simply $p(n,k)$ , again by definition. The $1$ is to count this first attempt. When we have $k$ couples correct, we can just remove them; now we have the exact same problem, but with only $n-k$ men and $n-k$ women, which by definition needs $E(n-k)$ attempts on average; thus, $p(n,k) \cdot E(n-k)$ is the weighted expected number of attempts when $k$ couples are matched. Summing over all $k$ exhausts all possibilities, giving the formula.

Now, by induction hypothesis, $E(n-k) = n-k$ for all $k \ge 1$ . This leaves us with:

$\displaystyle E(n) = 1 + p(n,0) \cdot E(n) + \sum_{k=1}^n p(n,k) \cdot (n-k)$

Another important thing to note is that $p(n,n) > 0$ , because $p(n,n)$ is the probability that all $n$ elements are in their correct positions, which is simply $\frac{1}{n!} > 0$ .

Remember that $\displaystyle \sum_{k=0}^n p(n,k) = 1$ . We have $p(n,1), p(n,2), p(n,3), \ldots, p(n,n-1) \ge 0$ (probabilities are always non-negative) and $p(n,n) > 0$ . This means:

$\displaystyle\begin{aligned} p(n,0) &= 1 - \sum_{k=1}^{n-1} p(n,k) - p(n,n) \\ &\le 1 - 0 - p(n,n) \\ &< 1 - 0 - 0 \\ &= 1 \end{aligned}$

Since $p(n,0) < 1$ , this means $p(n,0) \cdot E(n)$ doesn't fully cancel with $E(n)$ . Thus the equation $\displaystyle E(n) = 1 + p(n,0) \cdot E(n) + \sum_{k=1}^n p(n,k) \cdot (n-k)$ is a linear equation in $E(n)$ , and by the fundamental theorem of algebra, it has exactly one solution.

Finally, we can check that $E(n) = n$ is indeed a solution. The trick uses Lemma 1:

$\displaystyle\begin{aligned} 1 + \left( \sum_{k=0}^n p(n,k) \cdot E(n-k) \right) &= 1 + \left( \sum_{k=0}^n p(n,k) \cdot (n-k) \right) \\ &= 1 + \left( \sum_{k=0}^n p(n,k) \cdot n \right) - \left( \sum_{k=0}^n p(n,k) \cdot k \right) \\ &= 1 + n \cdot \left( \sum_{k=0}^n p(n,k) \right) - \left( \sum_{k=0}^n p(n,k) \cdot k \right) \\ &= 1 + n \cdot 1 - \left( \sum_{k=0}^n p(n,k) \cdot k \right) \\ &= 1 + n - 1 \\ &= n \\ &= E(n) \end{aligned}$

The fourth line is because $\sum p(n,k) = 1$ . The fifth line comes from Lemma 1.

Since we know $E(n) = n$ is a solution, and we know there is exactly only one solution, we can conclude that $E(n) = n$ , completing the proof.

Now we just use the claim for $n = 10$ , the given problem, to obtain $E(10) = \boxed{10}$ attempts to get all couples right.

---

This problem (in a different wording, but essentially the same thing) is actually a problem in Google Code Jam, although I forgot which one.

An elegant way to solve this problem is to use the theory of Martingales . Let $C_k$ denote the number of correctly matched pairs after $k$ matching attempts. Define the random variables $X_k=C_k-k, k \geq 0$ . Clearly, $X_0=0$ . We will show that $\{X_k\}_{k\geq 0}$ constitutes a Martingale sequence, w.r.t. the filtration $\mathcal{F}_n=\sigma(C_1,C_2,\ldots, C_n)$ .

For this, let us first compute expected number of new matches that we get after each matching attempt. Clearly, if there are $m$ unmatched pairs before the attempt, each of the pairs gets matched with probability $\frac{1}{m}$ . Thus the expected number of new matches after the attempt, using the linearity of expectation, is $1$ . Hence, $\mathbb{E}(X_{n+1}| \mathcal{F}_n)=\mathbb{E}(C_{n+1}|\mathcal{F}_n)- (n+1)= C_n+1-(n+1)= X_n$ Thus, it follows that $\{X_k\}_{k \geq 1}$ is a Martingale sequence. Now define the stopping time $\tau$ to be the first time for which $C_\tau=10$ , i.e., all pairs are matched. Using the Optional Stopping Theorem , (using condition (b) for its validity) we get $\mathbb{E}X_\tau= \mathbb{E}X_0=0= \mathbb{E}C_\tau-\mathbb{E}\tau$ i.e., $\mathbb{E}\tau=10 \hspace{10pt} \blacksquare$

After each try we get to know that if we have guessed correctly or wrong. So as there are 10 couples the number of tries will be 10

I just said 10 bc since there are 10 woman and men it must have taken 10 tries; there are a total 20 people and one couple is made out of 2 people so basically 20 divided by 2 :) Hope this helps