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.
- Combinatorics: Number of possible 10-card hands from superdeck (10 times 52 cards)
- Bulgarian Solitaire: Size of root loops
- Game Theory Matching a Deck of Cards
- In the card game “Projective Set”: Compute the probability that $n$ cards contain a set
- I don't understand why this card trick works
- In the card game Set, what's the probability of a Set existing in n cards?
Formulas for expected number of cards on the right hand side and the left hand side when all cards have been picked up.
Solving the formulas with as much accuracy as possible
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.
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