3 ms·

Yes, better title would be "How thick is a fair three-sided coin?"

hinkley 4y ago
Getting a fair coin toss from a weighted coin is a fun mental exercise. I wonder what protocol one might employ to get a fair toss from a three sided coin that is 'best effort', where the edge is either under or over represented in the outcome but happens 1/4 < p < 1/2
- vikingerik 4y ago
  I think the two-sided protocol just extends to three. Do a set of three flips. If any two are the same, restart, until you get three distinct results. Each possible ordering of the three results is equally probable regardless of the weightings, so you can take any designated one (say the first) as the ultimate result. This should extend to any N, do sets of N flips until you get exactly one of each N distinct result, and take the first as the final result.
  - madcaptenor 4y ago
    Alternately, a protocol for getting a fair "d3" from a coin with any number of sides - flip three times. If all three results are the same or if all three are different, restart. If two are the same and one is different, the position of the odd one out gives your ultimate result. For example it works for simulating a d3 using a two-sided coin: THH or HTT -> 1, HTH or THT -> 2, HHT or TTH -> 3, HHH or TTT -> reroll. This can be combined with your protocol, but it takes some thought to interpret because in your protocol the result is what actually shows up on the coin, but in mine it's the position.
    - vikingerik 4y ago
      Aha, very nice. This is generalizable too: to get a fair dN from a randomization source with any number of unfair outcomes, do sets of N randomizations until you get a set that's exactly 1 of something and N-1 of something else, and the position of the unique one gives the ultimate result. (This requires N > 2, since for N=2 you can't tell which was the 1-of and which was the N-1.)
  - xnorswap 4y ago
    And you can calculate given an actual fair N-sided dice the proportion of wasted flips/rolls: 1: 0 2: 1/2 3: 7/9 4: 58/64 N: 1 - (N-1)! / N^(N-1) By the time you have a typical 6-sided dice, you only get 6 different rolls in 6 rolls 1.54% of the time. I haven't calculated what happens when bias is introduced but my intuition is that with more bias you would discard more. (Based on the extreme case that if one of the sides can never roll you would never accept a result.)

Getting a fair coin toss from a weighted coin is a fun mental exercise. I wonder what protocol one might employ to get a fair toss from a three sided coin that is 'best effort', where the edge is either under or over represented in the outcome but happens 1/4 < p < 1/2

vikingerik 4y ago
I think the two-sided protocol just extends to three. Do a set of three flips. If any two are the same, restart, until you get three distinct results. Each possible ordering of the three results is equally probable regardless of the weightings, so you can take any designated one (say the first) as the ultimate result. This should extend to any N, do sets of N flips until you get exactly one of each N distinct result, and take the first as the final result.
- madcaptenor 4y ago
  Alternately, a protocol for getting a fair "d3" from a coin with any number of sides - flip three times. If all three results are the same or if all three are different, restart. If two are the same and one is different, the position of the odd one out gives your ultimate result. For example it works for simulating a d3 using a two-sided coin: THH or HTT -> 1, HTH or THT -> 2, HHT or TTH -> 3, HHH or TTT -> reroll. This can be combined with your protocol, but it takes some thought to interpret because in your protocol the result is what actually shows up on the coin, but in mine it's the position.
  - vikingerik 4y ago
    Aha, very nice. This is generalizable too: to get a fair dN from a randomization source with any number of unfair outcomes, do sets of N randomizations until you get a set that's exactly 1 of something and N-1 of something else, and the position of the unique one gives the ultimate result. (This requires N > 2, since for N=2 you can't tell which was the 1-of and which was the N-1.)
- xnorswap 4y ago
  And you can calculate given an actual fair N-sided dice the proportion of wasted flips/rolls: 1: 0 2: 1/2 3: 7/9 4: 58/64 N: 1 - (N-1)! / N^(N-1) By the time you have a typical 6-sided dice, you only get 6 different rolls in 6 rolls 1.54% of the time. I haven't calculated what happens when bias is introduced but my intuition is that with more bias you would discard more. (Based on the extreme case that if one of the sides can never roll you would never accept a result.)