2

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!

Hagen von Eitzen
  • 374,180
Carl German
  • 23

2 Answers2

2

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.

ShreevatsaR
  • 41,374
  • 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? – Carl German Apr 03 '14 at 00:23
  • @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). – ShreevatsaR Apr 03 '14 at 01:46
  • @CarlGerman: If that's not clear, I can try to explain again differently. – ShreevatsaR Apr 03 '14 at 01:47
  • 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.

     – Carl German Apr 05 '14 at 18:56
  • Is there a general formula here that I can use? – Carl German Apr 05 '14 at 19:02
  • @CarlGerman: putting two numbers together, as in $\frac{5}{6}\frac{4}{6}$, just means multiplying them; I realise it might have been confusing because I used $\cdot$ as well for the same purpose (I just used the latter to make the last one stand out). The general formula for dice with $n$ faces (numbered $1$ to $n$) is that the repeat happens after $k+1$ rolls (where $k \ge 1$) with probability $$\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}}.$$ – ShreevatsaR Apr 06 '14 at 01:58
  • @CarlGerman: For $n=6$, doing this calculation gives expected value $E[k+1] = \frac{1223}{324} \approx 3.77$. – ShreevatsaR Apr 06 '14 at 02:04
  • @CarlGerman: I've added it to the answer. – ShreevatsaR Apr 06 '14 at 02:23
  • Excellent -- thank you!!! I have marked your solution as the answer. Is there a standard name for the formula you provided? Is this the so-called Geometric distribution? – Carl German Apr 06 '14 at 03:40
  • @CarlGerman: No, the geometric distribution is the number of times you must roll dice before you see a particular number (say $4$). (Or more generally, number of independent trials until some event.) It is a very different sort of distribution, and it does not have bounded support: you might be staggeringly unlucky and need arbitrarily many dice throws before seeing that particular event. I'm not aware of any standard name for this distribution here, but the formula is the same as that for the birthday problem. – ShreevatsaR Apr 06 '14 at 07:19
1

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$$

Matthew Conroy
  • 11,234
Zubin Mukerjee
  • 17,832
  • Despite the length of this answer, it does not answer the main question (but sends the reader on at least two deadends). – Did Apr 02 '14 at 21:22
  • 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. – Zubin Mukerjee Apr 02 '14 at 21:36
  • @ZubinMukerjee, Thanks for the detailed reply. However, I think your answer only lists solutions for specific cases and does not provide a general answer. – Carl German Apr 03 '14 at 00:02