Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  sos440 Mar 18 '12 at 13:12
3  
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
1  
@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
show 2 more comments

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
1  
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
show 2 more comments

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.