World's most popular travel blog for travel bloggers.

Reference needed: lower bound on sample size for determining which side of coin is biased with high probability

, ,
Problem Detail:

I am looking for a reference to see if the following problem has been addressed before. Suppose we know that a coin is biased with probability $p>\frac{1}{2}$, but we are unsure if the coin is biased for heads or tails. I want to know a lower bound on a sample size $n$ needed to determine with high probability which side the bias is in favor of i.e. with probability at least $1-\delta$ so the answer would be $n=\Omega(g(p,\delta))$ or something like that.

Thanks for any help!

Yes. You need approximately $\sim 1/|p - 1/2|^2$ observations (that many are necessary and sufficient), assuming $p$ is close to $1/2$. I've omitted constant factors, but the constant is small. The exact constant will depend on the degree of confidence you want, but it will vary as something like $\log (1/\delta)$ (or lower): $\delta$ drops exponentially fast in the number of observations.

For more details and analysis, see http://cstheory.stackexchange.com/q/22328/5038. You might also be interested in http://cstheory.stackexchange.com/a/30938/5038.