# Choosing my most preferred card from a set of n cards.

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.
• This is known as the Secretary Problem – lulu Feb 11 at 19:14
• 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 – JoseSquare Feb 11 at 19:23
• @lulu could you explain the math under the 'Deriving the optimal policy' section – johanso Feb 11 at 19:27
• 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. – lulu Feb 11 at 19:30
• 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. – lulu Feb 11 at 19:33