Re:Make a Fair Coin from a Biased Coin (2018)
by moron4hire on Tuesday March 15, 2022 @11:00PM
(#30694847)
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.
[ Parent
| on HN ]
Re:Make a Fair Coin from a Biased Coin (2018)
by mbokinala on Tuesday March 15, 2022 @11:24PM
(#30695001)
I believe the steps said to toss the same coin twice.
Re:Make a Fair Coin from a Biased Coin (2018)
by madars on Wednesday March 16, 2022 @01:29AM
(#30695634)
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.
Re:Make a Fair Coin from a Biased Coin (2018)
by dotancohen on Wednesday March 16, 2022 @04:39AM
(#30696566)
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.
Re:Make a Fair Coin from a Biased Coin (2018)
by IncRnd on Wednesday March 16, 2022 @12:39AM
(#30695377)
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.