9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ sounds like a multi-armed bandit question $\endgroup$ – gunes Oct 4 '20 at 14:17
  • 3
    $\begingroup$ 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. $\endgroup$ – user20160 Oct 4 '20 at 19:46
5
$\begingroup$

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)

enter image description here

$\endgroup$
17
  • 2
    $\begingroup$ 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? $\endgroup$ – user6703592 Oct 4 '20 at 18:54
  • 3
    $\begingroup$ 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. $\endgroup$ – Acccumulation Oct 5 '20 at 5:17
  • 3
    $\begingroup$ "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. $\endgroup$ – Acccumulation Oct 5 '20 at 5:30
  • 3
    $\begingroup$ 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. $\endgroup$ – Accidental Statistician Oct 5 '20 at 16:50
  • 3
    $\begingroup$ 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). $\endgroup$ – Ruben van Bergen Oct 5 '20 at 17:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.