3 ms·

The tornado trick doesn't work if you don't combine it with the Von Neumann trick, though. > What we’re going to do is take 5 coins, ideally all of different s

The tornado trick doesn't work if you don't combine it with the Von Neumann trick, though. > What we’re going to do is take 5 coins, ideally all of different shapes and sizes, and put them into a large cup. You want the cup to be large so that as you shake the coins around, the coins get jumbled in a highly random way. Give the cup 5 good shakes where the coins are tumbling around, and then dump the coins out and count the number of heads. If there are an even number of heads, record a ‘0’ for the random bit. If there are an odd number of heads, record a ‘1’ for the random bit. Consider the extreme case where all of the coins have a 0.1% chance of coming up heads: you have a 99.501% chance of getting 5 heads (odd), 0.498% chance of getting 4 heads and 1 tails (even), a 0.001% chance of getting 3 heads and 2 tails (odd), and a vanishingly small chance of getting 3 or more tails. So if you use the tornado trick with 5 coins that biased, your "random" bitstring is going to look something like "11111111111111...".

Taek 6y ago
If your coins are 99.9% biased it means you are going to need more than 5 coins. Bias approaches zero exponentially fast as you add more coins, and in this case it means you'd need 1151 coins at 99.9% bias per coin to have a simulated coin with a bias of less than 55%. At 99% bias per coin you only need 114 coins, and at 90% bias you only need 11 coins. The main difference between the tornado trick and the von Neumann trick is how well they work in practice. In practice, coin tosses have at least a small amount of correlation, which breaks the von Neumann trick and gives you sloppy entropy. In the degenerate case, you might end up with almost no randomness despite using the von Neumann trick. In practice, coin flips in the tornado have a bias that is around 55% per coin, which means that 5 coins is more than enough to give you reliable entropy. The tornado trick is about trying to fit into the real world well, which means discarding fears of using coins that are 99.9% biased towards a particular outcome, since coins like that don't exist in common contexts.

Taek 6y ago

If your coins are 99.9% biased it means you are going to need more than 5 coins. Bias approaches zero exponentially fast as you add more coins, and in this case it means you'd need 1151 coins at 99.9% bias per coin to have a simulated coin with a bias of less than 55%. At 99% bias per coin you only need 114 coins, and at 90% bias you only need 11 coins. The main difference between the tornado trick and the von Neumann trick is how well they work in practice. In practice, coin tosses have at least a small amount of correlation, which breaks the von Neumann trick and gives you sloppy entropy. In the degenerate case, you might end up with almost no randomness despite using the von Neumann trick. In practice, coin flips in the tornado have a bias that is around 55% per coin, which means that 5 coins is more than enough to give you reliable entropy. The tornado trick is about trying to fit into the real world well, which means discarding fears of using coins that are 99.9% biased towards a particular outcome, since coins like that don't exist in common contexts.