So here's one possible algorithm for the problem I'll call the "harmonic strategy." (There are N candidates in all, you see them in random order, and have to make a decision to hire one immediately after you see them, or they are gone forever. Incidentally, there is a wikipedia article on "Secretary Problem" and it says it was originally called "fiancee problem."). HARMONIC STRATEGY: Let C be a suitable constant 0<C<1. For k=1,2,3,... If less than C*N/k candidates remain unexamined, and the last one you saw had rank<=k among all those so far seen ("rank" counting 1,2,... from the best), then hire. For brevity let f(k) = 1/k - 1/(k+1) = 1/((k+1)*k). It seems to me that the expected rank R of the one you hire with this strategy (among all N candidates) will obey R = order 1 with probability P[1] of order 1, order k (1<k<N) with probability P[k] of order (1 - (1-k/N)^(f(k)*N)) * (1-P[k-1]), (1+N)/2 with whatever probability is left over. If we note that for large N that (1-k/N)^(f(k)*N) = exp(-k*f(k)) = exp(-1/(k+1)) = 1-1/(k+1) approximately, then we see the the probability that R=order k, is about 1/(k+1) fraction of whatever probability is left over from all the preceding k. Since SUM 1/k = infinity (harmonic series diverges) logarithmically we see PRODUCT (1-1/k) = 0 ("harmonic product") in fact it telescopes so the exact value of Product[ 1-1/k from k=2..N ] = 1/N, indicating that the "leftover probability" should become of order 1/N at most, for large N. That is good because it means the final term contributes at most O(1) to the expectation value of R. Now in fact you can see that every time k doubles the (1-P[k-1]) approximately halves, which means P[k] behaves like 1/k^2 for large k. Hence performing the sum to find the expectation value of R we conclude: CLAIM: Expect(R) = O(logN). So this has been an admittedly sketchy proof that Expect(R) = O(logN) is assured by the harmonic strategy. I conjecture the harmonic strategy is optimal to within a constant factor, i.e. that no matter what strategy is employed, Expect(R) will always be at least of order logN. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)