Skip to content

Instantly share code, notes, and snippets.

@pervognsen

pervognsen/von_neumann_bias.md

Last active November 9, 2023 09:51
Show Gist options
  • Save pervognsen/d9e6306555118a42953d5d2af9beb888 to your computer and use it in GitHub Desktop.
Save pervognsen/d9e6306555118a42953d5d2af9beb888 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
von_neumann_bias.md

Von Neumann is credited with a method for generating fair coin flips from repeated tosses of a bent coin with unknown probability p via rejection sampling: In each round, toss the bent coin twice. Map (heads, tails) to heads and (tails, heads) to tails. For (heads, heads) and (tails, tails), repeat the process.

Since (heads, tails) has probability p*(1-p) and (tails, heads) has probability (1-p)*p, this generates the same distribution as a fair coin flip, but the process has a random running time.

  1. What is the expected running time in number of rounds?
  2. If you forcibly terminate the process after n rounds and return heads/tails arbitrarily, what is the bias?
  3. If you're given a bound on p (say you know the bent coin is no more biased than p = 0.9) and a maximum tolerated bias for that generated output, what is the minimum value of n that reduces the bias below that level?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment