4 ms·
> As an example, let’s take 2 coins that each have a bias of 75%. The ‘distance from unbiased’ for each coin is 0.25. We double that for each coin to get 0.5, t
by ballenf 6y ago
> As an example, let’s take 2 coins that each have a bias of 75%. The ‘distance from unbiased’ for each coin is 0.25. We double that for each coin to get 0.5, then we multiply them together to get 0.125. Finally, we add 0.5 to get 62.5%. The full equation would be (0.5 + (2x0.25)x(2x0.25)) = 62.5%.
I think the answer here would be 75%, no? 0.5 x 0.5 = .25 not .125, or am I missing something? Maybe the example was supposed to have 3 coins -- then the math would work.
Does that result somehow make sense in that each coin is halfway to being completely biased?
The strange thing in that formula is seen with 2 80% biased coins. You end up with a total bias of 86%. Which goes counter to the idea that mixing biased coins is always an improvement.
- dragontamer 6y agoSomething strange is going on in that paragraph for sure. Its not very rigorous. Lets start with a more rigorous approach: E(heads) == .75 on a biased coin. Maybe with 100-coin flips, with an average of 75-heads. We have a normalish-distribution centered around 75 where we can still draw a good random number from. It probably wouldn't be too hard to "subtract 25" after 75-flips and get something less biased as a result. That's the idea anyway. Variance of a single coin flip, or variance(heads) == .75 * .25 == 0.1875. Honestly, I'm not sure where that 62.5% figure comes from at all.
- Taek 6y agoedit: Math mistake in the blog post, now fixed and updated. I was missing a '1/2' that you have to multiply the entire product of the coins by. -------- old comment enumerating all possibilities: You can see the example is correct by enumerating all possibilities. For coins with a 75% bias, you can represent the possible outcomes by "HHHT". Which means the set of possible outcomes for 2 such coins is: HHHT x HHHT = HH HH HH HT HH HH HH HT HH HH HH HT TH TH TH TT That's 10 instances of HH/TT and 6 instances of HT/TH, or a simulated coin with a 10/16 chance of heads = 0.625 bias. Two 80% coins looks like: HHHHT x HHHHT HH HH HH HH HT HH HH HH HH HT HH HH HH HH HT HH HH HH HH HT TH TH TH TH TT Which results in 17/25 outcomes as 'heads', or 68% bias for the simulated coin. Which supports the statement that mixing biased coins is always an improvement.
- tubbyjr 6y agoWell yes, but actually no (0.5 + (2x0.25)x(2x0.25)) != 62.5% Your math there doesn't add up... quite literally
- dragontamer 6y ago> For coins with a 75% bias, you can represent the possible outcomes by "HHHT" Your method seems to lack rigor. Lets take a fair D4 (https://en.wikipedia.org/wiki/Four-sided_die https://en.wikipedia.org/wiki/Four-sided_die), and define "Heads" as 1, 2, 3, and 'Tails" and 4. This gives us a perfectly biased 75% Heads coin. The possibilities are: * Heads: 75% of the time (123) * Tails: 25% of the time (4) -------- With two "flips" of this D4, we've got: * HH -- 56.25% (11, 12, 13, 21, 22, 23, 31, 32, 33) * HT -- 18.75% -- Von Neuman Heads (14, 24, 34) * TH -- 18.75% -- Von Neuman Tails (41, 42, 43) * TT -- 6.25% (44) --------- The Von Neuman Method throws away the TT and HH possibilities, leaving an 18.75% chance of heads and an 18.75% chance of tails. The HH and TT require a "reroll". Thus, we've removed the bias of the dice. In any case, by giving every state an equal chance and a specific name (11, 12, 13...), we have a more rigorous count of the possibilities. I don't know where your method went wrong... but clearly something is off.
- Taek 6y agoI think you've misunderstood my method. We aren't using the Von Neumann extractor here, we're counting the total number of heads and saying "heads" for the result if the count is even, and "tails" of the result is odd. With your D4, that means the HH and TT both count as heads - 62.5% total, which is consistent with everything else.