A D20 labelled {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,20} is rolled 8 times, is the probability of at least two consecutive 1s 25599203481/25600000000

Question

This D20 has nineteen of its sides labelled as {1}, and the last one labelled as {20}. If this die is rolled 8 times, there are 25,600,000,000 possible different outcomes. Please confirm, prove or show that there are 25,599,203,481 out of all possible cases, which have at least two {1} rolled next to each other.

Two or more {20} do not satisfy this. For example, the rolls {1,20,1,20,20,20,1,20} is a false instance, because there are no two consecutive rolls with {1} in this string.

The method that I used to get this answer was not brute forced, but I am wanting to compare my method with maybe a simpler method that may exist.

I am only an amateur mathematician, but also help people in doing the math of their board game designs, and while this math problem seems like a fringe question, I have constructed it as a fringe case of a project that I have been working on.

Answer 1

Here is a way to proceed. I will replace the outcomes $1$ and $20$ by $1$ and $0$. We consider the following Markov chain with states $0,1,2$:

     1        1
[0] ---> [1] ---> [2]
 A        |
 |        |
  \______/
   

which counts the consecutive ones.

• The state $0$ means "no two consecutive ones so far, last result is empty or a $0$".
• The state $1$ means "no two consecutive ones so far, last result is $1$".
• The state $2$ means "two consecutive ones were already obtained". This state is absorbant, once we land here, we never quit.

Let $p=19/20$ be the probability to "read" an one, and $q=1-p=1/20$ the opposite probability. The transition matrix for this chain is $$ A = \begin{bmatrix} q & p & 0\\ q & 0 & p\\ 0 & 0 & 1 \end{bmatrix} \ . $$ Then we can compute easily (with a computer of course) the value of $A^8$.

gp > p = 19/20; q = 1-p;
gp > A = [q, p, 0; q, 0, p; 0, 0, 1];
gp > A^8
%6 =
[10223/1280000000 592059/25600000000 25599203481/25600000000]
[31161/25600000000 173299/25600000000 1279989777/1280000000]
[0 0 1]

So the probability to get from $0$ to $2$ in eight steps is that entry 25599203481/25600000000.

Answer 2

Simplify the notation to consider a coin with $P(H) = 19/20$ and $P(T) = 1/20$, and let $0 \leq n \leq 8$ be the number of $H$s in the sequence of $8$. Clearly if $n = 0$ or $1$ there are no consecutive $H$s. Likewise if $5 \leq n \leq 8$ you must have two successive $H$s.

Thus the only cases we must consider are $n = 2,3,4$.

For $n=2$, there are just $7$ cases: $HHTTTTTT$, $THHTTTT$, etc.

For $n=4$, there are just two cases where there are no $TT$ sequences: $HTHTHTHT$ and $THTHTHTH$. Compute the total number with 4 Ts and 4 Hs, and then subtract $2$.

For $n=3$, place $HH$ in any of 6 paired slot, and for each consider the possible positions for the remaining $H$. (Be careful to not overcount!)

Answer 3

This would be better expressed the other way around: the probability that a roll does not have two consecutive ones is $796519/(20^8)$, or in other words the number of ways of not getting two consecutive ones is $796519$.

The recurrence relation is pretty straightforward. Rather than have all these duplicate '1's kicking around, I'm going to use a regular d20 and look at the number of ways of not rolling two consecutive non-20 results. This is most simply looked at in terms of two sequences: $a_n$, the number of sequences without two consecutive non-20s where the last result is a 20, and $b_n$, the number of such sequences where the last result isn't a 20. Then we see that $a_{n+1} = a_n+b_n$, because putting a 20 on the end of a valid sequence gives a valid sequence regardless of whether it previously ended in 20 or not. Likewise, $b_{n+1}=19a_n$, because we can't put any non-20 result on a sequence that didn't end in 20, but we can put nineteen different results on a sequence that did.

Putting these together, we have that $a_{n+1}=a_n+19a_{n-1}$, and the result that you want for a sequence of length $n$ is $a_n+b_n=a_{n+1}$. This is a fibonacci-style recurrence relation, and it can easily be solved with all of the usual techniques for solving linear recurrence relations.

Answer 4

Cases where the rolls do not have consecutive $1s$ need to be $796519$, easily computable on a pocket calculator as

$1 + \binom8 1\cdot19 + \binom 7 2\cdot{19}^2 + \binom6 3\cdot{19}^3 +\binom5 4\cdot{19}^4 = 796519$

The term $\binom 7 2\cdot{19}^2$, for instance is where there are $two\; 1's \;and \;six\; 20's$, giving $7$ spaces for the $1's$ in the interstices of the $20's$ including the ends.