Interview question of biased coin

Question

Here is a question of quantitative interview:

A, B are biased coins. Now we toss 100 times of A or B to determine which one has the larger probability of head. What's the optimal strategy?

Actually i don't much understand the word optimal, for my opinion, 50 times toss A and 50 times toss B then the one with large frequency of head has the large probability of head.

Answer 1

Nothing frustrates me more than when someone tells you to do the "optimal" thing without telling you the criteria over which to optimize. That being said, I'm betting that since it was an interview, they intended for you to determine what you wanted to optimize for.

Your approach might not be "optimal" if we wanted to optimize for statistical power. If the difference in bias is small, 50 flips might not be sufficient to detect which coin has larger bias.

I suspect they were hoping you knew about bandit algorithms. Given the constraint on flips and the goal of learning the coin with the largest bias, this sounds like an AB test one might run in industry. One way the algorithm is run is as follows:

• Start with uniform beta priors on each on the biases of the coin
• Draw from those priors and select the coin who's draw was largest.
• Flip the coin and update the priors (now posteriors)
• Repeat

Here is a python implementation of the bandit. The two coins have a bias of 0.4 and 0.6 respectively. The bandit correctly identifies that coin 2 has the larger bias (as evidenced by the posterior concentrating on larger biases.

import numpy as np
from scipy.stats import beta, binom
import matplotlib.pyplot as plt

import numpy as np
from scipy.stats import beta, binom
import matplotlib.pyplot as plt

class Coin():
    
    def __init__(self):
        self.a = 1
        self.b = 1
    def draw(self):
        return beta(self.a, self.b).rvs(1)
    def update(self, flip):
        if flip>0:
            self.a+=1
        else:
            self.b+=1
    def __str__(self):
        return f"{self.a}:{self.b}={self.a/(self.a+self.b):.3f}"



#Unknown to us
np.random.seed(19920908)
coin1 = binom(p=0.4, n=1)
coin2 = binom(p=0.6, n=1)


model1 = Coin()
model2 = Coin()

for i in range(100):

    draw1 = model1.draw()
    draw2 = model2.draw()

    if draw1>draw2:
        flip = coin1.rvs()
        model1.update(flip)
    else:
        flip = coin2.rvs()
        model2.update(flip)


        
x = np.linspace(0,1,101)

plt.plot(x, beta(model1.a, model1.b).pdf(x))
plt.plot(x, beta(model2.a, model2.b).pdf(x))
print(model1,model2)

Answer 2

in addition to the prior reply and useful comments, and to answer the actual question, the best approach is leveraging Thomson Sampling, there is an excellent article on sudeepraja's blog.

it iteratively samples from the current posterior, selecting the highest mean.