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 you have an "unfair" coin, that lands heads with probability $p\in(1/2,1]$ (where $p$ is known to you). You are given some $\epsilon>0$, and want to demonstrate to someone that this coin is not fair with confidence $1-\epsilon$, using as few flips as possible. What is the optimal method for doing this?

Formally, this is what I mean: define $X=\{H,T\}^\omega$, the space of infinite sequences consisting of heads and tails. This space has two probability measures on it: $\mu_p$, the probability measure coming from the unfair coin, and $\mu_{1/2}$, the probability measure that would come from a fair coin. We choose an event $E\subset X$ satisfying $\mu_{1/2}(E)\leq \epsilon$, and define a function $f_E:X\to \mathbb{Z}_{>0}\cup\{\infty\}$, $$ f(a_1,a_2,\ldots)=\inf \{n:(b_1,b_2,\ldots)\in E\text{ whenever }b_1=a_1,\ldots,b_n=a_n\}. $$ Thus $f(a_1,a_2,\ldots)$ is the number of coin flips required to establish that $(a_1,a_2,\ldots)\in E$. In particular, $f(a_1,a_2,\ldots)=\infty$ if $(a_1,a_2,\ldots)\not\in E$. We would like to choose $E$ so that the quantity $$ \int_X f(x)\,d\mu_p(x) $$ is finite and as small as possible.

One possibility is to take $$ E=\{(a_1,\ldots):\exists N\geq N_0\text{ s.t. }\#\{n\leq N:a_n=H\}>\frac{\frac{1}{2}+p}{2}N\}, $$ where $N_0$ is chosen to be sufficiently large (depending on $\epsilon$). In other words, we flip at least $N_0$ times, the stop when the proportion of heads is closer to $p$ than to $\frac{1}{2}$. By choosing $N_0$ sufficiently large, we will have $\mu_{1/2}(E)\leq \epsilon$, and I believe we also get $\int_X f(x)\,d\mu_p(x)<\infty$. It seems clear that this choice of $E$ is not optimal, however.

share|improve this question
    
I'm a little confused, what if you set $n=\lceil\dfrac{-\log(\epsilon)}{\log 2}\rceil$ and let $E$ be the event that there are no heads in the first $n$ tosses. Obviously this isn't what you want, but you haven't dismissed it. Do you require $\mu_p(E)=1$? –  Tim Jun 23 '13 at 18:36
    
@Tim We have $f(x)=\infty$ for $x\not\in E$, so if $\mu_p(E)\neq 1$, then $\int f(x)\,d\mu_p(x)=\infty$. –  Julian Rosen Jun 23 '13 at 20:30

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.