Gabeland

Suppose you have a fair 6 sided die, and you’re rolling it repeatedly. On average, how many rolls will it take to get a 1?

The answer is 6. And I mean, that makes sense, right? There’s a 1/6 chance you roll a 1 each time, so it should happen about 1 in every 6 times.

Still not convinced? Well, let’s define X to be the average number of rolls it takes to get a 1.
After you do your first roll, there’s two relevant options: Either you rolled a 1, or you didn’t. If you did get a 1, then the average number of rolls to get 1 from this state is 0, because you already did. Otherwise, if you didn’t get 1, you’re right back where you started. Each roll is independent, so the average number of rolls from this state is X.

Let’s turn that into an equation:
X = 0*1/6 + X*5/6 + 1.
The extra +1 at the end is because after your first roll, you will have done 1 extra roll. Crazy, isn’t it?

Now we can solve that equation.
X = 5X/6 + 1
X/6 = 1
X = 6
And there it is! The answer is in fact 6. In general, for any event that has probability p of occurring each step, it takes an average of 1/p steps to occur.

If you were convinced initially, then that may have seemed pointless to you. But that method will help out later.

And by later, I mean right now, because here’s another problem: How long will it take for you to have rolled each number from 1 to 6 at least once?

Well, on average, it takes 6 rolls to get a 1, and 6 rolls to get a 2, and 6 rolls to get a 3, and so on. So after 6 rolls, you’ll probably have gotten each number, right? Except 6 is the minimum number of rolls it can take, so it’s probably not also the average.

On the flip side, if you have to get all of them, you could just chain them together to get 36. But that’s also not right, since while looking for, say, 3, you could get a 5 and then you don’t have to look for it. How do you quantify that interaction?

Let’s call A the average number of rolls it takes to get all of them. We’ll keep track of them based on how many unique numbers we’ve gotten so far. So B is the average starting from having 1 unique, C is the average starting from 2 unique, and so on. If you don’t understand, it should make sense once I use them.

On the first roll, you’re guaranteed to get a number you haven’t gotten yet.
A = B + 1

If you’ve gotten 1 number so far, there’s a 5/6 chance you’ll get a new one from the next roll. So on average, the number of rolls it will take is 6/5.
B = B/6 + 5C/6 + 1
5B/6 = 5C/6 + 1
B = C + 6/5

If you’ve gotten 2 numbers, there’s a 4/6 chance you get a new one. So the average number of rolls it will take is 6/4. (Intentionally not reducing the fractions)
C = 2C/6 + 4D/6 + 1
4C/6 = 4D/6 + 1
C = D + 6/4

If you’ve gotten 3 numbers, there’s a 3/6 chance you get a new one. See the pattern yet?
D = E + 6/3
E = F + 6/2
F = G + 6
And G is the time it will take to get all 6, if you already have all 6. Which would be 0.
F = 0 + 6 = 6
E = 6 + 6/2 = 9
D = 9 + 6/3 = 11
C = 11 + 6/4 = 25/2
B = 25/2 + 6/5 = 137/10
A = 137/10 + 1 = 147/10 = 14.7
There you have it! The average number of rolls it takes to get all 6 numbers at least once is 14.7.