4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Concerning question 1: Do these help: First, second? $\endgroup$ Commented Dec 6, 2014 at 11:20
  • 1
    $\begingroup$ 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? $\endgroup$
    – Michael M
    Commented Dec 6, 2014 at 12:32
  • $\begingroup$ Q: How many times? ANSWER: a lot. $\endgroup$
    – wolfies
    Commented Dec 6, 2014 at 14:50
  • 2
    $\begingroup$ The multiple answers at stats.stackexchange.com/questions/12174/… provide several approaches to tackles questions like this. $\endgroup$
    – whuber
    Commented Dec 6, 2014 at 18:35
  • $\begingroup$ You realize that you'll have different numbers of throws to get "6" size times and to get any side six times? $\endgroup$
    – Aksakal
    Commented Dec 7, 2014 at 16:16

2 Answers 2

6
$\begingroup$

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$

$\endgroup$
6
$\begingroup$

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 die 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 die 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 die (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 die, we must get a number from {1, 2, 3, 4, 5, 6} and end rolling the die afterwards, the count ($X_1$) must be 1, also $\mu_1$, unless you are not playing a 6-sided die or the die 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 die 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 die, 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 die, $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 die). (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 die.

The entries of the matrix are the probability of getting from one stage (row) to one stage (column). If we die 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 die 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$-times and get five 6's in a row (stage $5$) and roll the die 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] $$

$\endgroup$
11
  • 2
    $\begingroup$ +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$. $\endgroup$ Commented Dec 6, 2014 at 13:55
  • $\begingroup$ Oh yes, I got a typo in my code of calculation. The solution of the system should be (55974, 55968, 55932, 55716, 54420, 46644) $\endgroup$
    – pe-perry
    Commented Dec 6, 2014 at 14:05
  • 1
    $\begingroup$ Also, the answer of question 2 is 0.001699134 (if I calculate it correctly) $\endgroup$
    – pe-perry
    Commented Dec 6, 2014 at 14:06
  • 1
    $\begingroup$ 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 (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$. $\endgroup$ Commented Dec 6, 2014 at 14:09
  • 1
    $\begingroup$ @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 $\endgroup$
    – Aksakal
    Commented Dec 10, 2014 at 3:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.