Skip to main content
added 1077 characters in body
Source Link
isaacg
  • 7.8k
  • 2
  • 21
  • 57

I have found a $144/35$$6156/1505 \approx 4.09$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

However, if on the second try the numbers are paired again, but with a different pair, such as AABB, this also gives us a random number of 1 or 2. If all 4 rolls are the same, we then repeat the procedure. The probability of finding any kind of solution on the first two steps is 5/6, but on the next 2 steps it goes up to 35/36. After AA, the only combination that does not give a solution is AA again. AB works, but so does BB. Obviously, this could be extended to groups of 8 and higher, but the improvement becomes very small.

We can use a similar procedure to this if we get rolls like AAABBBCCC in the main system. However, since the probability of a result like this is less than 1/512, I will skip it for now.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + y/6 \implies y = 12/5$ (2$y = 2 + (1/6)*(2 + y/36) \implies (215/216)*y = 2 + 1/3 \implies y = (216*7)/(215*3) = 504/215 \approx 2.344$

2 rolls definitely used, plus 1/6 chance of trying again, on which 2 rolls are definitely used and 1/36 chance of repeat.) This is an improvement of .65 rolls in this case. Adding in support for AAAABBBB would likely be minimal.

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = 3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 3 + 1 \implies x = (36/35)*4 = 144/35$$x = 3 + (5/12)*(504/215) + x/36 \implies (35/36)x = 3 + 42/43 \implies x = (36/35)*(214/43) = 6156/1505 \approx 4.09$

I have found a $144/35$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + y/6 \implies y = 12/5$ (2 rolls definitely used, plus 1/6 chance of repeat.)

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = 3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 3 + 1 \implies x = (36/35)*4 = 144/35$

I have found a $6156/1505 \approx 4.09$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

However, if on the second try the numbers are paired again, but with a different pair, such as AABB, this also gives us a random number of 1 or 2. If all 4 rolls are the same, we then repeat the procedure. The probability of finding any kind of solution on the first two steps is 5/6, but on the next 2 steps it goes up to 35/36. After AA, the only combination that does not give a solution is AA again. AB works, but so does BB. Obviously, this could be extended to groups of 8 and higher, but the improvement becomes very small.

We can use a similar procedure to this if we get rolls like AAABBBCCC in the main system. However, since the probability of a result like this is less than 1/512, I will skip it for now.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + (1/6)*(2 + y/36) \implies (215/216)*y = 2 + 1/3 \implies y = (216*7)/(215*3) = 504/215 \approx 2.344$

2 rolls definitely used, plus 1/6 chance of trying again, on which 2 rolls are definitely used and 1/36 chance of repeat. This is an improvement of .65 rolls in this case. Adding in support for AAAABBBB would likely be minimal.

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = 3 + (5/12)*(504/215) + x/36 \implies (35/36)x = 3 + 42/43 \implies x = (36/35)*(214/43) = 6156/1505 \approx 4.09$

There was a little bug in your equation, you always have to roll the first 3 times, so 3 shouldn't be multiplied by anything.
Source Link

I have found a $144/35$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + y/6 \implies y = 12/5$ (2 rolls definitely used, plus 1/6 chance of repeat.)

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = (5/9)*3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 5/3 + 1 \implies x = (36/35)*(8/3) = 144/35$$x = 3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 3 + 1 \implies x = (36/35)*4 = 144/35$

I have found a $144/35$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + y/6 \implies y = 12/5$ (2 rolls definitely used, plus 1/6 chance of repeat.)

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = (5/9)*3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 5/3 + 1 \implies x = (36/35)*(8/3) = 144/35$

I have found a $144/35$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + y/6 \implies y = 12/5$ (2 rolls definitely used, plus 1/6 chance of repeat.)

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = 3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 3 + 1 \implies x = (36/35)*4 = 144/35$

Source Link
isaacg
  • 7.8k
  • 2
  • 21
  • 57

I have found a $144/35$ solution. Here is how it goes:

Label the faces A, B, C, D, E, F. Roll the dice 3 times.

Each permutation of a given set of three faces is equally likely, because rolls are independent, so if the three rolls are different, we are done. If we number the permutations by their lexicographic ordering (ADE = 1, AED = 2, DAE = 3, ...), this gives us a uniform distribution from 1 to 6.

If the rolls are all the same, we have learned nothing useful, so we start over.

If two rolls are the same and one is different, (AAB), we have uniformly sampled from the 3 permutations of that outcome, e.g. AAB from (AAB, ABA, BAA). Once we have this value, we switch to attempting to generate a 1/2 probability.

We do this by rolling the dice twice. If the results are different, we use lexicographic ordering, and if they are the same, we try again. This gives us a uniformly random number, either 1 or 2.

We combine the random number from 1 to 3 with the random number from 1 to 2 with a formula such as $2*x-(y-1)$, where x is the number from 1 to 3 and y is the number from 1 to 2. This gives us a uniformly random number from 1 to 6.

Probability analysis:

Let y = average number of rolls to get 2 different numbers, to give the 1/2 probability in the second case.

$y = 2 + y/6 \implies y = 12/5$ (2 rolls definitely used, plus 1/6 chance of repeat.)

Let x be the average number of rolls to achieve a 1/6 probability. P(3 different) = $6*5*4/6^3 = 5/9$. P(2 same, 1 different) = $(6*5/6^3)*3 = 5/12$. P(3 same) = $6/6^3 = 1/36$. Thus,

$x = (5/9)*3 + (5/12)*(12/5) + x/36 \implies (35/36)x = 5/3 + 1 \implies x = (36/35)*(8/3) = 144/35$