1
$\begingroup$

If we have an unbiased coin and we want to generate a biased coin with probability $p$ of getting a head and $1-p$ of getting a tail. What is the lower bound of the expected number of flips that generating this biased coin?

  • 0
    As a function of $p$?2012-03-26
  • 0
    For which simulation algorithm?2012-03-26
  • 0
    DidierPiau: Not a specific kind, just to find out a lower bound2012-03-26
  • 0
    $1$ is a lower bound; $2$ is an upper bound for the expectation. What do you mean by *the* lower bound?2012-03-26
  • 1
    I guess you are looking for [entropy](http://en.wikipedia.org/wiki/Entropy_%28information_theory%29), in such case you need $p\log_2 (p) + (1-p)\log_2(1-p)$ coin flips to get your result (note that for $p\in [0,1]$ the result is in $[0,1]$ too, i.e. for $p \neq 0.5$ you will need less than one coin flip). (In other cases, what happens if $p$ is transcendental?)2012-03-26

2 Answers 2