We had mentioned once previously that statisticians think, as it relates to dating, that to be optimal, one must be prepared to be lonely 37% of the time. Here, I was citing the secretary problem without understanding it at all.
The problem is given n candidates, how do you maximize the probability of marrying the best one when you must date the candidates in sequence. Your only options are to pass or to marry. You do not know what the maximum score a candidate can have – in fact you have no idea what the distribution of the candidates is at all.
The simplicity of the solution is largely dependent on the fact you know very little. Because you know nothing about the distribution, and you cannot infer anything about the distribution from the candidates already dated, the only possible strategy is: at point p, the % of candidates already dated, you accept the next potential winner. [Note 1]
Assuming you use this strategy, what is the likelihood of choosing #1 to marry? If #1 occurs < p, then you lose. If #1 > p, and #2 < p, then you win. If #1 > p, and #2 > p and #3 < p then you win if #1 occurs before #2 (probability = 1/2). If #1 > p, and #2 > p, #3 > p and #4 < p then you win if #1 occurs before #2 and #3 (probability = 1/3). And so on. Writing this out in probability form, we see that the probability of winning is
This expression simplifies to (this is not obvious, but it is a commonly used Taylor Series)
P is optimized at p = 1/e. The best outcome is P = 1/e. So, in fact, you are rather unhappy at 1-1/e (63%) of the time. That’s a lot of the time. Since ~50% of marriages end in divorce, this model appears to have some consistency.
It is likely that in real life the maximization function is not to maximize the probability of marrying #1, but also be fine with, say, the top 3. Let's assume you use the same strategy as before. This isn't the optimal strategy, but probably not too far from the truth. P takes the following form:
The optimal stopping point is ~0.26 and P is 0.59, which is much more satisfied. [Note 2]
But the other reason why people can do better than even 0.59 is that from experience, they can begin to understand the distribution from which candidates are drawn. Let’s assume that this time, there is a known maximum. In fact after some dates, a likely maximum of a set will become statistically meaningful to estimate. An estimate of about (current max)*(n+1)/n would at least be unbiased, if not statistically meaningful.
Without the loss of generality, let's assume candidates are drawn from a uniform distribution [0,1]. That means if you meet a candidate that is 0.999, even if it is the first person you meet out of 100, you would probably marry him or her [Note 3].
Given x, the most recent maximal point, and n, the number of future draws, we can see the probability of winning if you choose to marry here is x^n. The probability of winning if you choose to pass is more complicated. Of the remaining n draws, one would expect to draw m candidates superior to x with a probability of distribution of binomial. Similar to the last problem, you win if #1 is the first one drawn thereafter, which happens with a likelihood of 1/m [Note 4].
From this point on, the math turns funky, difficult and often not solvable without a computer. This equation, for example, is not solvable but we can approximate it in the limit accurately: x = n/(n+0.8043). If you draw a number greater than x(n) on turn n, you should marry. The probability of winning pursuing this strategy is 0.580164 for large n , which is a lot higher than 1/e. [Note 5]
Book: https://www.amazon.com/gp/product/0486653552/ref=od_aui_detailpages00?ie=UTF8&psc=1
Paper: https://link.springer.com/chapter/10.1007%2F978-0-387-44956-2_22
Note 1: Is it clear that this is the only possible strategy? Since the historical data is irrelevant, the only variable appears to be p. This isn't hard to convince yourself of.
Note 2: This is clearly not the optimal strategy because if you got to the last draw, and you drew #2, you would take it.
Note 3: Note that we are effectively assuming a uniform distribution [0,1] but we don’t lose any generality here since every distribution can be mapped to a uniform one (this mapping is at the heart of the Gaussian Copula).
Note 4: There is a small logical leap here. It is not clear that just because the local maximum is being satisfied that the global maximum is being satisfied. But you might notice that as you wait, your chance of winning goes down. So in this case, what you would have accepted at time a, you certainly will accept at time b. Perhaps this point requires no explanation at all since it is all too well known for people in the dating market. Put another way the "decision numbers are monotone decreasing".
Note 5: One important simplification is consolidating n!/(n-m)! to n^m, which is true in the limit (used in the Poisson approximation of Binomial, interestingly). That leaves what looks like a Taylor series in terms of a = (1-x)/x. It appears this step requires a computer since it cannot be simplified. An excel spreadsheet can tell us that a = (1-x)/x = 0.8043, so then it tells us that x = n/(n+0.8043). The probability of winning is, also, unsolvable and requires a computer.