2
$\begingroup$

PHP developer here so no real math background :-( gave up after googling and hence the question

As the question states how many times does a single die have to be rolled for any of the previously rolled numbers to repeat. Meaning if the numbers have not repeated with each successive roll then the solution should take into account all previously rolled numbers to compute the probability of repeating

Finally is there a formula to compute this for arbitrary certainty? Meaning how many time to roll the dice number repeating with 50% or 70% certainty?

Example 1: First roll: 5 How many more times do I have to roll the die to get a 5 again.

Example 2: First roll: 1 Second roll: 3 How many more times do I have to roll the dice to get a 1 or 3 again.

Example 3: First roll: 2 Second roll: 1 Third roll: 4 How many more times do I have to roll the dice to get a 2 or 1 or 4 again.

And so on...

I would greatly appreciate a link to the theory or google terms as I would like to understand this clearly and not just get an answer.

Thank you very much for your time!

$\endgroup$
  • $\begingroup$ Geometric distribution $\endgroup$ – Henry Apr 2 '14 at 6:37
  • 2
    $\begingroup$ This is known as the "birthday problem", which may help you search. $\endgroup$ – Alex Becker Apr 2 '14 at 6:37
  • $\begingroup$ Also on a related note: Pigeonhole principle. After $7$ rolls you are guaranteed to get a match. $\endgroup$ – Guy Apr 2 '14 at 6:39
  • 2
    $\begingroup$ Carl, do you understand that it is possible to flip a fair coin and land heads 1000 times in a row? This is in reference to example 1 or 2. $\endgroup$ – Display Name Apr 2 '14 at 6:41
2
$\begingroup$

As you are guranteed to get a repeat after at most seven rolls, this is a very finite problem and we can simply enumerate all cases.

Here are possible runs of the consecutive dice rolls, where distinct letters stand for distinct numbers coming up, and the rolling is stopped as soon as we have a repeat.

  • $aa$: probability $\frac16$ (need the second roll to be the same as the first)

  • $aba$ or $abb$: probability $\frac56 \cdot \frac26$ (second roll distinct from first, and third roll same as any of the first two)

  • $abc$ and then repeat (that is, $abca$ or $abcb$ or $abcc$): $\frac56 \frac46 \cdot \frac36$

  • $abcd$ and then repeat: $\frac56 \frac46 \frac36 \cdot \frac46$

  • $abcde$ and then repeat: $\frac56 \frac46 \frac36 \frac26 \cdot \frac56$

  • $abcdef$ and then repeat: $\frac56 \frac46 \frac36 \frac26 \frac16 \cdot 1$

Thus, the number of times a dice is rolled before seeing a repeat is $2$ with probability $\frac16$, $3$ with probability $\frac5{18}$, and so on. In general, the probability that we roll $k+1$ times before seeing a repeat is $$\frac{n}{n}\frac{n-1}{n}\frac{n-2}{n}\cdots\frac{n-k+1}{n} \frac{k}{n} = \frac{n!k}{(n-k)!n^{k+1}}$$

From these numbers you can calculate the expected value, the thresholds for 50% or 70% certainty, etc.

For $n=6$, doing these calculations gives the expected number of times you roll the dice until seeing a repeat to be (using $r$ below for $k+1$, the number of rolls): $$\operatorname{E}[r] = \sum_{r=2}^7 r \frac{6!(r-1)}{(6-r+1)!6^r} = \frac{1223}{324} \approx 3.77$$ The cumulative probability distribution looks like the below:

CDF of r

Thus for example, you need to roll the dice at most $5$ times, with probability about $90\%$, at most $4$ times with probability about $70\%$, etc.

$\endgroup$
  • $\begingroup$ Thanks for the detailed response. Can you explain step 2 where you define the probability of aba or abb? According to wikipedia I am guessing this is a case of conditional probability right? If so can you please explain how you arrived 5/6 x 2/6? $\endgroup$ – Carl German Apr 3 '14 at 0:23
  • $\begingroup$ @CarlGerman: Different dice rolls are independent, so the probability of an outcome in some dice roll is the same whether or not we condition it on outcomes in other dice rolls. For the pattern $aba$, the probability of getting $a$ on the first dice roll is $1$ (because whatever the first dice roll is, that's what we call $a$); the probability of getting a $b$ different from $a$ on the second dice roll is $\dfrac{5}{6}$ (because there are $5$ possible choices of $b$ different from $a$); and probability of getting either $a$ or $b$ on the third roll is $\dfrac{2}{6}$ (two choices out of six). $\endgroup$ – ShreevatsaR Apr 3 '14 at 1:46
  • $\begingroup$ @CarlGerman: If that's not clear, I can try to explain again differently. $\endgroup$ – ShreevatsaR Apr 3 '14 at 1:47
  • $\begingroup$ Thanks for explanation, it makes sense. However for the next case of 3 rolls $(abc)$ what is the arithmetic operator between $\frac56$ and $\frac46$? What would the answer be for this case? Thanks again for all your help. $\endgroup$ – Carl German Apr 5 '14 at 18:56
  • $\begingroup$ Is there a general formula here that I can use? $\endgroup$ – Carl German Apr 5 '14 at 19:02
1
$\begingroup$

In general, the expected value for how many trials it will take for an event with probability $p$ to occur for the first time is $1/p$.


Example: The expected number of times that one needs to roll a die to get a two is $$\frac{1}{\frac{1}{6}}=6$$ since the probability of rolling a two on any given roll is $1/6$.


To answer your question. If you roll a five, the expected number of rolls you'll need to get another five is $6$, as in the example above.

The probability that you get a five on your very next roll is $1/6$. The probability that your first five is on the second roll is $$\frac{5}{6} \cdot \frac{1}{6}$$

In general, the probability that you get your first five on the $n^\text{th}$ roll after your first is $$\left(\frac{5}{6}\right)^{n-1} \cdot\frac{1}{6}$$.

This relates to what is known as a geometric distribution.


If you roll a $1$ then a $3$, the expected number of rolls you need to get either a $1$ or a $3$ is, similarly, $$\frac{1}{\frac{2}{6}} = 3$$

$\endgroup$
  • $\begingroup$ Despite the length of this answer, it does not answer the main question (but sends the reader on at least two deadends). $\endgroup$ – Did Apr 2 '14 at 21:22
  • $\begingroup$ I'm sorry. I didn't think it was completely unhelpful, but I'll work on editing this answer to include the certainty level questions. $\endgroup$ – Zubin Mukerjee Apr 2 '14 at 21:36
  • $\begingroup$ @ZubinMukerjee, Thanks for the detailed reply. However, I think your answer only lists solutions for specific cases and does not provide a general answer. $\endgroup$ – Carl German Apr 3 '14 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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