 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Repeated roll (Posted on 2012-05-25) Consider the following game: Roll a fair die of n sides. Continue rolling until some number has been rolled twice. You win if it takes 4 or more additional rolls (5 or more total).

What is the least number of sides the die could have if the expected number of additional rolls required is greater than 4?

 No Solution Yet Submitted by Jer No Rating Comments: ( Back to comment list | You must be logged in to post comments.) solution | Comment 2 of 4 | The probability that the first number will appear on the very first additional roll is 1/n. That this will not happen, but that one of the first two will appear on the second added roll is (n-1)/n * 2/n. That neither of these happens, but a match appears on the third added roll, is (n-1)/n * (n-2)/n * 3/n, etc.

In computing the expected value of the number of added rolls, each of these mutually exclusive probabilities must be multiplied by the respective series length and then the terms added together. Each term, i, is then i*Sum{j=1 to i-1}(n-j)/n * i/n.

CLS
DEFDBL A-Z
FOR n = 2 TO 20
tot = 0
FOR i = 1 TO n
term = i * i / n
FOR j = 1 TO i - 1
term = term * (n - j) / n
NEXT
tot = tot + term
NEXT
IF n >= 4 THEN
prob4 = (n - 1) / n * (n - 2) / n * (n - 3) / n
ELSE
prob4 = 0
END IF
PRINT n, tot; TAB(40); prob4
NEXT

The program above implements the given expected added rolls, and also, for comparison, the probability that the repetition will happen only after at least 4 added rolls, i.e., that the first three added rolls will not produce a match.

`n         exp. number of             prob. of needing            added rolls           at least 4 added rolls`
`2             1.5                      03             1.888888888888889        04             2.21875                  .093755             2.510400000000001        .1926             2.774691358024691        .27777777777777787             3.018138700711438        .34985422740524788             3.245018005371094        .410156259             3.458315744885656        .460905349794238710            3.66021568               .50411            3.852372050737359        .54094665664913612            4.036073675098951        .572916666666666613            4.21234791295252         .600819299044151114            4.382029424383519        .625364431486880515            4.545807285147228        .647111111111111116            4.704258247072678        .6665039062517            4.857870820801628        .68389985752086318            5.007063098992892        .699588477366255219            5.152196200957448        .713806677358215520            5.293584586000899        .72675`

Note that the answer to the puzzle is that it takes a 12-sided die to make the expected number of added rolls to exceed 4.

Further exploration:

But it takes only a 10-sided die to give over 50% probability that at least 4 added rolls will be needed.

Simulation verification of formulas used:

A simulation program for the 20-sided case verifies that we've used the correct formulas:

DEFDBL A-Z
FOR trial = 1 TO 1000000
n = 20
REDIM h(20)
h(0) = INT(RND(1) * n + 1)
fin = 0
roll = 0
DO
roll = roll + 1
r = INT(RND(1) * n + 1)
h(roll) = r
FOR i = 0 TO roll - 1
IF r = h(i) THEN fin = 1: EXIT FOR
NEXT
LOOP UNTIL fin
totrolls = totrolls + roll
IF roll >= 4 THEN tot4 = tot4 + 1
PRINT trial, totrolls / trial, tot4 / trial
NEXT

finding the averages after a million trials as 5.296289 and .726962, in statistical agreement with the table entries for n=20.

 Posted by Charlie on 2012-05-25 14:30:40 Please log in:

 Search: Search body:
Forums (0)