https://www.cs.cmu.edu/~kmcrane/
1. Toss the coin and remember the answer.
2. Toss the coin again, if it is different from your previous toss then your result from #1 is fair. Otherwise, go back to step 1.
If p is the probability of getting heads, there are four possible outcomes with their associated probabilities:
TT -> (1 - p)^2 (rejected)
HT -> p * (1 - p)
TH -> (1 - p) * p
TT -> p^2 (rejected)
And that coin wasn't even biased... although Tom Stoppard was a confounding factor.
Imagine I glue a poker chip to a washer. There's a clear bias in the outcome of this "coin".
This method resolves that bias.
I'm not sure that two concurrent harmonious answers constitutes a "fixed" coin or a diagnosis of a fixed coin.
This scheme will be rubbish with a one sided coin ie the limit for "arbitrary fixed coin".
2. the person who achieves this is the winner.
Assign some scheme for converting permutations to an index.
Then get uniform bits out, maintain two variables: one is the product of the number of permutations, the other gets multiplied by the number of permutations and the index added. Whenever the number of possibilities is divisible by two, output the LSB of the index accumulator and halve the number of possibilities.
Size up your groups and accumulators and you can get arbitrarily high extraction rates.
Doing it efficiently and in constant time (e.g. without divisions) is the more exciting trick. A colleague and I managed an extractor for the binary case that packs takes 10+3N multiplies and N CTZs to pack N bits (giving an exact invertible encoding when bits choose ones is < 2^64).
Another reason to use dice for tabletop games is so that the game can be played without the use of a computer.
When I play GURPS, I generally use different dice with each dice roll in order to try to mitigate some of the bias. (I don't know quite how much effective this really is, though.)
https://archimedes-lab.org/2021/07/15/amazing-roman-rock-cry...
gametorch•7mo ago
the basic idea is that, because multiplication commutes, probability of A then B is the same as probability of B then A, so long as they are independent events (rolling objects typically meets this criteria)
so instead of using just A or just B, which might neither have 0.5 probability, you only count "A then B" and "B then A" as rolls
and this trivially extends to constructing a fair N-sided die out of any arbitrarily biased die for any N
ted_dunning•7mo ago
What they are doing is designing physical shapes that will have a specified probability of falling in different positions.
What you are talking about is post processing a biased random signal to get a less biased signal.
stevage•7mo ago
svat•7mo ago
ncruces•7mo ago
They wrote something interesting, even if it only tangentially matches the topic.
Pointing out that it doesn't exactly match the topic also adds to the conversation, I guess, but I think we've now exhausted any interest (so I won't be arguing further).
gametorch•7mo ago
wasn't trying to hurt anyone or anything
ethan_smith•7mo ago