Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
As a function of $p$? –  deinst Mar 26 '12 at 20:41
    
For which simulation algorithm? –  Did Mar 26 '12 at 20:58
    
DidierPiau: Not a specific kind, just to find out a lower bound –  Mathematics Lover Mar 26 '12 at 21:22
    
$1$ is a lower bound; $2$ is an upper bound for the expectation. What do you mean by the lower bound? –  Henry Mar 26 '12 at 21:42
1  
I guess you are looking for entropy, 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?) –  dtldarek Mar 26 '12 at 23:14

2 Answers 2

This answer concerns the maximal (rather than expected) number of tosses; which is not what is asked for.


After flipping a fair coin $n$ times, you have $2^n$ equally likely outcomes. Every event defined in terms of these outcomes has probability $k/2^n$ for some $k\in\{0,\dots,2^n\}$. And conversely, for every $k$ there is such an event. Conclusion:

Required number of flips is $ \inf\{n: 2^np\in\mathbb Z\}$.

Which is infinite when $p$ is not a dyadic rational; meaning that for such $p$ you can't simulate the biased coin at all.

Example: if $p=0.375$, you need $3$ flips.

share|improve this answer
1  
This is not correct: note that the problem says "expected number of coin flips". E.g. you can simulate a biased coin with $p = \frac13$ (which is not a dyadic rational) by the process of flipping a coin twice, saying "heads" if you see "HH", "tails" if you see "HT" or "TH", and repeating the experiment if you see "TT". This has probability $\frac14$ of requiring yet another pair of flips, but the expected number of coin flips to terminate is $\frac43 (2) = 8/3$, not infinite. See e.g. this question (there are probably others too on math.SE). –  ShreevatsaR Jul 16 '13 at 4:18
    
@ShreevatsaR Good point; would you like to give a correct answer to this question? –  40 votes Jul 16 '13 at 4:21

If you expand $p$ in binary, then take head of your flips as a $1$, tail as a $0$, you can state head or tail as soon as you disagree with $p$. There is no lower bound, as the sequence of flips could match the expansion of $p$ as long as you want. Say $p=\frac 13=0.01010101\overline{01}_2$. As long as you alternate tails and heads you can't tell. With probability $1$ that will stop sometime. The expected number of flips is $\sum_{i=1}^{\infty} \frac i{2^i}=2$

share|improve this answer
    
Lower bound on the expected number of the flips is what the problem asks for. Did you mean "there is no upper bound"? (Which also should exist (in terms of $p$), I guess?) And are you saying that that the expected number of flips is $2$ irrespective of the value of $p$? Something seems wrong with that... I haven't thought through this clearly, but e.g. if $p = \frac1{100}$ I suspect we'll need at least 7 flips (and probably more). –  ShreevatsaR Jul 16 '13 at 5:27
    
Actually now I understand why you say there is no lower bound: in the case of $p=\frac1{100}$ for instance, there is less information than in the $p=\frac12$ case, because most of the time we can just say "tails". (I was earlier thinking of the $(\frac1{100}, \frac1{100}, \dots, \frac1{100})$ distribution rather than the $(\frac1{100}, \frac{99}{100})$ distribution we care about here.) However, there is still a lower bound in terms of $p$, I think it's $H(p)/H(\frac12)$ i.e. $p\lg\frac1p+(1-p)\lg\frac1{1-p}$. This is $< 1$ though. –  ShreevatsaR Jul 16 '13 at 6:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.