Coins and randomness

Reading suggestion - August 10, 2023

Randomness extraction based on von Neumann’s:

Various Techniques Used in Connection With Random Digits

Why: Classic topic relevant in many areas, learning, algorithmic information:

von Neumann’s biased coin revisited

and I have also touched on it in Equivalences between learning of data and probability

It is crucial for both practical applications and theory

Selection of articles on coin randomness:

• How to Turn Loaded Dice into Fair Coins

• Unbiased coin tossing with a biased coin

• Generating Random Bits from an Arbitrary Source

• You can load a die but you can’t bias a coin

• Independent unbiased coin flips from a correlated biased source

• Iterating von Neumann’s proceedure for random bits

• Tossing a Biased Coin - Problems

• Tree algorithms for coin tossing

• New Coins from Old, Smoothly

• Unbiasing Random Bits

• Blind-friendly von Neumann’s Heads or Tails

Related Code available online

Related and fun: strange coin probabilities

• Counterintuitive Probabilities in Coin Tossing

• Pattern matching probabilities and paradoxes