The Random Matching Puzzle: How Many Matches Should We Expect?

[bob012345]

TL;DR

This is a variation of an old problem. The goal is to match objects between two sets by pure guessing. I hope I didn’t mess up the wording.

You are given ten objects in set A and ten objects in set B. There is a one to one correspondence between the objects in sets A and B but you know nothing and have to guess each pairing. The question is on average, how many guesses did you get correct?

Spoiler

The answer is just one. An easy way to sense this is assume there are just two objects in each set. Then, either you get both correct or none correct. Then, the average would be one over many trials. It is also independent of how many objects there are as long as the sets have a one to one correspondence. We could change ten to $n$ and still get one. I suspect most folks here intimately familiar with statistics and probability knew that but for others it is a surprising result as it was to me. The variant I used as a source is from the introduction to Paul J. Nahin’s book Digital Dice where he quotes a version from Marilyn vos Savant’s column involving a pop quiz matching 24 presidents with their terms in office.

 

[anuttarasammyak]

The total number of ways to create a one-to-one correspondence between two sets of 10 elements is 10!= 3,628,800. Thus probability of perfect matching would be its inverse.

If I can say "all 10 elements in set A correspond to no.1 in set B", I surely get 1 correct correspondence.

 

[FactChecker]

I can't follow this:

It is also independent of how many objects there are as long as the sets have a one to one correspondence.

 

[bob012345]

The total number of ways to create a one-to-one correspondence between two sets of 10 elements is 10!= 3,628,800. Thus probability of perfect matching would be its inverse.

If I can say "all 10 elements in set A correspond to no.1 in set B", I surely get 1 correct correspondence.

True, but I stressed the one to one correspondence and that you have to pair one member of set A to one member of set B. You don’t have ten number 1’s in set B to pair with each member of set A.

 

[bob012345]

I can't follow this:

Let’s say set A is the numbers 1 through 10 in order. Set B are the same numbers but in random order. The answer here would be the same if there were 10 or 20 or any number as long as each member of A corresponded to one member of B.

 

[PeroK]

Let’s say set A is the numbers 1 through 10 in order. Set B are the same numbers but in random order. The answer here would be the same if there were 10 or 20 or any number as long as each member of A corresponded to one member of B.

Imagine repeating the experiment many times. How often does 1 get matched to the corresponding element from set B? If there are n elements, then 1/n. This is the case for every number. So, the expected number of matches is precisely 1. No matter how many elements are in the two sets.

 

[FactChecker]

Imagine repeating the experiment many times. How often does 1 get matched to the corresponding element from set B? If there are n elements, then 1/n. This is the case for every number.

If they are independent. But if the first n-1 have matched, then the last one must match. They are not independent.

 

[FactChecker]

Let’s say set A is the numbers 1 through 10 in order. Set B are the same numbers but in random order. The answer here would be the same if there were 10 or 20 or any number as long as each member of A corresponded to one member of B.

I understand what the words mean, but I can't see clear logic for that conclusion.

 

[PeroK]

If they are independent. But if the first n-1 have matched, then the last one must match. They are not independent.

The probability of any number matching is 1/n. Over a large number of trials, k, it will match k/n times. So, the total number of matches in n(k/n) = k. So, the expected number of matches per trial is 1.

It doesn't matter that different numbers matching on any given trial are not independent events.

 

[FactChecker]

The probability of any number matching is 1/n.

I disagree. They are dependent events. They are only independent if multiple A objects can be matched with the same B object.
The case of n=2 makes that clear. If one object matches, the other MUST match the remaining B object, (unless you allow both objects to be matched to the same B object, which is not how I interpret the problem).

 

[bob012345]

I disagree. They are dependent events. They are only independent if multiple A objects can be matched with the same B object.
The case of n=2 makes that clear. If one object matches, the other MUST match the remaining B object, (unless you allow both objects to be matched to the same B object, which is not how I interpret the problem).

Sure, it must. For any $n$ you can match any number up to $n$ except $n-1$. For your example that is zero and two. That doesn’t change what is being said about the average number of matches which is the total number of matches divided by the number of trials. Here is some data for different cases of $n$ all with 20 trials. The average number of matches per trial goes as 1.15, 1, 1. It is coincidence that the cases for 10 and 20 objects is exactly 1. These have small sample size. For many trials the average gets very close to 1.

 

[bob012345]

In the data above, each trial of set B is randomly ordered independent of set A.

 

[FactChecker]

Oh, I see it now! I'm not sure I can coherently say what I got wrong and see correctly now, though. Thanks!

 

[Matterwave]

I tried to solve this in my head while taking a walk thinking it'd be an easy puzzle. But I ran into difficulty and eventually I had to look up the operation I didn't know how to do.

I label the objects in set A as 1 through N. The simplified game is: I pick out the objects 1 at a time at random, how often do I pick the nth number on the nth pick?

The partial solution I arrived at is: for each k < N I should be able to get a value (an integer), say M(k), of the number of permutations such that exactly k are in the right position. This value should be N choose k multiplied by "the number of ways to permute the rest such that they're all wrong". Finally I should be able to do $\frac{1}{N!}\Sigma_{k=1}^N k\cdot M(k)$ (the $k=0$ "term" is 0 but it actually accounts for a lot of permutations).

It's here that I failed to come up with a formula. "The number of ways to permute N-k objects such that none of the N-k objects are in their original position" is not something I know how to do. But apparently it's a thing: https://en.wikipedia.org/wiki/Derangement

Hence, my (partial) solution should be:

$$\langle k\rangle = \frac{1}{N!}\sum_{k=1}^N k\cdot\frac{N!}{(N-k)!k!}\cdot D_{N-k}$$

I don't know how to evaluate the above so... I checked for $N=3,4$ by hand and got 1. I suppose one could write a short snippet of code to calculate the above for arbitrary N and I guess they all evaluate to 1.

 

[PeroK]

I disagree. They are dependent events. They are only independent if multiple A objects can be matched with the same B object.
The case of n=2 makes that clear. If one object matches, the other MUST match the remaining B object, (unless you allow both objects to be matched to the same B object, which is not how I interpret the problem).

Put 10 balls in a bag, numbered 1-10. The probability that the first ball is #1 must be 1/10. The probability that the last ball is #10 must be 1/10. The same for all the numbers in between.

If you did 100 trials, you would "expect" #1 to be the first ball 10 times. And you would expect #10 to be the last ball 10 times. The same with the others.

Overall, therefore, you'd expect the total number of matches to be 100. One per trial.

I didn't really expect on a science forum to have such a battle over this.

 

[PeroK]

I tried to solve this in my head while taking a walk thinking it'd be an easy puzzle. But I ran into difficulty and eventually I had to look up the operation I didn't know how to do.

I label the objects in set A as 1 through N. The simplified game is: I pick out the objects 1 at a time at random, how often do I pick the nth number on the nth pick?

The partial solution I arrived at is: for each k < N I should be able to get a value (an integer), say M(k), of the number of permutations such that exactly k are in the right position. This value should be N choose k multiplied by "the number of ways to permute the rest such that they're all wrong". Finally I should be able to do $\frac{1}{N!}\Sigma_{k=1}^N k\cdot M(k)$ (the $k=0$ "term" is 0 but it actually accounts for a lot of permutations).

It's here that I failed to come up with a formula. "The number of ways to permute N-k objects such that none of the N-k objects are in their original position" is not something I know how to do. But apparently it's a thing: https://en.wikipedia.org/wiki/Derangement

Hence, my (partial) solution should be:

$$\langle k\rangle = \frac{1}{N!}\sum_{k=1}^N k\cdot\frac{N!}{(N-k)!k!}\cdot D_{N-k}$$

I don't know how to evaluate the above so... I checked for $N=3,4$ by hand and got 1. I suppose one could write a short snippet of code to calculate the above for arbitrary N and I guess they all evaluate to 1.

You don't have to guess. I've proved it's 1 in each case!

 

[Matterwave]

You don't have to guess. I've proved it's 1 in each case!

Heh, fair. I didn't try to read the other posts in this thread in detail before I posted so that I didn't spoil myself.

But in that case, me using the word "guess" there would be because I'm guessing that my solution (the eqn I presented) is correct and reproduces your "1 in each case".

 

[PeroK]

Heh, fair. I didn't try to read the other posts in this thread in detail before I posted so that I didn't spoil myself.

But in that case, me using the word "guess" there would be because I'm guessing that my solution (the eqn I presented) is correct and reproduces your "1 in each case".

I see what you mean.

 

[PeroK]

More simply:
$$E = \sum_{k=1}^{n}kp(k)$$where $p(k)$ is the probability of precisely $k$ matches in a set of size $n$.

The trick is to see that this can be calculated without needing the probabilities. By looking at the expected value for each individually number:
$$E = \sum_{k =1}^n E(k) = nE(1) = 1$$where $E(k)$ is the expected number of times number $k$ is matched.

 

[Hornbein]

Linearity of expectation states that the expected value of a sum of random variables is always equal to the sum of their individual expected values, regardless of whether the variables are independent or dependent.

The main thing I learned in my studies of probability is to try not to see the situation as a process. That's tricky. Strive to come up with a static analysis where nothing changes.

 

[FactChecker]

The main thing I learned in my studies of probability is to try not to see the situation as a process. That's tricky. Strive to come up with a static analysis where nothing changes.

I think that describes my mistake. If I look at it as the process of assigning A elements into positions to match B elements, I went down the rabbit-hole of complicated conditional probabilities. On the other hand, if I look at it as a B element receiving one of the N A elements to match, I get the 1/N probability with no conditional complications. (Is that correct? I will have to think about that.)

 

[bob012345]

I didn't really expect on a science forum to have such a battle over this.

I think what makes such a puzzle such as this one interesting is that it is counting on there being a subtle confusion between expectation and probabilities. It became obvious to me in hindsight but it wasn’t obvious to me in foresight.

 

[Hornbein]

I never found the linearity of expectation to be obvious. Dependencies between the random variables change the distribution of their sum but not the expectation of that sum. It just a fact I remember from school.

The proof is that expectations are defined as Lebesque integrals and Lebesque integrals are linear. End of story.

 

[anuttarasammyak]

If I can say "all 10 elements in set A correspond to no.1 in set B", I surely get 1 correct correspondence.

The correspondence is fixed throughout the game. On each turn, I propose one pairing, for example, “a₁ corresponds to b₂,” and receive a yes-or-no answer.

In the luckiest case, I can determine the complete correspondence in just 9 turns. In the unluckiest case, it takes 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 turns.

I assume that the average number of turns is half the maximum, i.e., 45/2 = 22.5 turns in approximation at least.

 

[PeroK]

I never found the linearity of expectation to be obvious. Dependencies between the random variables change the distribution of their sum but not the expectation of that sum. It just a fact I remember from school.

The proof is that expectations are defined as Lebesque integrals and Lebesque integrals are linear. End of story.

The events must be mutually exclusive but not necessarily independent.

Although, in this case, you still need to look at the events in the right way.