Puzzle time - rolling a die

[jon-nyc]

On average, how many times do you need to roll a die before all six different numbers have turned up?

No brute force coding solutions Klaus. Use your brain.

[Aqua Letifer]

@jon-nyc said in Puzzle time - rolling a die:

On average,

So, am I to take that literally? Greater than 50% of the time?

[jon-nyc]

Yes.

In theory you could do it in 6 rolls or any number higher.

But what’s the average?

[Horace]

((Rolls for kids from Lake Wobegon) + (Rolls for kids from Chicago)) / 2

[Klaus]

:::

If p(n,k) is the probability to get exactly k different numbers with n rolls, then

p(1,1) = 1
p(1,k) = 0 for k != 1
p(n,k) = p(n-1,k)*k/6 + p(n-1,k-1)*(6-k+1)/6 all other cases

If you plug in the numbers, you get p(12,6) = 0.438 and p(13,6) = 0.5138, hence 13.

I assume there's a closed form of the recurrences, but I can't be bothered to calculate them right now.
:::
(edited)

[LuFins Dad]

What type of die? Dodecahedron? Icosahedron? Are there racial modifiers?

[jon-nyc]

Klaus - You’re on the right track but not quite there.

Might be easier to compute the expected values of the number of rolls needed for each k and add them.

[Klaus]

Hm, I've written a one-liner to generate some random numbers, and I see that my model doesn't give the correct answer, but I don't quite understand why. The last line can be read as

"to get k different numbers with n rolls, you either already got k different numbers with n-1 rolls and got another number that you already saw, or you got k-1 different numbers with n-1 rolls and this time got a number different from the ones you already had."

Still looks reasonable to me. Isn't it annoying when you have a nice model but it doesn't fit to reality? I've always been of the opinion that if the model is really beautiful, reality should be changed to fit the model and not vice versa!

[Klaus]

:::

Stumbled upon the "coupon collector's problem", which seems to be applicable here and according to which the expected value for this problem should simply be 6 * (1 + 1/2 + 1/3 + ... + 1/6) which is around 14.7 - which also agrees with my simulation.

Hmm...

I still think reality should bend to model.

:::

[jon-nyc]

:::

That's correct. But you were on the right track with your logic, I'm not sure where it went wrong.

Let's do this in terms of expected values.

Let E(k) be the expected number of rolls to get k unique numbers after you've gotten k-1 unique numbers.

Clearly E(1) = 1.

As you point out, the probability of getting a unique number on the next roll is 5/6. So the expected number of rolls is 6/5. E(2) = 6/5

By the same logic E(3) = 6/4, E(4) = 6/3, E(5) = 6/2, and E(6) = 6/1

Add them up and you get 147/10. So 15 rolls.

:::

[Klaus]

@jon-nyc said in Puzzle time - rolling a die:

But you were on the right track with your logic, I'm not sure where it went wrong.

I thought about this again.

My model computes a subtly different probability. p(13,6) = 0.5138 means that if I roll the dice 13 times, then in 51.38% of the cases I'll hit all 6 numbers. If I do this only 12 times, then in 43.8%. I verified this with a simulation and it is indeed true.

But that's different from "how many times do you need to roll a die before all six different numbers have turned up?". That's an expected value that averages over any number of rolls: Sometimes I need just 6 rolls, and if I'm unlucky I may need 500.

So I have answered a related but different question that would have been a nice follow-up puzzle