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.

An unfair coin is tossed giving heads with probability $p$ and tails with probability $1-p$. How many tosses do we have to perform if we want to find $p$ with a desired accuracy?

There is an obvious bound of $N$ tosses for $\lfloor \log_{10}{N} \rfloor$ digits of $p$; is there a better bound?

share|improve this question
    
Can you explain the obvious bound? I'm curious. –  GWu Apr 13 '11 at 14:35
    
@GWu: $\lfloor\log_{10}{N}\rfloor$ is how many decimal digits number $1/N$ has. It is also how much a $N$th toss will influence your knowledge of $p$. –  Eelvex Apr 13 '11 at 15:18

3 Answers 3

This is a binomial distribution. The standard deviation on the number of heads is $\sqrt{Np(1-p)}$, so leaving aside the difference between your measured $p$ and the real $p$ you need $N \gt \frac{p(1-p)}{accuracy^2}$

share|improve this answer
    
But I don't know $p$; I want accuracy as a function of $N$ only. –  Eelvex Apr 13 '11 at 14:24
3  
@Eelvex: The function is maximised when $p=1/2$ so use that. If you want accuracy to mean $k$ standard deviations rather than just 1, take $N > \left(\dfrac{k}{2 \times \text{accuracy} }\right)^2$. –  Henry Apr 13 '11 at 14:49

There is no way to find $p$ by tossing the coin with an accuracy like for the deterministic problems. That's a Monte-Carlo simulation and hence you better use bounds for these methods. Note that these bounds are probabilistic. E.g. $$ \mathsf{P}(|p-\hat{p}_n|>\delta)\leq 2\mathrm{e}^{-2n\delta^2} $$ where $\hat{p}_n$ can be obtained as a frequency of heads from tossing the coin $n$ times, i.e. $$ \hat{p}_n = \frac{1}{n}\#( \text{heads in the tossing sequence} ). $$

share|improve this answer

Your 'obvious bound' is incorrect. You cannot place absolute bounds on the value of p, regardless of the size of N.

However, as you increase N, your confidence improves in your calculated $p=N_{heads}/N$. Theoretically, though improbably, you could get 250 heads from 1000 throws of a fair coin.

You need to carry out a hypothesis test under the binomial distribution using a confidence interval of your choosing.

share|improve this answer

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.