Tweeted twitter.com/StackCompSci/status/814760083515179013
2 added plot
source | link

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

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?

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

1
source | link

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?