Abrazolica

In the last post I looked at how many rolls it takes to get a run of \(6\)'s on a die. Now I'm going to solve the problem using the probabilities for not getting a run of \(6\)'s. This will lead to a result that Krzys calls the Darth Vader rule.

Let's start with the probability generating function for not getting a run of \(n\) sixes. The regular expression for strings that do not have \(n\) consecutive \(6\)'s is:

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

With the substitutions \(6\rightarrow pz\), \(0\rightarrow qz\) and the usual operator conversions, the probability generating function is

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

Let \(q_k\) be the coefficient of \(z^k\) in the power series expansion of \(H(z)\), then \(q_k\) is the probability of not getting a run of \(n\) \(6\)'s in \(k\) rolls. To find the sum of all these probabilities set \(z=1\) and you get

\[H(1)=\sum_{i=0}^{\infty}q_i=\frac{1-p^n}{qp^n}\]

which turns out to be the expectation for the number of rolls it takes to get a run of \(n\) \(6\)'s that I derived in the last post. Is this just a coincidence or what?

To see why this must be true let \(X\) be the random variable for the number of rolls it takes to get a run and let \(p_k\) be the probability that \(X=k\). The probability of not getting a run on roll \(k\) is equal to the probability that \(X\) is greater than \(k\). This allows us to relate the \(p\)'s and \(q\)'s as follows:

\[q_k=P(X > k)=\sum_{i=k+1}^{\infty}p_i\]

so \(q_0=\sum_{i=1}^{\infty}p_i=1-p_0\) and, for \(k > 0\), \(q_k-q_{k-1}=-p_k\). The generating functions for \(q_k\) and \(p_k\) must therefore be related as follows: \((1-z)H(z)=1-G(z)\) or

\[H(z)=\frac{1-G(z)}{1-z}\]

Taking the limit of the right hand side as \(z\) goes to \(1\) gives

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

This means you can find the expected number of rolls for getting a run by summing the probabilities for not getting a run. It may seem surprising at first but if you write it out as:

\[E[X]=\sum_{i=0}^{\infty}q_i=\sum_{i=0}^{\infty}P(X > i)\]

then you can see the result since the \(P(X > i)\) terms are sums of \(p_k\) terms such that every \(p_k\) term appears exactly \(k\) times in the overall sum, making it by definition the expectation. The result is true for any discrete random variable that takes on positive integer values. Krzys calls this the Darth Vader rule and he has another paper, which you can find here, where he generalizes the rule to any non-negative random variable \(X\).