4 ms·

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 be

by 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

by paulmd 5y ago

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