7
$\begingroup$

I am trying to prove the theoretical "37-percent rule" for dating. The setup, if I remember correctly, is this. Suppose that you will meet exactly $N$ potential mates in your life, and you will meet them one at a time, in a perfectly random order. The potential mates rank from best to worst (in a total ordering), and you want to maximize the probability that you end up with the best one. However, you can only tell how good the mates are relative to each other, so while you can fully rank the people you've already met, you can't say anything about the ones you have yet to meet. Also, for each potential mate, you can either stay with them forever or leave forever, i.e. there is no divorce or post-breakup dating.

The result I have heard, and which I am trying to prove, is that your best strategy is to wait and reject the first 37% of them ($1/e$, to be precise), and then marry the next one that is better than all you have previously met. The $1/e$ number presumably arises as the limit as $N \to \infty$.

Obviously, you should never marry someone who isn't strictly better than all the previous ones, because then your chances of picking the right one are $0$. Also, given a strategy that you wait through the first $K$ partners and then marry the next one that is the best so far, I calculate your expected chances of succeeding as \begin{equation} \frac{\displaystyle \sum_{M = K}^{N-1} \frac{M - 1 \choose K-1}{N - M}}{N \choose K} \end{equation}

(Let $M$ be the maximum value among the first $K$ people you meet, where $1$ is the value of the worst person, $2$ is the next, and so on, with your desired mate having value $N$. Given $M$, your chances of winning are $\frac{1}{N - M}$, because the value $N$ must be the first to appear out of the highest $N - M$ values. The chances of the maximum being exactly $M$ are ${M - 1\choose K - 1}/{N \choose K}$.)

(The above formula doesn't technically work for $K = 0$, but the reasonable convention ${-1 \choose -1} = 1$ gives the desired value $\frac1N$.)

The two things I am unable to prove, and which I would like to see ideas for, are:

  1. Given that you never pick someone unless they are the best so far, how do you prove further that the best strategy must involve waiting for some $K$ people and then going for anyone else after that $K$?

  2. Why is the formula above optomized at $K = N / e$, and how could one show this?

$\endgroup$
  • 5
    $\begingroup$ See en.wikipedia.org/wiki/Secretary_problem $\endgroup$ – Mankarse May 14 '13 at 12:04
  • $\begingroup$ @Mankarse: thanks - it appears I didn't search for this problem under the right name. However, Wikipedia doesn't address (1) or prove (2), and the approach for (2) it gives is stronger and possibly different(?) and confuses me. I would be interested in more elementary proofs or at least intuitions for (2). $\endgroup$ – 6005 May 14 '13 at 12:27
  • 1
    $\begingroup$ math.stackexchange.com/questions/45266/… $\endgroup$ – ShreevatsaR May 14 '13 at 13:41
  • $\begingroup$ "Obviously, you should never marry someone who isn't strictly better than all the previous ones, because then your chances of picking the right one are 0." Oh? Why would you ever choose the first candidate? (You wouldn't.) But the first might be the best, so you're forced (then) to marry someone who isn't strictly better than all the previous ones. This happens $1$-out-of$n$ times. (A related problem arises for the first two, etc.) $\endgroup$ – David G. Stork Dec 21 '18 at 21:23
  • $\begingroup$ @DavidG.Stork I don't follow your reasoning. The first candidate is strictly better than all previous candidates (since there are no previous candidates), so it's OK to marry them (gives you chance $1/n$ of winning, but still better than $0$). On the other hand, it's not OK to marry someone who's worse than a previous candidate. Then your chances of winning are $0$. $\endgroup$ – 6005 Dec 26 '18 at 22:03
2
$\begingroup$

The decision to marry or not need only be made when the current result is better than all previous results (otherwise the current choice is definitely suboptimal). The choice, at point $K$ to marry or not (provided the $K$th date is better than all before) does not depend on the previous dates in anay ways (aprt from them being worse than the $K$th) because all relatiev orders are equally likely. Therefore, any optimal strategy must consist of probabilities $p_k$ for $1\le k\le N$ such that when the $k$th date is better than all before, we marry (and stop) with probability $p_k$ and continue otherwise. Let $q_k$ be the probability of picking the best provided we picked none of the first $k$. Then the probability of picking the best provided we picked none of the first $k-1$ is $$ q_{k-1}=\frac{\frac1Np_k+\frac{N-k}{N}\frac1k(1-p_k)q_k+\frac{N-k}{N}(1-\frac1k)q_k}{P(\text{none of the first $k-1$ selected})}=\alpha_kp_k+\beta_k$$ ($k$th is best and we pick, or best is after $k$ and $k$ is best of first and we don't pick it, or best is after $k$ and $k$ is not best of first) and hence is clearly maximized at $p_k=0$ ($\alpha<0$) or $p_k=1$ ($\alpha>0$) or in a rare possibility $p_k$ does not matter at all ($\alpha=0$) and can wlog. be selected to be $0$ or $1$.

You can make yourself clear that haveing $p_k=1$ and $p_{k+1}=0$ cannot be optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.