4 ms·

edit: 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 co

by Taek 6y ago

edit: 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 ago
Well yes, but actually no (0.5 + (2x0.25)x(2x0.25)) != 62.5% Your math there doesn't add up... quite literally
- deleted 6y ago
  [deleted]
- Taek 6y ago
  Ah whoops you have to multiply the whole product by 1/2. (0.5 + 1/2 * (coin product)) not (0.5 + (coin product)) Thanks for pointing out the mistake. I've edited the blog post accordingly.
  - tubbyjr 6y ago
    ty, great post other than that little issue
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 ago
  I 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.
- thaumasiotes 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. ...but that's exactly the same method you just complained lacked rigor. (It doesn't, but what were you complaining about?)

by Taek 6y ago

tubbyjr 6y ago

Well yes, but actually no (0.5 + (2x0.25)x(2x0.25)) != 62.5% Your math there doesn't add up... quite literally

deleted 6y ago
[deleted]
Taek 6y ago
Ah whoops you have to multiply the whole product by 1/2. (0.5 + 1/2 * (coin product)) not (0.5 + (coin product)) Thanks for pointing out the mistake. I've edited the blog post accordingly.
- tubbyjr 6y ago
  ty, great post other than that little issue

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 ago
I 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.
thaumasiotes 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. ...but that's exactly the same method you just complained lacked rigor. (It doesn't, but what were you complaining about?)