The Strategy for choosing a Mate
What's Cool about thisNotice that if you, young lady, pick your spouse at random, the probability of making the "best" choice would be 1/n. Furthermore, surely our intuition tells us that, as n increases, our chances of choosing the best mate-- regardless of the strategy-- would surely decrease to zero. (The more suitors, the less likely we'd be to pick the best one.)But this turns out not to be the case! We can show that even if n tends to infinity, there is a strategy that will enable us to single out the best spouse almost 37% of the time !!
The following is incomplete. I will add to this as time permits:
The Odds of Finding Prince CharmingLet's begin with a simple example to show the approach we will eventually use. Suppose there were only n=3 suitors in your future, and we decide to reject the first marriage proposal, and pick as our mate the next suitor that appears who is better than the first one.Let 3 denote the best suitor (the one who would be best as a mate), 2 the second best, and 1 the least worthy. We can easily make a list and see that the sample space consists of six possible orders in which we might meet the suitors. Let (i,j,k) represent the sample outcome wherein the ith-rated suitor appears first, the jth-rated appears second, and the kth-rated third. Then the outcomes in S can be written (1, 2, 3)Notice that he sequences marked by "*"s are the ones for which our proposed strategy would yield the best choice. Since all orderings are equally likely, the probablility of this particular strategy working is 3/6, making it clearly superior to the "random" procedure that would have a probability of only 1/3 of choosing the best suitor. Before considering this as a general optimized strategy, we need to define a term as follows. A candidate for marriage is any suitor that is better than all the others we have seen up until that point. For example, if n were 4 and the order of presentation were 3214, then 4 (and 3, trivially) would be the only candidates. If the order were 1234, then all four suitors would be candidates.
Theorem . The form of the optimal strategy is to reject the first x - 1 suitors, and choose as the mate the first candidate appearing thereafter.Proof. If suitor i is a candidate, it makes sense to choose him as a husband if the probability of his being the best choice exceeds the probability of finding the best choice using whatever the optimal strategy is, beginning with the (i + 1)st suitor. THat is, we should choose suitor i (provided he is a candidate) if P(we win with suitor/candidate i) > P(we win with optimal strategy from i + 1 on) Clearly the probability on the right side must decrease as i increases (for i = 0, its value is precisely what we are seeking; at i = n - 1, it acheives its minimum, 1/n. To complete the prrof, we need to know something about the behavior of the probability on the left side. Lemma. Given n suitors, the probability of a candidate in the ith position being the eventual husband is directly proportional to i; specifically,...to be continued...
This proof can be found in precise detail, with its original phrasing,
in Larsen and Marx's Introduction to Probability and it's Applications, p. 90.
shannon@sleckey.com |