Probability of picked cards to be smaller than the largest picked card

I have an assignment for my algorithms module that requires us, amongst other things, to find the equations for the following question.

Edit – Question Updated

You have n cards with pairwise different integer values from 1 to n , shuffled randomly on a pile. You pick cards from the pile, one after another, and depending on the card’s value you put it either on the right hand side or on the left hand side; more precisely: if the card has smaller value than all cards previously picked from the pile, then you put it on the right hand side, otherwise you put it to the left.

  1. Formulas for expected number of cards on the right hand side and the left hand side when all cards have been picked up.

  2. Solving the formulas with as much accuracy as possible

  3. What is the probability that on the right hand side there are at least log log n cards at the end of the process? Use some classic inequalities, e.g. Markov Inequality.

My idea is that the number of cards on the left hand side would be $\sum\limits_{i = 1}^n {\frac{{n – m}}{{n – i}}}$ and those on the right hand side would be n – left hand side. Am not sure if my reasoning is right here though. m being the largest card picked from the pile.

Solutions Collecting From Web of "Probability of picked cards to be smaller than the largest picked card"

Hints:

  • I suspect we can ignore $m$

  • The probability that the $i$ card picked is greater than all of the previous $i-1$ cards is $\dfrac1i$.

  • The event of putting the $i$th card in the “largest so far” pile is independent of the event of putting the $j$th card in the “largest so far” pile if $i\not =
    j$

Added: You could then show that the expected number of cards in the “largest so far” pile is the harmonic number $H(n)$. You might go further and show that the probability of the number of cards in the “largest so far” pile is essentially a Stirling number of the first kind divided by a factorial