God doesn't roll dice!

Math Problem #2

Problem

Consider a game where you have a standard dice with numbers from 1 to 6 and also consider the usual activity of rolling such a dice. Eventually, you will roll a number that has already appeared before in the sequence. For example, if I roll the dice and get the sequence 4, 5, 1, 6, 1 then I repeated the number 1 on the 5th roll of the dice.

So the question here is how many rolls would it take for you to roll a repeat?. For those of you who are familiar with probability and statistics, the question would be better stated as to “What is the number of expected rolls till the dice repeats one of the numbers?”

---

What is ‘Expected Value’?

Mathematically it’s defined the ‘weighted average value of a random variable over a large number of independent experiments’. A random variable, in turn, is a variable that maps numbers to possible outcomes in an experiment. Confused?

Let’s consider a simple experiment - tossing a fair coin. The outcomes are either Head or Tail, each with an equal probability of 0.5

Let’s have a random variable X that is equal to 0 when we toss head, and 1 when we toss a tail. Hence for this random variable, the expected value, or E(X) is nothing but 0*0.5 + 1*0.5 = 0.5

Consider the example of dice, and take the random variable X as the number appearing on the top of the dice after a roll. This number can be anywhere between 1 and 6, including them, and each number has an equal probability of 1/6 on appearing on top of the dice.

Hence in this case,

E(X) = 1*(1/6) + 2*(1/6) + 3*(1/6) + 4*(1/6) + 5*(1/6) + 6*(1/6) = 21/6 = 3.5

---

Solution

Well if you’re extremely lucky (or if you have been playing some board games this quarantine), you might observe the repetition in the second roll itself, for example, you might get [6,6] in the first two trials. But the problem is a more general question, as in what are the expected number of rolls before you may repeat a number. 

As we saw here, it can happen in 2 rolls at a minimum. Is there an upper bound on this one as well? Yes! As we can say the 7th roll would be a repeated number. Even when you get all different numbers in the first 6 rolls, you would definitely get repetition in the 7th roll. Thus, the 7th roll will always be a repetition, but there is a possibility that it’s not the first one. Of course, we can get repetition in rolls < 7 just that now our answer is bound within 2 and 7

Let’s backtrack our way up to the solution, and let’s also consider E(x) as the ‘expected number of rolls required to observe a repetition after we have seen x numbers before’. Hence our initial question would require us to calculate E(0) as we need to calculate the number of rolls required to get repetition, even before we have rolled any dice.

For this logic, we would have E(6) = 1 as when we have seen 6 numbers already, a single roll would bring us a number that has already appeared in the sequence before.

Now coming on to E(5) we see that

E(5) = (5/6)*1 + (1/6)*(1+E(6))

This means that we have a 5/6 chance of rolling a number that is equal to the five numbers occurred before and would not need another roll and we have a 1/6 chance of rolling a sixth number, after which we would need the expected number of rolls required to observe a repetition, given we have seen 6 numbers, which is already shown before as E(6) = 1

Therefore,

E(5) = (5+2)/6 = 7/6

Looking at E(4), we see that there is a 4/6 chance of rolling a number we have seen before and 2/6 chance of rolling one that we haven’t

Hence,

E(4) = (4/6)*1 + (2/6)*(1+ E(5)) 

E(4) = 4/6 + 26/36 = 50/36 = 25/18

We see a recurring pattern that is -

E(x) = (x/6)*1 + {(6-x)/6}*(1+E(x-1))

Using this, we calculate

E(3) = (3/6) + (3/6)*(1+E(4)) = 61/36

E(2) = (2/6) + (4/6)*(1+E(3)) = 115/54

E(1) = (1/6) + (5/6)*(1+E(2)) = 899/324

And finally,

E(0) = (1+E(1)) = 1223/324 = 3.77

Hence, when we start out with nothing, or when we haven’t seen any number before, the expected number of dice rolls that would be required to get a repetition is 3.77.

---

I hope you liked this week’s newsletter. In case you have any comments feel free to post them, we’ll be glad to connect. Share the post with your friends!