2
$\begingroup$

I have a box of stickers. It contains $n$ stickers. Each sticker is labelled with a different number from $\mathbb{Z}$.

I have infinite supply of boxes.

Box labelling game: I pick a random sticker and stick it on the box that has largest label smaller than current sticker. If all the currently labelled boxes have label bigger than the current sticker then I just pick a new box and stick the label on it.

Example, Stickers : [3, 1, 2, 5, 7, 6, 8]

Game steps: 1. Box0 -> 3 2. Box0 -> 3, Box1 -> 1 3. Box0 -> 3, Box1 -> 2 4. Box0 -> 5, Box1 -> 2 5. Box0 -> 7, Box1 -> 2 6. Box0 -> 7, Box1 -> 6 7. Box0 -> 8, Box1 -> 6

In this example I ended up using 2 boxes. What is expected number of boxes I will end up labelling?

In this example Box0 got 4 labels, Box1 got 3 labels. What is the distribution of labels on the boxes?

Plot of distribution form experiment (looks like moustache):

enter image description here

$\endgroup$
  • 2
    $\begingroup$ This is exactly the algorithm of longest increasing subsequence (decreasing in this case). Try keywords like "longest increasing subsequence" and "random permutation". The expected length (number of boxes) is asymptotically $2\sqrt{n}$. I know nothing about your second question though. The expected number of labels of box 0 is $\frac{s(n+1,2)}{n!}$ where $s$ is the Stirling number of the first kind, but the others seem harder. $\endgroup$ – aaaaajack Dec 29 '16 at 7:33
  • 1
    $\begingroup$ @aaaaajack Make into an answer? $\endgroup$ – Yuval Filmus Dec 29 '16 at 11:25
  • $\begingroup$ @YuvalFilmus I'm gonna think about the second question more and I'll do when I give up. $\endgroup$ – aaaaajack Dec 29 '16 at 12:41
  • $\begingroup$ @aaaaajack I have added a plot that might help with answering the 2nd part. $\endgroup$ – Pratik Deoghare Dec 29 '16 at 16:00
  • $\begingroup$ @PratikDeoghare Can you explain more about your plot? $\endgroup$ – aaaaajack Dec 29 '16 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.