2

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.

Community
  • 1
Lincoln
  • 35

1 Answers1

1

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

Henry
  • 157,058
  • Does that mean that the solution would be γ + log m, for one of the piles, and 1 subtracted by the previous pile answer for the other? – Lincoln Jan 02 '14 at 15:26
  • How do you come up with the probability of 1/i for the ith card picked? wouldn't it be m - (value of largest card picked) / m-i ? My idea comes from the reasoning, say m is 50, picking up the 4th card, and the largest card picked up to now is 40. The probability of picking a larger card than 40 is 10/46 - being 50-40/50-4 ? – Lincoln Jan 02 '14 at 16:57
  • @grixtil: on your first comment, there is a difference between the expected size of a pile and the distribution of its possible sizes. On your second, the problem becomes much more complicated if you use the value of the largest card, and I have ignored it, as the calculations are simpler without it: any of the first $i$ cards can be the largest of the first $i$, with equal probability, so the probability that it is the $i$th which is largest is $\frac1i$. – Henry Jan 02 '14 at 20:52
  • I've updated the question with the full original question submitted to me, and my reasoning for it – Lincoln Jan 03 '14 at 14:35