Abrazolica

A friend of ours, Krzysztof Ostaszewski, has a paper in The Mathematical Gazette (p. 39, V. 96, N. 535, March 2012) called: The 6666 Problem. It's about different ways to calculate the average number of times a die has to be rolled to get \(n\) sixes in a row. The paper is a fun read for anyone interested in probability problem solving tricks. I'm going to show another way to solve the problem that was not covered in the paper. I'll call it the Symbolic Method.

Let's start with the particular problem of getting four sixes in a row. The sequence of die rolls can be recorded as a string of \(0\)'s and \(6\)'s where a \(0\) represents any number other than \(6\). It is easy to write down a regular expression for the language consisting of all strings with four consecutive \(6\)'s only at the end. The regular expression is:

\[R=(0+60+660+6660)^*6666\]

For a succinct introduction to regular expressions and how to turn them into generating functions see my previous blog post, Counting with Regular Expressions or see our new book Finite Automata and Regular Expressions: Problems and Solutions.

To turn the regular expression into a probability generating function use the substitutions \(6\rightarrow pz\) and \(0\rightarrow qz\) where \(p\) is the probability of rolling a \(6\) and \(q=1-p\) is the probability of not rolling a \(6\). For a fair die \(p=1/6\) and \(q=5/6\). With the substitutions and the usual operator conversions the probability generating function becomes

\[G(z)=\frac{p^4z^4(1-pz)}{1-z+qp^4z^5}\]

From the generating function it's easy to get the expected number of rolls and the variance. The expectation is found by taking the first derivative of \(G(z)\) and setting \(z=1\).

\[\mu=G'(1)=\frac{1-p^4}{qp^4}\]

This equation is just a geometric series in disguise. It is equivalent to: \(\frac{1}{p}+\frac{1}{p^2}+\frac{1}{p^3}+\frac{1}{p^4}\). So for a fair die the expectation is: \(6+6^2+6^3+6^4=1554\).

Finding the variance is also relatively painless. The equation is:

\[\sigma^2=\mu(1-\mu)+G''(1)\]

Where \(G''(1)\) is the second derivative of \(G(z)\) evaluated at \(z=1\). For this particular problem the variance is:

\[\sigma^2=\frac{1}{q^2p^8}-\frac{9}{qp^4}-\frac{p}{q^2}\]

which evaluates to \(\sigma^2=2404650\) or a standard deviation of \(\sigma=1550.69\). This is a very volatile process.

The symbolic method can easily be generalized for runs of length \(n\). The regular expression in this case would look like:

\[R=(0+60+660+6660+\cdots+6^{n-1}0)^*6^n\]

The probability generating function is then

\[G(z)=\frac{p^nz^n(1-pz)}{1-z+qp^nz^{n+1}}\]

and the expectation and variance are given by

\[\mu=\frac{1-p^n}{qp^n}\]

\[\sigma^2=\frac{1}{q^2p^{2n}}-\frac{2n+1}{qp^n}-\frac{p}{q^2}\]

Now let's look at the situation where we start with one \(6\) and we want the expected number of rolls for getting four \(6\)'s in a row. The regular expression in this case is a simple extension of the one above. If the next three rolls are \(6\)'s then we have the run. If the next rolls are \(0\), \(60\), or \(660\) then we are back to the previous situation of starting with no \(6\)'s. The regular expression is therefor

\[R=666+(0+60+660)(0+60+660+6660)^*6666\]

which can easily be turned into a probability generating function. Actually we can express it in terms of the previous generating function as follows:

\[G_1(z)=p^3z^3+qz(1+pz+p^2z^2)G(z)\]

Using this form will show how the expectation changes when starting with one \(6\). I will leave the details for the interested reader.

The advantage of the symbolic method is that you can very easily extend it to find expectations and variances for arbitrary patterns such as \(66066\) for example. To find regular expressions for arbitrary patterns it is best to first construct a finite automaton for matching the pattern. The regular expression can then be found from the automaton. The method for doing this is in our new book: Finite Automata and Regular Expressions.

For more information on deriving and using probability generating functions for runs and patterns see our book: The Coin Toss: Probabilities and Patterns. The book derives generating functions from recursion equations which is different from the method described here.