If I roll the dice 50 times, how do I calculate the chance that I will roll 6 at least 5 times in a row?
Why this problem is hard
- With 5 tries this would be easy: take $(1/6)$ to fifth power.
- With 6 tries this is manageable; take the probability of rolling 6 the first five times, add the probability of rolling 6 the last five times, then subtract the overlap (all six results are 6).
- Given two overlapping sets of 5 rolls, the probability that one is all 6's is not independent from the probability that the other is all 6's.
- In principle this could be continued, but inclusion-exclusion gets out of hand. There has to be a better way; what is it?
Best Answer
This is equivalent to counting the number of strings with length $50$ over the alphabet $\Sigma=\{1,2,3,4,5,6\}$ that avoid $66666$ as a substring of five consecutive characters. Let $S_n$ be the set of such strings with length $n$ and $L_n=|S_n|$. The prefix of an element in $S_n$ can be only: $$ x,\quad 6x,\quad 66x,\quad 666x,\quad 6666x$$ where $x$ differs from $6$. This gives the recursive formula: $$ L_n = 5(L_{n-1}+L_{n-2}+L_{n-3}+L_{n-4}+L_{n-5})\tag{1}$$ with the initial conditions: $$ L_0=1,\quad L_1=6,\quad L_2=36,\quad L_3=216,\quad L_4=1296,\quad L_5=7775.\tag{2}$$ So we have that: $$ L_n = A_1\sigma_{1}^n + A_2\sigma_2^n + A_3\sigma_3^n+A_4\sigma_4^n + A_5\sigma_5^n \tag{3}$$ where $\sigma_i$ is a root of the characteristic polynomial $f(x)=x^5-5(x^4+x^3+x^2+x+1)$ and the $A_i$s are constants given by the initial conditions. $f(x)$ has only one real root, very close to $6$, namely: $$\sigma_1 = 5.999356651043833111223\ldots $$ and all the other roots satisfy $|\sigma_i|<1$, hence our probability is close to: $$1-\left(\frac{\sigma_1}{6}\right)^{50}=0.0053471814\ldots\sim\frac{1}{187}.$$ An explicit computation of the coefficients in $(3)$ gives: $$ A_1 = 1.00040773044846\ldots,$$ $$ A_2 = A_3 = -0.006863339\ldots,$$ $$ A_4 = A_5 = 0.0066594738\ldots,$$ hence the true probability is: