# What is the expected number of dice one needs to roll to get 1,2,3,4,5,6 in order?

If I have a fair die and throw it until I get a run of 1,2,3,4,5,6 in order, how many times on average must I throw the dice?

-
Considering the corresponding transition matrix, we obtain that the average trial you need to get a run of 1, 2, 3, 4, 5, 6 is 46656. – Sangchul Lee Mar 18 '12 at 13:12
There are $6^6 = 46656$ permutations of the results. The run you want to obtain is unique, so it has the probability $\frac{1}{46656}$. Therefore, the expected number of times you have to throw the dice is $46656$. – rubik Mar 18 '12 at 13:24
@rubik: It doesn't work like that. You could also get a run of $1,2,3,4,5,6$ starting at the second dice roll. After $N$ throws you have $N - 5$ runs of length $6$, and you want one of them to be this specific one. – TMM Mar 18 '12 at 13:33
@rubik, the probability should be greater than 1/46656, since dice is thrown continuously. – quartz Mar 18 '12 at 13:35
@rubik: If you were looking for 1,1,1,1,1,1 then you would get a different (larger) answer. – Henry Mar 18 '12 at 13:37

Let's write

• $a =$ expected throws to succeed with no useful throws recently
• $b =$ expected throws to succeed with 1 recently
• $c =$ expected throws to succeed with 1,2 recently
• $d =$ expected throws to succeed with 1,2,3 recently
• $e =$ expected throws to succeed with 1,2,3,4 recently
• $f =$ expected throws to succeed with 1,2,3,4,5 recently
• $g =$ expected throws to succeed with 1,2,3,4,5,6 recently

then

• $g = 0$
• $f = 1 + \frac16 g + \frac16 b + \frac46 a$
• $e = 1 + \frac16 f + \frac16 b + \frac46 a$
• $d = 1 + \frac16 e + \frac16 b + \frac46 a$
• $c = 1 + \frac16 d + \frac16 b + \frac46 a$
• $b = 1 + \frac16 c + \frac16 b + \frac46 a$
• $a = 1 + \frac16 b + \frac56 a$

so

• $a = 6 + b$
• $\frac16 b + \frac46 a = 4 + \frac56 b$
• $b = 30 + c$
• $\frac16 b + \frac46 a = 29 + \frac56 c$
• $c = 180 + d$
• $\frac16 b + \frac46 a = 179 + \frac56 d$
• $d = 1080 + e$
• $\frac16 b + \frac46 a = 1079 + \frac56 e$
• $e = 6480 + f$
• $\frac16 b + \frac46 a = 6479 + \frac56 f$
• $f = 38880 + g$

i.e.

• $a = 6 + 30 + 180 + 1080 + 6480 + 38880 + 0 = 46656$

So the answer is $46656$.

This is $6^6$ so the "obvious solution" turns out to be correct and there is probably a quicker way.

-
why $f = 1 + \frac16 g + \frac16 b + \frac46 a$ ? – quartz Mar 18 '12 at 14:07
Could you explain explicitly where the formulae for a-g come from? – j coe Mar 18 '12 at 14:58
@quartz: If you are at a position ending 12345 then you must throw the die, hence the $1$. You have a $\frac16$ chance of a 6 so you add a sixth of $g$, a $\frac16$ chance of a 1 so you add a sixth of $b$,and a $\frac46$ chance of a 2,3,4 or 5 so you add a sixth of $a$. Hence the equation. – Henry Mar 18 '12 at 15:26
@j coe: See my response to @quartz. The others are similar. For $g$, you have finished so $g=0$. – Henry Mar 18 '12 at 15:28
Note that for this argument to work, we need to already know that the expectations involved are all finite. – Chris Eagle Mar 18 '12 at 16:50

For each $k\geqslant6$, call $x_k$ the six last positions occupied at time $k$. Introduce $t_0=0$ and, for each $n\geqslant1$, $t_n$ the $n$th time when the word 123456 got completed, that is, $t_n$ denotes the $n$th visit to 123456 of the process $(x_k)_{k\geqslant6}$. The question asks for $\mathrm E(t_1)$.

Note that the sequence $(t_{n+1}-t_{n})_{n\geqslant0}$ is i.i.d. and distributed like $t_1$. This step uses the fact that after a completion of 123456 one must start to build a new occurrence entirely anew, that is, that no nontrivial suffix of 123456 is also a prefix of 123456. (Otherwise, $(t_{n+1}-t_{n})_{n\geqslant1}$ would be i.i.d. but with a different distribution than $t_1$, more precisely, the distribution of $t_{n+1}-t_n$ for every $n\geqslant1$ would be strictly dominated by the distribution of $t_1$, in particular, for every $n\geqslant1$, one would have $\mathrm E(t_1)\gt\mathrm E(t_{n+1}-t_n)$. In the present case, $\mathrm E(t_1)=\mathrm E(t_{n+1}-t_n)$.)

The process $(x_k)_k$ performs a random walk on the regular directed graph with $N=6^6$ vertices where every vertex 1u is linked to the six vertices u1, u2, ..., to u6, for every given 5-letters word u. The out-degree and the in-degree of every vertex being all equal to 6, the stationary distribution of the Markov chain is uniform, in particular the weight of 123456 is $w=1/N$.

By the law of large numbers for ergodic Markov chains, the asymptotic proportion of time spent at 123456 is almost surely $w$, that is, $t_n=(n/w)+o(n)$ almost surely. By the law of large numbers for i.i.d. sequences, $t_n=n\mathrm E(t_1)+o(n)$ almost surely.

Comparing these two expressions, one gets $\mathrm E(t_1)=1/w=N=6^6=46656$.

-