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.
