1
$\begingroup$

I have $n$ cards, however, I like only 1 card the most out of all the $n$ cards and that card is my favourite. I consider the cards one by one, giving each an integer score, where the higher the score means the more I like that card. There are no ties in scores. The game is such that once I am done considering the $k^{th}$ card I lose the opportunity to select it as my favourite card forever. Suppose the candidates are considered in random order, chosen uniformly at random from all $n!$ possible orderings.

Current plan: consider the first $m$ cards, find the max score among them and then discard them. After the $m^{th}$ card, choose the first card who receives a higher score than the maximum from $m$ cards to be the favourite.

Let $E$ be the event that I choose my most preferred card as my favourite. Let $E_i$ be the event that the $i^{th}$ card is the most preferred and i choose it as my favourite. Find Pr[$E_i$] and show that Pr[$E_i$] = $\frac{m}{n} \sum_{j=m+1}^{n}\frac{1}{j-1}$

I have no idea how to begin solving this sum. Any intuition would be nice.

$\endgroup$
  • 4
    $\begingroup$ This is known as the Secretary Problem $\endgroup$ – lulu Feb 11 at 19:14
  • $\begingroup$ That series is the harmonic series $\sum \frac{1}{k}$ starting on $k=m$ and finishing in $k=n-1$. I don´t know if this will help you $\endgroup$ – JoseSquare Feb 11 at 19:23
  • $\begingroup$ @lulu could you explain the math under the 'Deriving the optimal policy' section $\endgroup$ – johanso Feb 11 at 19:27
  • $\begingroup$ It's pretty literal. The strategy is "Look passively at the first $r-1$ applicants. Then, after that, pick the first one that is better that all the ones you saw. " In order for this to work you need the best applicant to come after the first $r-1$ and, moreover, the best applicant must come first amongst all the applicants after the first $r-1$ which are better than all the first $r-1$. The article simply writes all this out carefully. $\endgroup$ – lulu Feb 11 at 19:30
  • $\begingroup$ For instance: if the second best is amongst the first $r-1$ but the best is not, then this strategy works perfectly. If the third best is amongst the first $r-1$ but neither the best nor the second best is, then the strategy works with probability $\frac 12$. And so on. $\endgroup$ – lulu Feb 11 at 19:33

Your Answer

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

Browse other questions tagged or ask your own question.