Finding a rare biased coin from an infinite set

Question

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.

Answer 1

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.)

Answer 2

I'll interpret the problem this way . . .

A bucket of coins is such that

• Some coins are biased, the rest are fair, but the coins are physically indistinguishable.$\\[4pt]$
• The fraction of coins which are biased is equal to $t$, with $0 < t < 1$, and where the value of $t$ is known.$\\[4pt]$
• For each of the biased coins, the probability of heads is $p$, with $0 < p < 1$ and $\;p\ne{\large{\frac{1}{2}}}$, and where the value of $p$ is known.

Fix an acceptance threshhold $a$, with $0 < a < 1$.

Initialize a flip counter to zero.

A game is played as follows . . .

Selecting a coin at random from the bucket, you can flip it repeatedly until you either

• Decide to reject the coin, putting it back in the bucket, then starting over, but not resetting the flip count back to zero.$\\[4pt]$
• Accept the coin, ending the game, and declaring that, based on the results, the conditional probability that the coin is biased is at least equal to $a$.$\\[4pt]$

The objective is to choose a strategy which minimizes the expected flip count.

Such a strategy can be described as follows . . .

• Select a coin at random from the bucket.$\\[4pt]$
• After each flip of the selected coin, compute, based on the results so far, the conditional probability, $b$ say, that the coin is biased.$\\[4pt]$
• If $b\ge a$, accept the coin, else if $b < t$, reject the coin.

As a numerical example, for the values

$$ t=\frac{1}{4},\;\;\;\;p=\frac{3}{4},\;\;\;\;a=\frac{9}{10} $$

the above strategy, based on a Maple simulation (shown below), yields an expected flip count of about $42$.