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?
Lower bound of generating a biased coin?
1
$\begingroup$
probability
-
0As a function of $p$? – 2012-03-26
-
0For which simulation algorithm? – 2012-03-26
-
0DidierPiau: Not a specific kind, just to find out a lower bound – 2012-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
-
1I 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