Hacker News new | ask | show | jobs
by stouset 779 days ago
Enlist my friends to flip more coins in parallel :)

At a high level I’d probably try and exploit the fact that every bit sequence with a given number of H and T has equal probability. e.g., HHHT HHTH HTHH THHH are equally probable and so can be mapped to four different values. That still only gets me 2 bits (50%) but other combinations (e.g., variations on HHTT) could get me log2(6) bits. I’m guessing with a higher number of flips I could extract (on average) more and more as a proportion. No clue what the asymptote would be.
1 comments
stouset 779 days ago
Thinking further, for N flips you get 0 bits of entropy for all H or all T. For all other sequences, you get log2(N choose count(H)) bits of entropy, and you can average the sum of these over N.

According to Wolfram Alpha this works as N gets larger but it’s not great. For 16 flips you get 9.5 bits of entropy, but hey at least I beat half! 32 flips gets you about 20 bits of entropy. By 64 flips you get 43 bits, and that’s approaching 2/3 efficiency. Maybe not so bad after all!

Going higher is a little tough since I’m on mobile but it starts crawling reaching only 71% efficiency by 1024 flips. I’m curious if it does actually asymptotically reach 100% efficiency (for a fair coin), even if quite slowly.

Edit: Playing more[1] it really seems to approach 72.1. I wonder if I can figure out the asymptote analytically…

[1] https://www.wolframalpha.com/input?i=sum+from+i=1+to+N-1+of+...

link
stouset 777 days ago
This kind of nerd-sniped me. I did find a closed-form solution, that relies on an identity mapping the product of successive factorials ("hyperfactorials") to the Barnes G-Function which is related to the Riemann Zeta Function at a level deep past my comprehension. Still, here's[1] the closed form solution which returns the number of bits of entropy able to be generated given some number of coin flips using this approach, assuming the coin is indeed fair. Divide by the number of flips again to get the efficiency.

Unfortunately, Wolfram Alpha isn't able to determine the limit of this function[2], and neither am I. :)

[1] https://www.wolframalpha.com/input?i2d=true&i=evaluate+Divid...

[2] https://www.wolframalpha.com/input?i2d=true&i=Limit%5BDivide...

link