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.

Suppose I flip coins until either the first coin comes down head or I have flipped 10 coins, all of which came down tail. How many times do I flip coins in expectation?

Is there a closed form expression for the expected number of trials for arbitrary success probabilities and upper bound on the number of trials?

In the example, the distribution of the number of trials approaches a geometric distribution with mean 2 when I continue flipping coins longer and longer. For the example, the expected number of trials is $\frac{509}{256}$, which is, unsurprisingly, smaller than $2$.

share|improve this question
1  
$\sum_{n=1}^N p(1-p)^{n-1}$ with $p$ being the probability of head coming up and $N$ the number of rounds. –  Michael Greinecker Apr 8 '12 at 0:05
    
Thank you. Yes, that is the correct explicit summation. Now: Is there a way to simplify the formula, without involving the summation? Ideally, is there a reference? –  Stephan Apr 8 '12 at 0:16

1 Answer 1

up vote 3 down vote accepted

If you flip a coin with success probability $p$ until the first success, you expect $1/p$ trials. The probability for not getting a success in $n$ trials is $(1-p)^n$. If you stop after $n$ trials, you reduce the expected number of trials by $1/p$ with probability $(1-p)^n$. Thus the expected number of trials becomes $(1-(1-p)^n)/p$.

share|improve this answer
    
This answer provides a very good approximation. Also, you give a very clever argument (I found the approximation somewhat more clumsily). In the example, the expected number of trials is 1.9883... and the formula that you give approximates this number well as 1.998. However, this formula does not provide an exact solution. –  Stephan Apr 8 '12 at 0:23
    
@Stephan: I would think that since I showed the courtesy of providing an argument, you might also show the courtesy of providing an argument if you're going to claim in boldface that my answer is wrong? –  joriki Apr 8 '12 at 0:27
    
Sorry, one second –  Stephan Apr 8 '12 at 0:29
    
Sorry. I do mean that this is a good approximation and I like the argument. I don't have an explicit argument why the formula does not work. However, I computed the expected number of trials in the example (using matlab) and then compare the computed number with the number from your formula. –  Stephan Apr 8 '12 at 0:31
1  
@Stephan: Then perhaps you could share your Matlab code? I don't see where my argument could go wrong, and $509/256=2-3/256$ doesn't feel right; I don't see how the $3$ could arise. Also, you could try some easier examples first, with $n=1,2,3$ -- as far as I can tell, my answer is correct for those, and it seems very unlikely that it could start going wrong only for higher $n$. –  joriki Apr 8 '12 at 0:32

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.