Double or nothing

05/07/2013 - 12:15pm
05/07/2013 - 1:10pm
Mark Huber (CMC)

Suppose you have a coin with an unknown probability $p$ of heads. Then if you wish to create a coin with probability $p(1 - p)$ of heads, you simply flip your coin twice and say "heads" if you get first a head and then a tail on your two flips. To get $2p - p^2$, again flip the coin twice, and say "heads" if you get at least one head on your two flips. Now suppose you want to get a $2p$ coin again only using flips of your $p$ coin. This is surprisingly difficult! I'll look at the current state of algorithms for this problem and discuss a pathway to faster methods. In addition, I will show how to reduce many $f(p)$ coin problems to the $2p$ problem, and present some applications to Monte Carlo integration that come directly from this doubling problem.

Millikan 208 (Pomona College)