10 ms·

Make a Fair Coin from a Biased Coin (2018)

95 points by leonry 5y ago

paulmd 5y ago
despite all the theoretical work, it's not physically possible to bias a coin to any notable degree. Unlike a die you can't weight one of the faces, you can bend the coin but it takes about a 90 degree bend in a coin to be able to say that a coin is biased with statistical confidence. Or in other words, if the coin appears reasonably flat, it's fair enough that you won't notice. https://izbicki.me/blog/how-to-create-an-unfair-coin-and-prove-it-with-math.html https://izbicki.me/blog/how-to-create-an-unfair-coin-and-pro... I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it.
- nuclearnice1 5y ago
  Interesting stuff! Instead of biasing the coin, consider unrandomizing the flip. Here’s one of many articles on Perci Diaconis trying just this https://www.ams.org/publicoutreach/math-history/hap7-fifty-one-percent.pdf https://www.ams.org/publicoutreach/math-history/hap7-fifty-o...
- moron4hire 5y ago
  It also assumes that the two "coins" are biased in the same way. If the two ostensibly-50/50 random events are not equally biased, von Neumann's algorithm doesn't work.
  - mbokinala 5y ago
    I believe the steps said to toss the same coin twice.
    - madars 5y ago
      Yep. The assumption is that two flips are independent and identically distributed but that's a fair one: your flips don't change the coin, it does not have memory, etc.
      - dotancohen 5y ago
        Yes, flips do change the coin: they change which side is "up" at the moment of release. This could change the outcome of the flip.
  - IncRnd 5y ago
    Exactly. The input is the issue, despite this method's claim to fix bias in the input. As you point out, this method works as a limited thought experiment but not in the real world. To make an extreme example, if someone can cause the sequence to contain strings of HHHT, this algorithm would absolutely bias towards returning H. So, the key to overcoming this algorithm is to inject a sequence that, regardless of which modulo 2 positition is A or B in the code, will tend to fall on such an input bias. The point is that people trust code that says it fixes these sorts of things, so it is often easier than not to break the code by controlling the input. There are other methods used in the real world when ingesting random bit sequences.
    - eru 5y ago
      Yes. Von Neumann's method is definitely not safe against adversarial input.
      - IncRnd 5y ago
        Correct, though this is often improperly left out of the threat model.
- vikingerik 5y ago
  How are we defining a notable degree? Even a 1% skew is tremendous - entire casino empires are built on that probability margin.
  - godelski 5y ago
    You could calculate the likelihood over a certain distribution, in your case 1%. But when you do that you find that the third coin has a higher likelihood of being a fair coin than the first coin. That one has a pretty big bend in it. The ones after have a less than 4% chance of being fair. But to the OP's point, seeing that the third coin is more likely to be fair than the flat one (and is past a 45 degree angle) I think their claim makes sense with pretty good bounds.
    - mannerheim 5y ago
      To be fair, a 1% bias would probably not be detected in a hundred trials. CI for Bernoulli is +/- z * sqrt(p * (1-p) / n), so for a 95% confidence interval smaller than a percentage point, we have 1.96 * sqrt(p * (1-p) / n) = 0.01 0.5^2 / n = (0.01/1.96)^2 n = (1.96/0.01 * 0.5)^2 Or about 9604. So you need roughly 10k trials to determine with 95% confidence a bias of 1%.
  - morelisp 5y ago
    Even a fair coin has a 51/49 skew in a normal flip. https://epubs.siam.org/doi/abs/10.1137/S0036144504446436?journalCode=siread https://epubs.siam.org/doi/abs/10.1137/S0036144504446436?jou... But bending/weighting won't change that.
- monkeycantype 5y ago
  It depends how you flip it. If you spin a coin on the table, it seems like it should be fair, but small weight differences make a huge difference. If you try with an Australian 20c it's nowhere near 50:50, closer to 70:30 (heavy is the head that wears the crown apparently - from memory its the queen's head side that end up down and the platypus comes out on top.)
  - russfink 5y ago
    And what if you flip it over turf, e.g. at a large stadium during a huge televised sporting event? The implications on all of it are pretty big.
    - alisonkisk 5y ago
    - IncRnd 5y ago
      Like in this CBS news report that caught a coin landing on its edge in a soccer game? https://www.youtube.com/watch?v=Sz3VwRLsfX0 https://www.youtube.com/watch?v=Sz3VwRLsfX0 There very well be refs who can take advantage of coin flips over time.
- r00tanon 5y ago
  If the coin is thinner on one side, then it will fall on its edge more often? If the coin has an offset hole in the middle? A triangular coin? With an offset hole in the middle? Include thinner condition on the last three.
- dchftcs 5y ago
  The theoretical possibility of generating unbiased random bits from biased ones has critical practical implications. In computers we need unbiased random bits all the time but often only have biased sources.
  - eru 5y ago
    Definitely. And the commenter you replied to knows that. See https://news.ycombinator.com/item?id=30696269 https://news.ycombinator.com/item?id=30696269 for how you can improve on von Neumann's technique and still stay provably unbiased in your output.
- jchonphoenix 5y ago
  You and your article are wrong. Place extra metal on one side near and edge and run the experiment again. All because you can't imagine a way to do it doesn't mean it can't be physically done. This is a lesson kids. Randos on the internet can be wrong. Even with high conviction
- jorvi 5y ago
  > Unlike a die you can't weight one of the faces You can just glue a weight to one side of the faces at an offset.
- IncRnd 5y ago
  > despite all the theoretical work, it's not physically possible to bias a coin to any notable degree. > I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it. That's a case of working from false assumptions that aren't necessarily true in practice. The way to make a coin flip fair is to control as many variables as possible during the flip and landing - because that is what is done by people who bias the flip. Only one of these variables is the coin itself. Bias sometimes exists in the apparatus around the coin. After all some historical coins have ferrous metal in them, as the simplest example. Bias can also be introduced by the people performing the flips. For example, there are people who can flip a coin onto its edge or with an outcome biased towards heads or tails. A flip onto the coin's edge can even be done by an amateur. [1] After all, even without bias a coin can land on its edge. See this CBS News video from a Soccer game's ref flipping a coin. [2] [1] https://www.youtube.com/watch?v=M0I-xm7iCBU https://www.youtube.com/watch?v=M0I-xm7iCBU. [2] https://www.youtube.com/watch?v=Sz3VwRLsfX0 https://www.youtube.com/watch?v=Sz3VwRLsfX0
sidedishes 5y ago
A similar cute trick for making a coin with arbitrary bias p out of a fair coin: go through the (possibly infinite) binary expansion of p, flipping once for each digit. If you flip tails on a 1 or heads on a 0, go to the next digit and repeat. If you flip heads on a 1 or tails on a 0, stop and take that as your flip. (And if you get to the end of the expansion, you can think of it as only 0s now, so interpret it as tails)
- peeters 5y ago
  This doesn't seem quite right, unless I'm misunderstanding. If your bias was 128 (10000000) by your algorithm you would get heads at least 50% of the time (heads on the first flip) and tails at least 25% of the time (heads then tails). I think instead of taking the "wrong" flip result when they don't match, you should treat "getting to the end" as heads and failing before that as tails (or vice versa).
  - klipt 5y ago
    p is a probability in range [0, 1]. So if p = 1/128, the expansion is 0.0000001. In this case the algorithm says you return tails unless you flip 7 heads in a row (which happens with probability 1/128).
    - peeters 5y ago
      Ah thanks for the explanation. Makes a lot more sense with the fractional expansion.
- klipt 5y ago
  Intuitively, you're building a random real number in the range [0, 1) bit by bit, and returning 0 or 1 once you're sure that number is above or below threshold p.
- eru 5y ago
  That's basically how arithmetic coding works, isn't it? https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding
Animats 5y ago
That's useful when you want random bits from a pulse noise source, such as radioactive decay. Count pulses over a period of time, and take the last bit of the count. Do this twice. 10 => 1, 01 => 0, 00, 11 => retry. It seems to be a corollary that you cannot get random bits at a guaranteed rate that way.
- klipt 5y ago
  Doesn't that assume the distribution at time 1 is also the distribution at time 2, which isn't entirely true since the source is already sightly less radioactive then?
  - Animats 5y ago
    That's a good point. The effect is small but nonzero.
  - teraflop 5y ago
    Still works, with a slight variation: instead of taking two measurements, you can take four successive measurements [A,B,C,D] over equal periods of time, and then do the aforementioned procedure with the values A+D and B+C as input. If the activity is decreasing at a linear rate, then A+D and B+C should have exactly the same distribution. In reality, they will be ever so slightly different because the decay is exponential rather than linear, but over short periods of time (compared to the half-life) the linear approximation is extremely good.
    - OscarCunningham 5y ago
      https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Equitable_sequencing https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Eq...
  - tedunangst 5y ago
    Coin flips aren't fair either, because gravity will change slightly between successive flips.
hackernewsb 5y ago
I have a generally-applicable approach, i.e., a coin with any number of sides and any probabilities. Here we go, in the spirit of brute force: 0. Train your wrist, 'cause you'll be flipping this a gazillion times (say just N times) 1. Enumerate all possibilities, i.e., sample space = {H, T}^N 2. Compute the probabilities of each. 3. Partition the sample space into two such that the total probability (sum of probabilities) is equal to 0.5. 4. Call one element of the partition heads and the other tails. 5. Want a "multi-sided-coin"? Go back to step 3 and create a finer partition.
- eru 5y ago
  How do you partition the sample space in step 3 without knowing the bias of the coin? If you squint right, I described a method in https://news.ycombinator.com/item?id=30696269 https://news.ycombinator.com/item?id=30696269 for how to do just that. But I wonder whether you have a different method in mind?
fennecs 5y ago
Makes me think of some sort of symmetrisation. So for a 6 sided dice, you roll it 6 times in a row. You discard your 6 rolls unless you get a permutation of {1,2,3,4,5,6}, and in that case pick one of the rolls consistently, eg the first or the last.
- sideshowb 5y ago
  You're going to need a lot of rolls though. It'll be quicker to decide e.g. Heads is 123, tails is 456 and use Von Neumann's approach. If you already have a rough estimate of the bias you could even pick different faces for heads/tails to get p as close to 0.5 as possible before you start, again reducing the number of throws.
  - wildmanx 5y ago
    The point was to make the die roll unbiased, not to convert it into a unbiased coin toss.
    - sideshowb 5y ago
      Fair point Though I suspect still quicker to convert to unbiased coin toss and use those as the bits of a number in the desired range than to wait for a permutation of 123456
      - eru 5y ago
        Especially if eg 5 had an extremely low probability of showing up. Or perhaps even 0% probability.
odyssey7 5y ago
What if the coin's bias changes from flip to flip, perhaps influenced by its earlier results? Is there a solution for this?
- LeonB 5y ago
  Without knowing what sort of influence it has — it’s difficult to construct a general method, though, please check my idea and see if this achieves the purpose. First you find a gambler, any gambler and ask them to show you the lowest denomination coin they have, and get them to verify for you that it is a fair coin. Now demonstrate your weird coin to them, and when they are amazed by its properties, swap it with them for the fair coin. Done.
- paxys 5y ago
  This makes me think – is a coin with a truly random bias from flip to flip any different from a perfectly fair coin?
  - mannerheim 5y ago
    Depends on what you mean by 'truly random'. A distribution can be skewed, in which case the bias would itself be biased and then clearly different from a perfectly fair coin. Assuming you mean a uniform distribution, we can calculate this. Been a while since I've done stats, so bear with me... We can first argue from symmetry that we should expect as many heads as tails. But this doesn't mean that this is necessarily the same distribution as a perfectly fair coin (Bernoulli with p = 0.5). Anyway, the distributions we have here are a Bernoulli distribution and a uniform distribution X ~ {0, 1}; 0 with probability 1-q, 1 with probability q q ~ [0, 1], uniformly The expected value of X is E[X] = 0 * p(0) + 1 * p(1) = p(1) I think we could prove p(1) = E[q], but I'm honestly not sure, and don't know if that holds up in general. But from the above, we know it's 0.5 anyway. Now, we need higher moments: E[X^n] = 0^n * p(0) + 1^n * p(1) = p(1) = 0.5 The moment generating function of a probability distribution is defined as M_X(t) = E[e^(tX)]. There's a theorem in probability that two distributions with the same MGF are the same. You can see from the above that this has the same moments as a Bernoulli distribution with p = 0.5. Hence, a biased coin with a random uniform bias should be identical to a Bernoulli distribution. In fact, I believe the above argument works for not just uniform bias, but any random bias that is symmetric about p = 0.5.
sjaak 5y ago
See also the paper "Streaming Algorithms for Optimal Generation of Random Bits" https://arxiv.org/pdf/1209.0730.pdf https://arxiv.org/pdf/1209.0730.pdf
- eru 5y ago
  Ha, I should have read your comment before typing out my home-grown method in https://news.ycombinator.com/item?id=30696269 https://news.ycombinator.com/item?id=30696269 Thanks for the link!
eru 5y ago
Von Neumann's solution is clever, but extremely inefficient in terms of how many flips you need per random bit produced. More interesting methods produce a stream of unbiased random bits out of a stream of flips; and you can look at the asymptotic efficiency. A simple method to run better than von Neumann's method: Produce 1,000 coin flips. Say you produce k heads and 1,000-k tails. Produce a table of all possible sequences of length 1,000 with k heads and 1,000-k tails. Look up the position of your actual realized sequence in that table. The index of that position is a uniform random integer in a range from 1 to the size of the table. Use your favourite method to extract unbiased bits from that unbiased integer. The only requirement to make the above method work is that coin flips are i.i.d., ie independent and identically distributed. (In practice you probably don't want to actually construct the table, but instead compute the index directly as-if you had constructed the table. You might also want to work with arbitrary number of flips, instead of a fixed 1,000; or even adopt the method to an arbitrary length stream of coin flips that you don't know in advance. Also in practice, you don't need to store the whole sequence. What you do is keep a count of how many heads and tails you've seen so far, but feed the individual coin flips into an 'entropy pool'. Your head/tail count will inform your estimate of how many bits of entropy you have in your pool. (It basically feeds into the formula for how many possible orders of arrangement you have, similar to the fixed-size method suggested above.) You generate your unbiased bits by draining the from the entropy pool. The method of entropy pools described here is pretty much how /dev/random works on Linux.)
- jagged-chisel 5y ago
  > Produce a table of all possible sequences of length 1,000 with k heads and 1,000-k tails. This is more efficient than Von Neumann?
  - dmurray 5y ago
    More efficient if coin flips are your scarce resource, less efficient if computation is scarce. But nowhere near as inefficient as it sounds - you don't actually have to materialize the table.
  - steerablesafe 5y ago
alberto_ol 5y ago
Original Von Neumann paper, the method is described in the second paragraph: https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf
amitport 5y ago
I would say that the second coin is unfair but it's not "unbiased" in the statistics sense. It has an expected mean and taking the sample mean of flips will converge to it.
riccardomc 5y ago
I thought this was about _crypto_ coins and their inherent unfair distribution. I guess I need to go out more.
wildmanx 5y ago
For certain P, optimizations are possible. For example, with P=1/3, the general method discards TT (P=1/9) and HH (P=4/9) and repeats, while keeping HT and TH (P=2/9 each). One could optimize this by only discarding TT while returning 0 for TT (P=4/9) and returning 1 for HT and TH (P=2/9 each, together also 4/9). Generally we just want to partition the event space into three parts such that two are equally likely while the third one is used to "scratch that, just repeat". Keeping HT and TH guarantees that, but if you want to minimize retries, better solutions are possible.

95 points by leonry 5y ago

despite all the theoretical work, it's not physically possible to bias a coin to any notable degree. Unlike a die you can't weight one of the faces, you can bend the coin but it takes about a 90 degree bend in a coin to be able to say that a coin is biased with statistical confidence. Or in other words, if the coin appears reasonably flat, it's fair enough that you won't notice. https://izbicki.me/blog/how-to-create-an-unfair-coin-and-prove-it-with-math.html https://izbicki.me/blog/how-to-create-an-unfair-coin-and-pro... I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it.

nuclearnice1 5y ago
Interesting stuff! Instead of biasing the coin, consider unrandomizing the flip. Here’s one of many articles on Perci Diaconis trying just this https://www.ams.org/publicoutreach/math-history/hap7-fifty-one-percent.pdf https://www.ams.org/publicoutreach/math-history/hap7-fifty-o...
moron4hire 5y ago
It also assumes that the two "coins" are biased in the same way. If the two ostensibly-50/50 random events are not equally biased, von Neumann's algorithm doesn't work.
- mbokinala 5y ago
  I believe the steps said to toss the same coin twice.
  - madars 5y ago
    Yep. The assumption is that two flips are independent and identically distributed but that's a fair one: your flips don't change the coin, it does not have memory, etc.
    - dotancohen 5y ago
      Yes, flips do change the coin: they change which side is "up" at the moment of release. This could change the outcome of the flip.
- IncRnd 5y ago
  Exactly. The input is the issue, despite this method's claim to fix bias in the input. As you point out, this method works as a limited thought experiment but not in the real world. To make an extreme example, if someone can cause the sequence to contain strings of HHHT, this algorithm would absolutely bias towards returning H. So, the key to overcoming this algorithm is to inject a sequence that, regardless of which modulo 2 positition is A or B in the code, will tend to fall on such an input bias. The point is that people trust code that says it fixes these sorts of things, so it is often easier than not to break the code by controlling the input. There are other methods used in the real world when ingesting random bit sequences.
  - eru 5y ago
    Yes. Von Neumann's method is definitely not safe against adversarial input.
    - IncRnd 5y ago
      Correct, though this is often improperly left out of the threat model.
vikingerik 5y ago
How are we defining a notable degree? Even a 1% skew is tremendous - entire casino empires are built on that probability margin.
- godelski 5y ago
  You could calculate the likelihood over a certain distribution, in your case 1%. But when you do that you find that the third coin has a higher likelihood of being a fair coin than the first coin. That one has a pretty big bend in it. The ones after have a less than 4% chance of being fair. But to the OP's point, seeing that the third coin is more likely to be fair than the flat one (and is past a 45 degree angle) I think their claim makes sense with pretty good bounds.
  - mannerheim 5y ago
    To be fair, a 1% bias would probably not be detected in a hundred trials. CI for Bernoulli is +/- z * sqrt(p * (1-p) / n), so for a 95% confidence interval smaller than a percentage point, we have 1.96 * sqrt(p * (1-p) / n) = 0.01 0.5^2 / n = (0.01/1.96)^2 n = (1.96/0.01 * 0.5)^2 Or about 9604. So you need roughly 10k trials to determine with 95% confidence a bias of 1%.
- morelisp 5y ago
  Even a fair coin has a 51/49 skew in a normal flip. https://epubs.siam.org/doi/abs/10.1137/S0036144504446436?journalCode=siread https://epubs.siam.org/doi/abs/10.1137/S0036144504446436?jou... But bending/weighting won't change that.
monkeycantype 5y ago
It depends how you flip it. If you spin a coin on the table, it seems like it should be fair, but small weight differences make a huge difference. If you try with an Australian 20c it's nowhere near 50:50, closer to 70:30 (heavy is the head that wears the crown apparently - from memory its the queen's head side that end up down and the platypus comes out on top.)
- russfink 5y ago
  And what if you flip it over turf, e.g. at a large stadium during a huge televised sporting event? The implications on all of it are pretty big.
  - alisonkisk 5y ago
  - IncRnd 5y ago
    Like in this CBS news report that caught a coin landing on its edge in a soccer game? https://www.youtube.com/watch?v=Sz3VwRLsfX0 https://www.youtube.com/watch?v=Sz3VwRLsfX0 There very well be refs who can take advantage of coin flips over time.
r00tanon 5y ago
If the coin is thinner on one side, then it will fall on its edge more often? If the coin has an offset hole in the middle? A triangular coin? With an offset hole in the middle? Include thinner condition on the last three.
dchftcs 5y ago
The theoretical possibility of generating unbiased random bits from biased ones has critical practical implications. In computers we need unbiased random bits all the time but often only have biased sources.
- eru 5y ago
  Definitely. And the commenter you replied to knows that. See https://news.ycombinator.com/item?id=30696269 https://news.ycombinator.com/item?id=30696269 for how you can improve on von Neumann's technique and still stay provably unbiased in your output.
jchonphoenix 5y ago
You and your article are wrong. Place extra metal on one side near and edge and run the experiment again. All because you can't imagine a way to do it doesn't mean it can't be physically done. This is a lesson kids. Randos on the internet can be wrong. Even with high conviction
jorvi 5y ago
> Unlike a die you can't weight one of the faces You can just glue a weight to one side of the faces at an offset.
IncRnd 5y ago
> despite all the theoretical work, it's not physically possible to bias a coin to any notable degree. > I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it. That's a case of working from false assumptions that aren't necessarily true in practice. The way to make a coin flip fair is to control as many variables as possible during the flip and landing - because that is what is done by people who bias the flip. Only one of these variables is the coin itself. Bias sometimes exists in the apparatus around the coin. After all some historical coins have ferrous metal in them, as the simplest example. Bias can also be introduced by the people performing the flips. For example, there are people who can flip a coin onto its edge or with an outcome biased towards heads or tails. A flip onto the coin's edge can even be done by an amateur. [1] After all, even without bias a coin can land on its edge. See this CBS News video from a Soccer game's ref flipping a coin. [2] [1] https://www.youtube.com/watch?v=M0I-xm7iCBU https://www.youtube.com/watch?v=M0I-xm7iCBU. [2] https://www.youtube.com/watch?v=Sz3VwRLsfX0 https://www.youtube.com/watch?v=Sz3VwRLsfX0

sidedishes 5y ago

A similar cute trick for making a coin with arbitrary bias p out of a fair coin: go through the (possibly infinite) binary expansion of p, flipping once for each digit. If you flip tails on a 1 or heads on a 0, go to the next digit and repeat. If you flip heads on a 1 or tails on a 0, stop and take that as your flip. (And if you get to the end of the expansion, you can think of it as only 0s now, so interpret it as tails)

peeters 5y ago
This doesn't seem quite right, unless I'm misunderstanding. If your bias was 128 (10000000) by your algorithm you would get heads at least 50% of the time (heads on the first flip) and tails at least 25% of the time (heads then tails). I think instead of taking the "wrong" flip result when they don't match, you should treat "getting to the end" as heads and failing before that as tails (or vice versa).
- klipt 5y ago
  p is a probability in range [0, 1]. So if p = 1/128, the expansion is 0.0000001. In this case the algorithm says you return tails unless you flip 7 heads in a row (which happens with probability 1/128).
  - peeters 5y ago
    Ah thanks for the explanation. Makes a lot more sense with the fractional expansion.
klipt 5y ago
Intuitively, you're building a random real number in the range [0, 1) bit by bit, and returning 0 or 1 once you're sure that number is above or below threshold p.
eru 5y ago
That's basically how arithmetic coding works, isn't it? https://en.wikipedia.org/wiki/Arithmetic_coding https://en.wikipedia.org/wiki/Arithmetic_coding

Animats 5y ago

That's useful when you want random bits from a pulse noise source, such as radioactive decay. Count pulses over a period of time, and take the last bit of the count. Do this twice. 10 => 1, 01 => 0, 00, 11 => retry. It seems to be a corollary that you cannot get random bits at a guaranteed rate that way.

klipt 5y ago
Doesn't that assume the distribution at time 1 is also the distribution at time 2, which isn't entirely true since the source is already sightly less radioactive then?
- Animats 5y ago
  That's a good point. The effect is small but nonzero.
- teraflop 5y ago
  Still works, with a slight variation: instead of taking two measurements, you can take four successive measurements [A,B,C,D] over equal periods of time, and then do the aforementioned procedure with the values A+D and B+C as input. If the activity is decreasing at a linear rate, then A+D and B+C should have exactly the same distribution. In reality, they will be ever so slightly different because the decay is exponential rather than linear, but over short periods of time (compared to the half-life) the linear approximation is extremely good.
  - OscarCunningham 5y ago
    https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Equitable_sequencing https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Eq...
- tedunangst 5y ago
  Coin flips aren't fair either, because gravity will change slightly between successive flips.

hackernewsb 5y ago

I have a generally-applicable approach, i.e., a coin with any number of sides and any probabilities. Here we go, in the spirit of brute force: 0. Train your wrist, 'cause you'll be flipping this a gazillion times (say just N times) 1. Enumerate all possibilities, i.e., sample space = {H, T}^N 2. Compute the probabilities of each. 3. Partition the sample space into two such that the total probability (sum of probabilities) is equal to 0.5. 4. Call one element of the partition heads and the other tails. 5. Want a "multi-sided-coin"? Go back to step 3 and create a finer partition.

eru 5y ago
How do you partition the sample space in step 3 without knowing the bias of the coin? If you squint right, I described a method in https://news.ycombinator.com/item?id=30696269 https://news.ycombinator.com/item?id=30696269 for how to do just that. But I wonder whether you have a different method in mind?

fennecs 5y ago

Makes me think of some sort of symmetrisation. So for a 6 sided dice, you roll it 6 times in a row. You discard your 6 rolls unless you get a permutation of {1,2,3,4,5,6}, and in that case pick one of the rolls consistently, eg the first or the last.

sideshowb 5y ago
You're going to need a lot of rolls though. It'll be quicker to decide e.g. Heads is 123, tails is 456 and use Von Neumann's approach. If you already have a rough estimate of the bias you could even pick different faces for heads/tails to get p as close to 0.5 as possible before you start, again reducing the number of throws.
- wildmanx 5y ago
  The point was to make the die roll unbiased, not to convert it into a unbiased coin toss.
  - sideshowb 5y ago
    Fair point Though I suspect still quicker to convert to unbiased coin toss and use those as the bits of a number in the desired range than to wait for a permutation of 123456
    - eru 5y ago
      Especially if eg 5 had an extremely low probability of showing up. Or perhaps even 0% probability.

odyssey7 5y ago

What if the coin's bias changes from flip to flip, perhaps influenced by its earlier results? Is there a solution for this?

LeonB 5y ago
Without knowing what sort of influence it has — it’s difficult to construct a general method, though, please check my idea and see if this achieves the purpose. First you find a gambler, any gambler and ask them to show you the lowest denomination coin they have, and get them to verify for you that it is a fair coin. Now demonstrate your weird coin to them, and when they are amazed by its properties, swap it with them for the fair coin. Done.
paxys 5y ago
This makes me think – is a coin with a truly random bias from flip to flip any different from a perfectly fair coin?
- mannerheim 5y ago
  Depends on what you mean by 'truly random'. A distribution can be skewed, in which case the bias would itself be biased and then clearly different from a perfectly fair coin. Assuming you mean a uniform distribution, we can calculate this. Been a while since I've done stats, so bear with me... We can first argue from symmetry that we should expect as many heads as tails. But this doesn't mean that this is necessarily the same distribution as a perfectly fair coin (Bernoulli with p = 0.5). Anyway, the distributions we have here are a Bernoulli distribution and a uniform distribution X ~ {0, 1}; 0 with probability 1-q, 1 with probability q q ~ [0, 1], uniformly The expected value of X is E[X] = 0 * p(0) + 1 * p(1) = p(1) I think we could prove p(1) = E[q], but I'm honestly not sure, and don't know if that holds up in general. But from the above, we know it's 0.5 anyway. Now, we need higher moments: E[X^n] = 0^n * p(0) + 1^n * p(1) = p(1) = 0.5 The moment generating function of a probability distribution is defined as M_X(t) = E[e^(tX)]. There's a theorem in probability that two distributions with the same MGF are the same. You can see from the above that this has the same moments as a Bernoulli distribution with p = 0.5. Hence, a biased coin with a random uniform bias should be identical to a Bernoulli distribution. In fact, I believe the above argument works for not just uniform bias, but any random bias that is symmetric about p = 0.5.

sjaak 5y ago

See also the paper "Streaming Algorithms for Optimal Generation of Random Bits" https://arxiv.org/pdf/1209.0730.pdf https://arxiv.org/pdf/1209.0730.pdf

eru 5y ago
Ha, I should have read your comment before typing out my home-grown method in https://news.ycombinator.com/item?id=30696269 https://news.ycombinator.com/item?id=30696269 Thanks for the link!

eru 5y ago

Von Neumann's solution is clever, but extremely inefficient in terms of how many flips you need per random bit produced. More interesting methods produce a stream of unbiased random bits out of a stream of flips; and you can look at the asymptotic efficiency. A simple method to run better than von Neumann's method: Produce 1,000 coin flips. Say you produce k heads and 1,000-k tails. Produce a table of all possible sequences of length 1,000 with k heads and 1,000-k tails. Look up the position of your actual realized sequence in that table. The index of that position is a uniform random integer in a range from 1 to the size of the table. Use your favourite method to extract unbiased bits from that unbiased integer. The only requirement to make the above method work is that coin flips are i.i.d., ie independent and identically distributed. (In practice you probably don't want to actually construct the table, but instead compute the index directly as-if you had constructed the table. You might also want to work with arbitrary number of flips, instead of a fixed 1,000; or even adopt the method to an arbitrary length stream of coin flips that you don't know in advance. Also in practice, you don't need to store the whole sequence. What you do is keep a count of how many heads and tails you've seen so far, but feed the individual coin flips into an 'entropy pool'. Your head/tail count will inform your estimate of how many bits of entropy you have in your pool. (It basically feeds into the formula for how many possible orders of arrangement you have, similar to the fixed-size method suggested above.) You generate your unbiased bits by draining the from the entropy pool. The method of entropy pools described here is pretty much how /dev/random works on Linux.)

jagged-chisel 5y ago
> Produce a table of all possible sequences of length 1,000 with k heads and 1,000-k tails. This is more efficient than Von Neumann?
- dmurray 5y ago
  More efficient if coin flips are your scarce resource, less efficient if computation is scarce. But nowhere near as inefficient as it sounds - you don't actually have to materialize the table.
- steerablesafe 5y ago

alberto_ol 5y ago

Original Von Neumann paper, the method is described in the second paragraph: https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf https://mcnp.lanl.gov/pdf_files/nbs_vonneumann.pdf

amitport 5y ago

I would say that the second coin is unfair but it's not "unbiased" in the statistics sense. It has an expected mean and taking the sample mean of flips will converge to it.

riccardomc 5y ago

I thought this was about _crypto_ coins and their inherent unfair distribution. I guess I need to go out more.

wildmanx 5y ago

For certain P, optimizations are possible. For example, with P=1/3, the general method discards TT (P=1/9) and HH (P=4/9) and repeats, while keeping HT and TH (P=2/9 each). One could optimize this by only discarding TT while returning 0 for TT (P=4/9) and returning 1 for HT and TH (P=2/9 each, together also 4/9). Generally we just want to partition the event space into three parts such that two are equally likely while the third one is used to "scratch that, just repeat". Keeping HT and TH guarantees that, but if you want to minimize retries, better solutions are possible.