# Interview question of biased coin

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.

• sounds like a multi-armed bandit question Oct 4, 2020 at 14:17
• The answer depends entirely on what you want to optimize. For example, treating this as a bandit problem (as others have suggested) tries to maximize the number of times you flip the 'greater' coin. On the other hand, if you want to minimize uncertainty about the probabilities (i.e. maximize information gained about the parameters), you could treat this as an active learning problem. Oct 4, 2020 at 19:46

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)


• Ba+=1 A = beta(Aa, Ba) here should Ba be Ab? And why do we use Beta distribution and could you explain the meaning of updating the parameter of Beta? Oct 4, 2020 at 18:54
• As the number of trials is fixed, this is not a bandit problem. You provided no argument for why flipping both 50 times isn't optimal, or why you're using the algorithm you're using. And on a programming note, putting the same line of code in both branches of an if-then-else block is redundant. Oct 5, 2020 at 5:17
• "Nothing frustrates me more than when someone tells you to do the "optimal" thing without telling you the criteria over which to optimize." The question says "Now we toss 100 times of A or B to determine which one has the larger probability of head." This clearly states that the objective is to determine which one has the larger probability of a head. I don't see any ambiguity. "Optimal" means to maximize the probability of identify the coin with the higher probability. Oct 5, 2020 at 5:30
• The idea behind using the beta.rvs() is that you flip a coin with a probability proportional to its probability of being the coin with the largest probability to land on heads. It works with more than two coins/bandits, and is known as Thompson sampling. Oct 5, 2020 at 16:50
• I don't think this answers the question, for the reasons @Acccumulation also mentioned. Your proposed strategy seems to optimize the number of tosses of the "best" coin (largest p(head)), while our objective is to maximize our confidence that we identified the best coin. It's not obvious that we will do that by mostly flipping the coin that currently seems most promising. As the blog linked by John points out, regular Thompson sampling does not optimize this confidence (you can modify TS to explore more, but it's not clear to me that this optimizes the identification objective either). Oct 5, 2020 at 17:59

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.