On Tue, Jun 17, 2014 at 10:00 PM, Charles Greathouse <charles.greathouse@case.edu> wrote:
That leads to a very different strategy, since the difference between best and second-best (say) is very small when N is large. So the optimal strategy in the "best is 1, others are 0" fails miserably here -- expectation n/e + (1 - 1/e) * n/2 = n(1/2 + 1/2e) = 0.6839...n, while you can get arbitrarily close to n with the strategy "only pick someone guaranteed to be in the top (say) 99%".
I agree that the strategy that maximizes the expected rank of the choice is different from the strategy that maximizes the chance that this rank is 1. For example, if you're maximizing expected rank, and the next-to-last candidate has rank n-2 of the n-1 you've seen so far, it's clearly better to take that than the next one. But I don't understand your proof that there are strategies that make the expected rank arbitrarily close to n. Choosing the first candidate that's guaranteed to be in the top 99% seems wrong; how can you get an expected rank of n setting your sights so low? Did you mean guaranteed to be in the top 1%? I guess that works for n sufficiently large; the chance that you won't see anyone in the top 1% in that last 1% is vanishingly small when n is sufficiently large. But while this shows that the expected rank approaches n as n approaches infinity, it doesn't give the correct strategy for any finite n. What is the right strategy to maximize expected rank for a given n? Andy
On Tue, Jun 17, 2014 at 9:40 PM, <rcs@xmission.com> wrote:
I'd always assumed that the scoring scheme was 1 point for choosing the worst, and N for choosing the best, and so on for intermediate ranks.
Rich
----
Quoting Bernie Cosell <bernie@fantasyfarm.com>:
On 17 Jun 2014 at 17:31, Tom Rokicki wrote:
Well, clearly it's a suboptimal strategy in the following way.
I assume when you say "it" you mean the "standard assumed optimal strategy"?
If after seeing N-2 candidates, I still haven't seen one better
than the K'th, I know I only have two left. If the next one is above the median seen so far, I'm probably certainly doing better to pick that one and pass on the last, than to wait for the last.
I can't quickly do the math to see if that has a better expected outcome than the 'standard strategy'....
... And of course a similar argument applies for
N-3, and so on.
But if that's the case, then you have the old paradox of "I'm going to give you an exam next week and it'll be a surprise". But perhaps not. Is this what you were thinking:
"examine the first K candidates. Take the first candidate that is larger than the *median* of those first K" [rather than wait for one that's larger than any of the first K]. I haven't a clue if replacing "larger than any" with "larger than the median" makes for a better or worse strategy. Or if there's a combined strategy. [look at the first K. Then if you hit one larger among the next L, take it [obviously with K+L<N], but if not THEN you take the first one larger than the median of the ones you've seen so far.
This seems to confirm my unease that the usual "assumption" [examine K and take the next that beats any of the K] probably needs to be proven to be an optimal strategy before you go and solve for K.
/Bernie\
-- Bernie Cosell Fantasy Farm Fibers mailto:bernie@fantasyfarm.com Pearisburg, VA --> Too many people, too few sheep <--
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com