Optimizing your wife. From MathPages, via reddit. (This is apparently also known as the secretary problem or the sultan's dowry problem.)
The following is a semi-standard bit of mathematical folklore. Say you expect to meet N possible suitors in your life. You want to maximize your chances of picking the best one, given that you expect to meet these people in a random order, and once you say no to one of them you can never see them again, and that you can say for any two of them either "X is better than Y" or "Y is better than X". (There are no ties, and everybody's comparable.)
My readers who are not mathematicians are probably thinking that these are ridiculous assumptions. This is true. In particular, the first one seems silly to me -- we don't meet people at random, but through other people we know, so I suspect that the longer one spends living the more one tends to find people one likes. This certainly is true in my experience when seeking out friends -- people who I like spending time with tend to know other people I'd like spending time with. The inability to go back to previous suitors seems to be not a horrible approximation. The fact that everyone is rankable seems at first like a bad assumption -- but we manage to do it for economic goods all the time. For example, houses have prices which are scalars, despite the fact that there are multiple dimensions along which houses can be compared. The fourth assumption, that you know how many potential suitors there are, seems the most wrong to me. But combined with the assumption that you meet suitors at a constant rate, this converts strategies which talk about numbers of suitors to strategies which talk about time.
My readers who are mathematicians probably didn't read the previous paragraph.
Anyway, the optimal strategy is to reject the first N/e of the people you meet, and then pick the first person you meet who's better than everyone you'd met previously. The probability of this strategy succeeding -- in that you pick the very best person -- is close to 1/e when N is large.
I'm pretty sure I first heard this around fifteen years ago, and have probably heard it at least once a year since then -- but I didn't know a proof until now. (Strictly speaking, there's some hand-waving in the argument given there, as there always is whenever someone says "X is approximately equal to Y" without giving any sort of bound on X-Y or X/Y -- but I don't plan to use this to prove anything else, so I'm convinced.)
Subscribe to:
Post Comments (Atom)
13 comments:
That "1/e for large N" reminds one immediately of counting the number of derangements! I wonder if there is some connection there.
The fourth assumption, that you know how many potential suitors there are, seems the most wrong to me.
That's exactly why I hated this formulation. It's a great toy problem, but horrible marketing. Besides, it gives the lay audience the impression that we mathematicians actually think so coldly and calculatingly about romance.
Do we really want to maximize our probability of finding the best one? This strategy of course guarantees that if you meet the best one in the first 1/e of your dating life, you'll remain unwed forever, despite finding people who come very close in quality to that high point. I think a slightly more forgiving strategy would be better, but then we need not just "X > Y" but an actual numerical value for each suitor.
I first heard this problem in the context of a game. You have a stack of a million index cards which you'll go through one by one, and you have to stop when you think you're on the highest card. I find this version a little easier to picture, since the assumptions you listed are much easier to control.
A good first pass at the strategy is what you described, except rejecting the first half of the cards (instead of 1/e). This is not optimal, but still surprisingly good--for large N, you have a 1/4 chance of winning, and it's easier to prove than the optimal solution. Basically, you'll win if and only if the highest card is in the second half and the second-highest card is in the first half, and this will obviously occur about 1/4 of the time.
I agree with the connection to derangements. And of course this is a problem about a property of permutations. There might be a connection; I haven't thought about it.
susan, what about if the third-highest is in the first half of the deck, the first and second are both in the second half, and the second comes after the first. Then you'll also win, won't you?
There is an elegant proof in Mosteller's "Fifty Challenging Problems in Probablity." See problem # 47, "Choosing the largest Dowry."
There is also a large literature on optimal stopping problems
My readers who are mathematicians probably didn't read the previous paragraph.
Heh. I'm laughing at myself right now for being predictable.
unapologetic: Good catch. The odds of that situation would be 1/16, if I've figured it correctly. (1/8 chance that each card in the correct half, and 1/2 for the required ordering of the cards in the second half.) Then you can continue figuring the probabilities for 4 cards, 5 cards, etc. The total probability would be 1/4 + 1/16 + 1/64 + 1/256... which I believe converges on 1/3 -- noticeably better than 1/4!
My readers who are mathematicians probably didn't read the previous paragraph.
Ha ha, maybe, but I found the discussion of the assumptions as interesting as the result itself.
I have heard that there are government grants available to help women and minorities with a small business. Finding the actual grants is a little difficult any information the actual name of the specific grants or something to send me in the right direction would help. Anyone have info on obtaining a government grant for small businesses? Thanks.
Sudipta Das
______________
Free grant
Good post.
Thanks for the info, you can also find Government Grants here,
or Free Grant Kit here,
Free Grant Kit Grant Kit
Post a Comment