Hacker News Reader

Comment by paulmd | Hacker News Reader

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-pro...

I get the idea as shorthand for a binary outcome, but the way you make a coin fair is to flip it.

View on HN

How are we defining a notable degree? Even a 1% skew is tremendous - entire casino empires are built on that probability margin.

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.

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%.

Even a fair coin has a 51/49 skew in a normal flip.

https://epubs.siam.org/doi/abs/10.1137/S0036144504446436?jou...

But bending/weighting won't change that.

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.)

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.

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

There very well be refs who can take advantage of coin flips over time.

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.

Definitely. And the commenter you replied to knows that.

See 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.

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-o...

> 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.

[2] https://www.youtube.com/watch?v=Sz3VwRLsfX0

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.

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.

I believe the steps said to toss the same coin twice.

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.

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.

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.

Yes. Von Neumann's method is definitely not safe against adversarial input.

Correct, though this is often improperly left out of the threat model.

> 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.

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

Reply on news.ycombinator.com