4

I wonder if there's any exact way to find out these two things about six-sided dice:

  1. How many throws would be necessary to get six times the same number (let's say six) in a row?
  2. What's the probability of getting six times the same number (again, let's say six) in a row within 100 throws?

I wrote a simple simulation program in C and tried it on $100*2^{20}$ numbers, but I want to compare my numbers and see if I can skip the programming part in future.

For the first question, I got number around $54160$, and for the second one it was $1861/1048576 \approx 0.001775$. I was told that my numbers should be smaller and bigger respectively. Is there any chance for my numbers to be OK? Otherwise it would mean that I made a mistake in my code.

kjetil b halvorsen
  • 63,378
  • 26
  • 142
  • 467
user35443
  • 141
  • 1
  • 3
  • Concerning question 1: Do these help: [First](http://math.stackexchange.com/questions/27989/time-until-a-consecutive-sequence-of-ones-in-a-random-bit-sequence/27991#27991), [second](http://math.stackexchange.com/questions/192177/how-many-times-to-roll-a-die-before-getting-two-consecutive-sixes)? – COOLSerdash Dec 06 '14 at 11:20
  • 1
    Question 1 is like asking "how large is a normally distributed random variable", which is nonsense. Maybe you are interested in the distribution the waiting time or maybe just its average? – Michael M Dec 06 '14 at 12:32
  • Q: How many times? ANSWER: a lot. – wolfies Dec 06 '14 at 14:50
  • 2
    The multiple answers at http://stats.stackexchange.com/questions/12174/time-taken-to-hit-a-pattern-of-heads-and-tails-in-a-series-of-coin-tosses provide several approaches to tackles questions like this. – whuber Dec 06 '14 at 18:35
  • You realize that you'll have different numbers of throws to get "6" size times and to get any side six times? – Aksakal Dec 07 '14 at 16:16

2 Answers2

6

Yes, there is a way to get the exact answer.


Definition & Notation:

$X_i$: number of throw to get the same number (let say 6) in $i$ consecutive rolls,

$\mu_i = E(X_i)$, that is the expected number of roll; $\mu_6$ is what we want.

$D$: Indicator of whether get the number we desire (6 in this case) in one throw, 1 for success, 0 for fail. It is clearly that $D \sim Bernoulli(p)$.

$p$: the probability of getting the number (6) we desire

Let's us start from the simplest case $i=1$, the number of throw to get one 6. Some of you may quickly realised that $$\mu_1 = \frac{1}{p}$$

In fact, when $i=1$, we are doing a sequence of independent bernoulli trial until we make the first success (get one 6) and $X_1$ is the number of trial needed until the first, which follows a geometric distribution$^1$$^2$$^3$ with parameter $p$, and its mean is $\frac{1}{p}$.

So, how about $i\ge2$? In order to get r consecutive 6's in dice rolling, we must get (r-1) consecutive 6's first. At that moment we have 2 scenarios:

  1. We get a 6 in the next throw and end
  2. We don't get a '6' and keep playing with our dice until we get r consecutive 6's

As you will see, the number of throw is $X_{r-1}+1$ in the first scenario, and $X_{r}+1+X_{r}$ in another. Don't forget that you have the count the throw right after you get (r-1)-time 6's, so we have '+1' when we calculate both counts. Combining them, we have

$$X_r = X_{r-1} + 1 + (1-D)X_r$$

Using double expectation: $$\mu_r = E(X_r) = E\left[E(X_r|D)\right]$$ $$\implies \mu_r = pE\left[E(X_r|D=1)\right] + (1-p)E\left[E(X_r|D=0)\right]$$ Since $$(X_r|D=1) = X_{r-1} + 1 \implies E(X_r|D=1) = \mu_{r-1} + 1$$ $$(X_r|D=0) = X_{r-1} + 1 + X_r \implies E(X_r|D=0) = \mu_{r-1} + 1 + \mu_r$$ we have $$\mu_r = p[\mu_{r-1}+1] + (1-p)[\mu_{r-1} + 1 + \mu_r]$$ After some rearrangement, we will get the following relationship: $$\mu_r = \frac{\mu_{r-1}+1}{p}$$

If we are playing a fair dice (i.e. $p=\frac{1}{6}$), we will obtain $\mu_6 = 55986$.

Now, we relax our criteria, let say any number (either 1, 2, 3, 4, 5, 6) appears six times in a row. The answer is truly smaller than 55986 because you can six 1's before getting six 6's. To calculate the expected number of throw, same logic used above still apply:

$Y_i$: number of throw to get the same number (either 1, 2, 3, 4, 5, 6) in $i$ consecutive rolls,

$\theta_i = E(Y_i)$, that is the expected number of roll; $\theta_6$ is what we want.

$D_x$: Indicator of getting $x$, $x\in\{1,2,3,4,5,6\}$.

First, we have $\theta_1=1$ this time. The reason is obvious, when we throw a dice, we must get a number from {1, 2, 3, 4, 5, 6} and end rolling dice afterwards, the count ($X_1$) must be 1, also $\mu_1$, unless you are not playing a 6-sided dice or the dice disappeared after you throw it etc.

And for $r \ge 2$, let's go back to the scenario of getting $x$ (r-1)-time

  1. We get a $x$ in the next throw and end
  2. We don't get a $x$ but $y$, $y \ne x$, keep playing with our dice until we get r consecutive $y$

For scenario 1, only ($Y_{r-1}+1$) rolls are needed, but for another scenario, we need ($Y_{r-1}+Y_r$). Be noted that no '+1' is needed here because when a different number $y$ shows up, we are attempt to get $r$ consecutive $y$, the 'first' roll is included in $Y_r$ here. Then, the following can be derived:

$$Y_r = D_x(Y_{r-1}+1) + (1-D_x)(Y_{r-1}+Y_r), x \in \{1,2,3,4,5,6\}$$

If we are playing a FAIR dice, the recursive relation can be generalized as $$Y_r = X_{r-1} + (1-D)Y_r$$

where $D$ is the indicator of getting the same number as last throw given that we are playing a fair dice, $Pr(D=1)=\frac{1}{6}$.

After all, the following can be derived, $$\theta_r = 6\theta_{r-1}+1$$

Applying the formula, $\theta_6 = 9331$ will be obtained under the looser criteria (fair dice). (Credit to Aksakal for pointing out my mistake).


For the second question, we can make use of the transition matrix $M$ $$M = \left[\begin{matrix} \text{stage} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & \frac{5}{6} & \frac{1}{6} & 0 & 0 & 0 & 0 & 0\\ 1 & \frac{5}{6} & 0 & \frac{1}{6} & 0 & 0 & 0 & 0\\ 2 & \frac{5}{6} & 0 & 0 & \frac{1}{6} & 0 & 0 & 0\\ 3 & \frac{5}{6} & 0 & 0 & 0 & \frac{1}{6} & 0 & 0\\ 4 & \frac{5}{6} & 0 & 0 & 0 & 0 & \frac{1}{6} & 0\\ 5 & \frac{5}{6} & 0 & 0 & 0 & 0 & 0 & \frac{1}{6}\\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{matrix}\right]$$

where stage $i$ means we currently have $i$ consecutive '6' and we assume that we are playing a fair dice.

The entries of the matrix are the probability of getting from one stage (row) to one stage (column). If we dice once; for example, from stage 6 to stage 6, the probability is 1 (because we have achieved our goal)

By the properties of transition matrix, $M^k$ is the transition matrix of rolling the dice k-time. Therefore, we can calculate $M^{100}$ and value in the first row and the last column will be the probability of going to stage 6 from stage 0 after 100-time of roll dicing, that is your answer. (it is 0.001699134)

If we loosen our criteria to any number six times in a row, our transition matrix will become

$$M = \left[\begin{matrix} \text{stage} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & \frac{5}{6}& \frac{1}{6} & 0 & 0 & 0 & 0\\ 2 & 0 & \frac{5}{6} & 0 & \frac{1}{6} & 0 & 0 & 0\\ 3 & 0 & \frac{5}{6} & 0 & 0 & \frac{1}{6} & 0 & 0\\ 4 & 0 & \frac{5}{6} & 0 & 0 & 0 & \frac{1}{6} & 0\\ 5 & 0 & \frac{5}{6} & 0 & 0 & 0 & 0 & \frac{1}{6}\\ 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{matrix}\right]$$


For question 1 (six consecutive '6'), there is another way of think (which is my original answer) but similar approach. It will yield a slightly different result and the reason is still unknown. Any discussion are all welcome.

Definition & Notation:

stage $i$: the moment that we have $i$ 6 in a row

$X_i$: the random variable of no. of rolls needed in stage $i$ in order to get "6" six times

$\mu_i = E(X_i)$, in this case, $\mu_0$ is our answer.

Suppose we have now diced $n$-time and get five 6's in a row (stage $5$) and roll the dice again. If we get a 6, we achieve our goal and the count of rolling is $n+1$; otherwise, we go back to stage $0$ and $(1 + X_0)$-time will be needed to archive our goal. Thus, the expected value of $X_5$ ($\mu_5$) will be $$\mu_5 = \frac{1}{6} + \frac{5}{6}(1+\mu_0) = 1 + \frac{5}{6}\mu_0$$

Now, consider we have four 6's in a row (stage $4$). If we get a 6 next, we proceed to stage $5$, that means we have to roll $(1+X_5)$-time more; otherwise, we are back to stage $0$. Thus, $$\mu_4 = 1 + \frac{1}{6}\mu_5 + \frac{5}{6}\mu_0$$

Following the same logic, the followings will be obtained: $$\mu_3 = 1 + \frac{1}{6}\mu_4 + \frac{5}{6}\mu_0$$ $$\mu_2 = 1 + \frac{1}{6}\mu_3 + \frac{5}{6}\mu_0$$ $$\mu_1 = 1 + \frac{1}{6}\mu_2 + \frac{5}{6}\mu_0$$ $$\mu_0 = 1 + \frac{1}{6}\mu_1 + \frac{5}{6}\mu_0$$

So, we get a system of linear equations: $$\left[\begin{matrix} \frac{1}{6} & -\frac{1}{6} & 0 & 0 & 0 & 0 \\ \frac{5}{6} & -1 & \frac{1}{6} & 0 & 0 & 0 \\ \frac{5}{6} & 0 & -1 & \frac{1}{6} & 0 & 0 \\ \frac{5}{6} & 0 & 0 & -1 & \frac{1}{6} & 0 \\ \frac{5}{6} & 0 & 0 & 0 & -1 & \frac{1}{6} \\ \frac{5}{6} & 0 & 0 & 0 & 0 & -1 \\ \end{matrix}\right] \left[\begin{matrix}\mu_0 \\ \mu_1 \\ \mu_2 \\ \mu_3 \\ \mu_4 \\ \mu_5\end{matrix}\right] = \left[\begin{matrix}1\\ -1\\ -1\\ -1\\ -1\\ 1\end{matrix}\right] \implies \left[\begin{matrix}\mu_0 \\ \mu_1 \\ \mu_2 \\ \mu_3 \\ \mu_4 \\ \mu_5\end{matrix}\right] = \left[\begin{matrix}55974\\ 55968\\ 55932\\ 55716\\ 54420\\ 46644\end{matrix}\right] $$

pe-perry
  • 762
  • 6
  • 21
  • 2
    +1. There has to be a mistake (probably a typo) concerning the first question: When I solve the linear equation system as given in the answer, I get different numbers: $55974, 55968, 55932, 55716, 54420, 46644$. – COOLSerdash Dec 06 '14 at 13:55
  • Oh yes, I got a typo in my code of calculation. The solution of the system should be (55974, 55968, 55932, 55716, 54420, 46644) – pe-perry Dec 06 '14 at 14:05
  • 1
    Also, the answer of question 2 is 0.001699134 (if I calculate it correctly) – pe-perry Dec 06 '14 at 14:06
  • 1
    That'a what I got (for the second question). Just out of curiosity: How do you explain the discrepancy between your answer to question 1 and the answer we get when we apply the formulas in [this answer](http://math.stackexchange.com/questions/192177/how-many-times-to-roll-a-die-before-getting-two-consecutive-sixes) (by Byron Schmuland)? Using $p=\frac{1}{6}$ and $n=6$, I get $\left(\frac{1}{6}^{-6}-1\right)/(\frac{5}{6})=55\,986$ which differs from your answer of $55\,974$. – COOLSerdash Dec 06 '14 at 14:09
  • I am still thinking why there is difference but still no conclusion. However, when I modified the definition of $X_i$, and follow similar logic, the formula you used was derived $$X_i \text{: no. of rolls to get }i\text{ consecutive 6's}$$ $$p = Pr(\text{get a 6}) $$ $$\mu_1 = 6$$ $$\mu_2 = \mu_1 + p + (1-p)(1+\mu_2)$$ $$\mu_3 = \mu_2 + p + (1-p)(1+\mu_3)$$ $$\vdots$$ $$\mu_k = \mu_{k-1} + p + (1-p)(1+\mu_k)$$ $$\implies \mu_k = \frac{\mu_{k-1}+1}{p}$$ – pe-perry Dec 06 '14 at 17:19
  • And one point to add, if you want to find out the expected number of throws to get six times the same number (either 1,2,3,4,5,6) in a row; the above formula/solution will be inappropriate. – pe-perry Dec 06 '14 at 17:24
  • @kitman0804, you are not answering OP's question 1. OP is not asking how many throws *in average*. So, maybe you should start with reformulating the question. Even more important, OP is asking two different questions in Q1: one is about any side and one is about side 6. They'll have different answers. – Aksakal Dec 07 '14 at 16:14
  • @Aksakal Thanks for your comment. I do believe that OP is asking about the average number of throws, not the 'necessary' number of throws which is 6 (maybe OP need to clarify it). Also, I have noticed that OP is also asking about any side six times, I have mentioned that the answer will be different in this case but did not provide the answer. I will add it soon. – pe-perry Dec 09 '14 at 11:51
  • 1
    @kitman0804, I don't think your answer for six of any side is right. It's got to be 1/6 of the 6 of 6. Somthing like ~9K – Aksakal Dec 10 '14 at 03:26
  • @Aksakal You are right. Thanks again for pointing my mistake. – pe-perry Dec 10 '14 at 06:48
  • Sorry for renewing after 3 years, I'm the OP. Got an offer to study mathematics at uni! How soon will I be able to understand all of the above? :P (e. g. during bachelors, masters or ...?) – user35443 Feb 20 '17 at 18:44
6

Regarding question 1, there is a very simple and elegant way to obtain a result via Martingale Theory (refer to the best (in my humble opinion) introductory book on the subject Probability with Martingales chapter 10 section 11). The proof requires hardly any calculations and is done in 3 steps provided that you use several martingale theory results (Doob's optional stopping time theorem in particular). Look it up!

QUESTION: What is the expected time for a monkey to type ABRACADABRA on a typewriter, provided that you only have 26 keys (the letters of the alphabet) and his typing is random (so 1/26 chances of producing any given letter at any time? Try solving this with standard recursive methods!

ANSWER: $E\left ( T \right ) = 26^{11} + 26^{4} + 26$

Had the chain been ABCDEFGHIJK it would have required (26^11), so although this might seem counter-intuitive, randomly producing chains that have symmetry or a repetitve pattern takes longer on average.

The general rule is the following:

$E\left ( T \right )= \sum_{k = 1}^{n}\left ( \frac{1}{p} \right )^{k}\times I_{pattern}\left ( n - k + 1 \right )$

where n is the length of the chain, p the probability of typing any given character, and

$$ I_{pattern}(k) = \begin{cases} 1 & \text{if pattern(j) $=$ pattern(k + j - 1) } \forall j \in \left \{1,...,n-k+1\right \}\\ 0 & \text{otherwise.} \end{cases} $$

In your case, since the pattern is simply a repitition of 6s, the average time (i.e. average number of rolls) is $6^{6} + 6^{5} + ... + 6$

Hitch Alisson
  • 161
  • 1
  • 3