Finding a rare biased coin from an infinite set

probability

I'm trying to develop an algorithm for finding biased coins. The basic problem formulation is this:

  1. There are an infinite number of coins
  2. Some proportion $t$ of the coins is biased (this number is known)
  3. All biased coins have the same probability $p_b$ of coming up heads (this number is also known)
  4. All other coins are fair
  5. Biased coins are otherwise indistinguishable from fair ones

The task is to find one biased coin, with some confidence, using the fewest number of coin flips.

I know the basic solution to a related problem, i.e. determining whether a single coin is biased. Following the formulation in https://en.wikipedia.org/wiki/Checking_whether_a_coin_is_fair, I can set my desired maximum error $E$ to be equal to $|p_b – 0.5|$ and use the equation $n = \frac{Z^2}{4E^2}$ to get the number of coin tosses $n$ required to determine whether the coin is indeed fair using a given $Z$ value.

However, I'm curious how the method might change given my formulation, where there are multiple coins and a known proportion are biased. A brute force algorithm, I suppose, would be to select a coin, flip it $n$ times, select another coin, flip it $n$ times, etc. until a biased one is found. But this feels sub-optimal.

Is it possible, for instance, to abandon a coin before $n$ flips is reached based on some criteria, i.e. using the evidence collected so far to judge whether it is worthwhile to keep flipping that coin or move on to another? It seems like the value of $t$, particularly if it is low, should be a useful prior that I can leverage.

I'm also concerned that if I test multiple coins, I am at risk of inadvertently finding significance where there is none.

Best Answer

Is it possible, for instance, to abandon a coin before n flips is reached based on some criteria, i.e. using the evidence collected so far to judge whether it is worthwhile to keep flipping that coin or move on to another? It seems like the value of t, particularly if it is low, should be a useful prior that I can leverage.

A Bayesian approach might go like this, for a single coin ... Let $\widetilde p$ be the unknown probability of success, with prior given by $P(\widetilde p =p_b)=t$ and $P(\widetilde p =1/2)=1-t$. Then the posterior, after $n$ conditionally i.i.d. tosses $X_1,...X_n$, with $k$ being the number of successes, is given by $$\begin{align} P(\widetilde p =p_B\mid X_1=x_1,...X_n=x_n) &= {P(X_1=x_1,...X_n=x_n\mid \widetilde p =p_B)\cdot P(\widetilde p =p_B)\over P(X_1=x_1,...X_n=x_n)}\\[3mm] &= {p_B^k(1-p_B)^{n-k}\cdot t\over P(X_1=x_1,...X_n=x_n)}\\ \\ \end{align}$$ and $$\begin{align}P(\widetilde p =1/2\mid X_1=x_1,...X_n=x_n) &= {P(X_1=x_1,...X_n=x_n\mid \widetilde p =1/2)\cdot P(\widetilde p =1/2)\over P(X_1=x_1,...X_n=x_n)}\\[3mm] &= {(1/2)^n\cdot (1-t)\over P(X_1=x_1,...X_n=x_n)} \end{align}$$

Then we could, for example, use the posterior odds-ratio, $$R:={P(\widetilde p =p_B\mid X_1=x_1,...X_n=x_n) \over P(\widetilde p =1/2\mid X_1=x_1,...X_n=x_n)}={p_b^k(1-p_b)^{n-k}\over(1/2)^n }{t\over 1-t}$$ with a decision rule like this:

$$\ \begin{cases}R>r &\implies \text{decide "biased"}\\ R<1/r &\implies \text{decide "unbiased"} \end{cases} $$ ... tossing until one alternative becomes sufficiently more probable than the other, as judged by some threshold ratio value $r$. To guarantee a bound on the number of tosses, one would probably want to set some maximum number $n_{max}$, such that if $n_{max}$ were ever reached without a decision being made, then a default rule would be applied to stop and decide in favor of whichever alternative had the higher posterior probability at that time. (A hybrid Bayesian-frequentist approach could also set $n_{max}$ based on the frequentist estimation value you quoted.)

EDIT:

Note that if we let $P_n := P(\widetilde p =p_B\mid X_1=x_1,...X_n=x_n)$ and subscript the corresponding $R$-value, then $R_n$ and $P_n$ are in 1-1 correspondence, each being an increasing function of the other:

$$P_n = {R_n\over R_n+1},\quad R_n = {P_n\over 1-P_n}.$$

Consequently the decision criteria can be written equivalently in terms of either quantity:

$$\text{using $(r_{lo}, r_{hi})$:}\quad\quad\begin{cases}R_n>r_{hi}\\[6mm] R_n<r_{lo}\end{cases}\iff\begin{cases}P_n>{r_{hi}\over r_{hi}+1}\\[3mm] P_n<{r_{lo}\over r_{lo}+1}\end{cases} $$ and $$\text{using $(p_{lo}, p_{hi})$:}\quad\quad\begin{cases}P_n>p_{hi}\\[6mm] P_n<p_{lo}\end{cases}\iff \begin{cases}R_n>{p_{hi}\over 1-p_{lo}}\\[3mm] P_n<{p_{lo}\over 1-p_{lo}}\end{cases} $$

I've written $lo$ and $hi$ quantities in case you want to explore setting the two criteria independently of one another, instead of my example above using $(r_{lo},r_{hi})=({1\over r}, r)\iff (p_{lo},p_{hi})=({1\over r+1},{r\over r+1})$. (E.g., @quasi's answer uses $(p_{lo},p_{hi})=(t, a)\iff (r_{lo}, r_{hi})=({t\over 1-t},{a\over 1-a})$ seeking to minimize the expected total number of flips required to decide that a biased coin has been found.)

Related Question