If a dice is rolled twenty times, what are the odds that a 3 and a 4 occur successively at least once?

Question

So at first this seemed like a fairly simple binomial trial problem, but I realized you can't model this as 19 separate events because each event sort of interferes with the next, in that, for

3 1 2 4

The one precludes the next "set of two" from being possible. So I'm not sure how to tackle this. I wrote some Python code to experimentally find a number that's close enough:

https://gist.github.com/danishanish/0c52d4585ef7bd0508644311990e20b5

So I've run this a whole bunch of times and the answer looks a lot like it's around ~0.155438 from a few thousand trials. I have two questions:

1. What is the proper mathematic way of computing this solution?
2. Is there any problem in my code that would keep it from finding the solution when scaled?

Answer 1

Assuming that you mean a $3$ and a $4$ consecutively and in that order, you can approach the problem using combinatorial methods using the principle of inclusion and exclusion.

Treat the $34$ string as a single unit, which can appear in any of $19$ different locations. The remaining $18$ digits can have any of $6$ different values, so that gives you a total of $19 \cdot 6^{18}$ possible combinations.

But that is an overcount because arrangements with a pair of $34$ combinations are counted at least twice. So you need to subtract off all sequences with a pair of $34$ combinations. There are $\binom {18}{2}$ possible positions the $16$ singlets and $2$ pairs can take.

Now you need to add back all arrangements with $3$ $34$ combinations. There are $\binom{17}{3}$ possible positions the $14$ singlets and $3$ pairs can take. Then subtract all sequences with $4$ of the pairs, etc., until finally you subtract the single arrangement with $10$ of the combinations. It's a little tedious but manageable.

Finally, divide by $6^{20}$, which is the total number of combinations. Thus,

$$ \frac{ \sum_{k=1}^{10} (-1)^{k+1} \binom{20-k}{k}6^{20-2k}}{6^{20}}.$$

Answer 2

I don't think you need inclusion-exclusion. If $a_n$ is the number of acceptable sequences of $n$ rolls, then $a_n=6a_{n-1}-a_{n-2}$ with initial conditions $a_1=6$, $a_2=35$, and now apply standard techniques for solving constant coefficient homogeneous linear recurrences. Or just write a program to compute $a_{20}$ from the initial values and the recurrence.