Average number of rolls until a number repeats

Question

Assume you have a fair three sided die. Now roll the die, until a number repeats. What is the average number of rolls?

I know that the average is just the sum of all the numbers divided by the number of items in the set.

Assuming that we first roll a 1, I got:

(1,2)(1,3)(1,1)

(1,2,1)(1,3,1)(1,2,3)(1,3,2)(1,2,2)(1,3,3)

(1,2,3,1)(1,2,3,2)(1,2,3,3)(1,3,2,1)(1,3,2,2)(1,3,2,3)

Which is a total of 15 which I should multiply by 3 to get a total of 30 different combinations. Now to find the average what should we divide 30 by? Can anyone point me into the right direction?

Answer 1

We can break into cases and calculate the probability of each event.

The probability that our first repeated number occurs on the second roll is $\frac{1}{3}$, seen by the fact that the first roll can be anything and the second roll must match the first.

The probability that our first repeated number occurs on the third roll is $\frac{2}{3}\times\frac{2}{3}$, seen by the fact that the first roll can be anything, the second roll must be something that doesn't match the first roll (2 options out of 3 equally likely), and then the third roll must match either of the first two rolls (2 options out of 3 equally likely).

The probability that our first repeated number occurs on the fourth roll is $\frac{2}{3}\times\frac{1}{3}\times 1$, seen by the fact that the first roll can be anything, the second roll must be something that doesn't match the first roll, the third roll must be something which doesn't match either of the first two rolls, and the fourth roll can be anything.

Finally, we notice that it is impossible for there not to have been a match by the fourth roll by pigeonhole principle.

Now, it is just a matter of computing the expected value by adding these results after multiplying each by their respective number of dice rolls required to achieve them.

The final total is:

$$\frac{1}{3}\times 2 + \frac{2}{3}\times\frac{2}{3}\times 3 + \frac{2}{3}\times\frac{1}{3}\times 4 = \frac{26}{9}\approx 2.8888\dots$$

Answer 2

You want the number of rolls divided by the number of 'sets of rolls' to get the average length.

So count up all the rolls and divide by 15. You'll be multiplying by 3 on top and bottom anyway so it won't matter.

So should be $15/48$. EDIT: $48/15$ (division was wrong way)

Answer 3

Let $X$ denote the random variable of how many rolls before some number repeats. What you should really be doing is using your table to calculate the probability of each value of $X$.

So, let $Y_1$ be the event that the first roll is 1 - then as you observed, $X$ is independent of $Y_1$, so $E(X) = E(X|Y_1)$. Now, from your table: $$p(X=1|Y_1) = 0; \\ p(X=2|Y_1) = \frac{1}{3}; \\ p(X=3|Y_1) = \frac{4}{9}; \\ p(X=4|Y_1) = \frac{6}{27} = \frac{2}{9}.$$ And by the pigeonhole principle, you know that $X \le 4$ in every case. From this, you should be able to go on and calculate $E(X|Y_1)$.

As an alternate approach, if you want to use the method of evaluating $X$ on elements of a table and taking the average, you absolutely need the sample space to consist of equal probability events. For example, from the observation that the result of $X$ is always determined by the fourth roll, you could list out the set of all possible first four rolls (though this is a synthetic solution, as in reality you would stop once some roll repeated instead of going on to all four rolls - you just then need to observe that the distribution will be the same one way or the other). Then, for each possibility, calculate the value of $X$ and then take the average.