Solving a probabilistic problem

Question

So I am interested in Computational Investing and came across this problem on a wiki page:

Write a program to discover the answer to this puzzle:"Let's say men and women are paid equally (from the same uniform distribution). If women date randomly and marry the first man with a higher salary, what fraction of the population will get married?"

I don't have much knowledge in probability theory, so I'm not really sure how to implement this in code.

My thinking:

1. Populate two arrays(female,male) with random salary values from a uniform distribution.
2. Randomly pair one female and one male array element and see if condition of higher salary is met.
3. If it is, increment a counter.
4. Divide counter by population and get percentage.

Is this the correct logic? Do woman continually date until there is no males left with higher salaries than women?

Answer 1

My thinking:

1. Populate two arrays(female,male) with random salary values from a uniform distribution.
2. Randomly pair one female and one male array element and see if condition of higher salary is met.
3. If it is, increment a counter.
4. Divide counter by population and get percentage.

Is this the correct logic? Do woman continually date until there is no males left with higher salaries than women?

There are a number of things wrong with the above.

1. Your algorithm has men and women continuing to date after they've been married. It's better to ignore the infidelity problem. You should remove a couple from the pool once they are married.

2. You're only doing steps #2 and #3 once. The randomly chosen pair either will satisfy the condition or they won't, which means your answer will be either 100% or 0%, and never anything in between.

You need some kind of loop and some kind of stopping condition for that loop.

---

First things first: This is a very politically incorrect question. It degrades women by implying that they only marry for money. However, it degrades men even more! Per this question, a male's threshold is "does she have a pulse?"

There are ways to rephrase this question that avoid the political incorrectness issue. For example, let sets X and Y be sets of the same cardinality. Each set comprises members with two attributes, value, which is drawn from U(0,1), and paired, which is initially false. By some scheme, we'll pair members of set X and set Y such that for each pair (x,y), we have x.paired == y.paired == false prior to the pairing and x.value > y.value'. After pairingxandy, thepairedattributes of membersxandyare set totrue`.

The fraction of the population that can be paired depends very much on the algorithm used to match elements of sets X and Y. This is not a well-phrased question.

Serial-serial matching

Assign random values to the value attribute of each member of set X and pf set Y. Walk over members yy of set Y. For each such member y, walk over members x of set X until a member is found that satisfies !x.paired && (x.value > y.value). This member x is then paired with member y.

The percentage of the population that is paired by this algorithm is about 97%.

Serial-random matching

Assign random values to the value attribute of each member of set X and pf set Y. For each pairable member of set Y (a member y of set Y whose value is greater than the maximum value of all unpaired members of set X is not "parable"), repeatedly randomly select a member of x of the unpaired members of set X until x.value > y.value. This member x is then paired with member y.

The percentage of the population that is paired by this algorithm is about 68%.

Random-serial matching

This is in a sense the inverse of the above algorithm. Here we repeatedly select a random member y from the unpaired members of set Y. Then we walk over the elements of set X, in order, until a match is found. Walking over the end says that y is a old maid is unpairable. The algorithm stops when the minimum value of set Y is greater than the maximum value of set X.

The percentage of the population that is paired by this algorithm is about 68%, the same as above.

Random-random matching

Randomly select a member y from the unpaired members of set Y and randomly select a member x from the unpaired members of set X. Pair these two members if x.value > y.value. Keep doing this until there are no pairable members left in the set.

The percentage of the population that is paired by this algorithm is about 68%, the same as above.

Speed dating Speed matching

Basically, this is the above algorithm but in parallel. Here we randomly pair members from the unpaired members of set Y with unpaired members of set X. All of these that meet the criterion x.value > y.value are paired, en masse.

The percentage of the population that is paired by this algorithm is about 68%, the same as above. The performance of this algorithm is anything but that of the above. This algorithm is blazingly fast.

match.com matching Optimal matching

Here we try to match members of set X and set Y that just barely pass the criteria. Doing this serially barely beats the serial-serial algorithm. Do this in parallel, and almost every member gets paired with another. The only ones that don't get paired are the members of set Y that are completely unpairable.