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.

New contributor
johanso is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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

johanso is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.