# Box labelling game

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):

• 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. – aaaaajack Dec 29 '16 at 7:33
• @aaaaajack Make into an answer? – Yuval Filmus Dec 29 '16 at 11:25
• @YuvalFilmus I'm gonna think about the second question more and I'll do when I give up. – aaaaajack Dec 29 '16 at 12:41
• @aaaaajack I have added a plot that might help with answering the 2nd part. – Pratik Deoghare Dec 29 '16 at 16:00
• @PratikDeoghare Can you explain more about your plot? – aaaaajack Dec 29 '16 at 17:16