Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Caution: I'm not a mathematician, but I remember some of what I learned in college.

I was reading about the Secretary Problem on Wikipedia, essentially about determining the optimal moment to stop evaluating new options. I'm interested in the variation where there is an unknown number of applicants, which they say can be solved with the $\frac{1}{e}$ law of best choice.

Wikipedia gives a simple formula for the time distribution function, where $f$ is the frequency of applicants, and $T$ is the maximum time you can wait.

$$F(t) = \int_{0}^{t} f(s)ds \ \ , \ \ 0\le t\le T$$

If I understand correctly, the article then asserts that the correct thing to do is to wait until $F(t) = \frac{1}{e}$.

I am puzzled at what this would mean in the real world. I'm interpreting the definite integral to mean the cumulative number of candidates. But it can't be asking us to wait until half a candidate shows up. Or is it saying to discard the first candidate, and take the next one that's as good? Or do I have this completely wrong and it's saying to wait until the density of candidates is $\frac{1}{e}$? If so that is unintuitive.

The Wikipedia article is unclear (to me, anyway) and I haven't found a better reference.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Suppose that all applicants have independently of each other the same arrival time density $f$ on $[0,T]$ and let $F$ denote the corresponding arrival time distribution function $$ F(t) = \int_0^t f(s) \, ds, \, 0 \leq t \leq T. $$

The author is stretching the analogy somewhat to give intuition for the integral of the probability density function. In this model, you might tell the applicants to email their resumes from midnight this morning to midnight tonight. Suppose the resumes arrive randomly according to the probability density function $f(s)$. Let $\tau$ be the time such that $F(\tau) = \frac{1}{e}$. In other words, a $\frac{1}{e}$ fraction of the area under the probability density function has been witnessed, which should roughly correspond to having seen a $\frac{1}{e}$ fraction of the applicants. (In practice, you could be so unlucky that all applicants randomly choose to arrive just before midnight tonight, but this is highly unlikely.) The strategy recommends that you dismiss all applicants who emailed before time $\tau$ and hire the first applicant after that who is better than all the previously dismissed ones.

In short, your goal is to reject the first $\frac{1}{e}$ fraction of applicants and hire the next applicant who is better than all the previously dismissed ones. If you happen to know there will be exactly $N$ applicants, then you can dismiss the first $\frac{N}{e}$ of them. If you do not know how many applicants will apply, then you must make some judgement about the distribution of the application times and choose the time when you expect a $\frac{1}{e}$ fraction have already applied.

share|improve this answer
    
Thanks for explaining that. On the other hand this seems like an extremely convoluted way of restating the problem. Of course if I know the average frequency of applicants, I know the total I'm going to get by time $T$, thereby reducing to the simpler problem where $N$ is known. In the real world, distributions of events are messier, and often never settle down to any average frequency. –  neilk Jun 21 at 22:58

In the discrete form of the Secretary Problem you consider sampling $k$ out of $n$ applicants before you make a selection. Then the optimal sample size is $1/e$ times $n$ only in the limit as $n \rightarrow \infty$ with $k/n$ held constant. In this case, the probability of making the best selection is also $1/e$.

For a finite population the optimal sampling fraction will depend on $n$, but $1/e$ should be a close approximation.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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