How many extra flips?
As in this problem you have a possibly biased coin that you want to use to simulate a sequence of 5 independent fair coin flips.
You proceed as follows:
- Use the strategy described in my solution to generate the output of a single fair coin flip
- Repeat independently four more times (i.e. five time in all)
If, in reality, the coin is a fair coin , how many more times have you flipped the coin in expectation than you truly needed to? (i.e. What is the expected price in terms of flips, that you have paid on account of not knowing the true distribution?)
Follow up to this problem
Part of my Biased Coins set.
The answer is 15.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
As described here , use can use rejection sampling to simulate a single fair coin flip by flipping the (possibly biased) coin twice and outputting the outcome of the second coin flip, if the two are different. If the the two outcomes are the same you reject that pair and repeat. Each trial succeeds with probability 2 p ( 1 − p ) . The number of trials needed until you succeed follows a geometric distribution with this parameter, and therefore its expectation is 2 p ( 1 − p ) 1 . Since each trial has two coin flips, in expectation you need p ( 1 − p ) 1 coin flips to simulate a single fair coin flip .
Since we want to simulate 5 fair coin flips, we need p ( 1 − p ) 5 flips of the biased coin in expectation.
Now, since the coin is actually a fair coin p = 1 / 2 . Since a fair coin is fair (!) we only need to flip it 5 times. Instead, because we don't know it is fair, we are flipping it 20 times in expectation. That is 1 5 extra times.