Fair results with unfair die

Question

You are given a 6-sided die.The die is biased, so it is more likely to produce some results than others, but you don't know the exact odds. It is however given that the odds are the same for each roll, and that all 6 faces have a non-zero probability of coming up.

Create a scheme, using this die as the only source of random, that generates a number from 1 to 6 with a probability of exactly 1/6 for each possible outcome.

For added difficulty, try to make a scheme that use as few rolls as possible on average. For calculating the average, assume a fair die.

My best solution has the following average:

144/35 ≈ 4.114

Answer 1

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$

Answer 2

In order to get the most out of each roll it is beneficial to note that it doesn't matter if the intermediate data is skewed, as long as each result is paired off with 5 others of equal probability.

A series of rolls is considered to have a form that depend only on which rolls were equal to another, the first roll is always designated A, the first of the remaining rolls that is not equal to A is B etc. So the series 552 has the form AAB, as does 223.

Six different forms that all have the same number of repetitions can be paired, like AAAAAB, AAAABA, AAABAA, AABAAA, ABAAAA, ABBBBB.

A set of form that has the same number of two different rolls only need to consist of three different forms as each form has two equally likely outcomes where these numbers are switched. For example AABC, ABAC, ABBC translates amongst other possibilities to 4412, 4421, 4142, 4241, 1442, 2441.

Finally an equal amount of three different numbers means that a form can be paired with only itself.

I have designed a table of pairings for up to 6 rolls:

Results after 3 rolls:
ABC        probability 4320/7776

Unpaired:
AAA
AAB
ABA
ABB

Results after 4 rolls:
AABB       probability  540/7776
ABAB
ABBA

AABC       probability 2160/7776
ABAC
ABBC

Unpaired:
AAAA
AAAB
AABA
ABAA
ABBB

Results after 5 rolls:
AABAC      probability  360/7776
ABAAC
ABBBC

Unpaired:
AAAAA
AAAAB
AAABA
AAABB
AAABC
AABAA
AABAB
ABAAA
ABAAB
ABBBA
ABBBB

Results after 6 rolls:
AAAAAB     probability   30/7776
AAAABA
AAABAA
AABAAA
ABAAAA
ABBBBB

AAAABB     probability   30/7776
AAABAB
AAABBA
AABAAB
AABABA
ABAAAB

AAAABC     probability  120/7776
AAABAC
AAABCA
AABAAC
ABAAAC
ABBBBC

AAABCD     probability   60/7776

AAABBC     probability  120/7776
AAABCB
AAABCC
AABABC
ABAABC
ABBBAC

AABABB     probability   15/7776
ABAABB
ABBBAA

Unpaired:  probability   21/7776
AAAAAA
AAABBB
ABAABA
ABBBAB
ABBBBA

If this table of pairings is used along with the rule that unpaired results of 6 rolls are discarded and the method is restarted with 3 fresh rolls the average number of rolls is given by the equation:

$$X=\dfrac{3\times4320+4\times2700+5\times360+6\times375+(6+X)\times21}{7776}\\ X=\dfrac{9312}{2585}\approx3.602$$

Extending the table to allow longer series, and thus reducing the chance of having to discard the rolls, should give a slightly better result, at the cost of making this answer even longer.

Answer 3

I approach the problem the following way:

first I think of a simpler problem of an unfair coin: say H=Heads, T=Tails

Without knowing the probability of heads or tails, if I flip the coin twice, only HT and TH will have the same equal probability P(HT) = P(TH) regardless of how the coin if biased, I cannot say much about the P(HH) or P(TT). If H and T have probabilities non-zero, then at some point or another two trials will have different outcomes. To come up with an outcome that has probability 0.5 out of this coin, I would flip the coin until the last two trials give me different outcomes (HHHHHHHHT or TTTTTH) and then take the last outcome as my result.

For the dice, I would do the same thing, even though it could take a very long time: roll the dice until 6 consecutive rolls have distinct outcomes (for 6 rolls, there is a change of 6!/(6^6) of happening or 0.015), and take the last roll as the result.