Say I have n biased coins. Coin $i$ lands on heads with probability $p_i$ which comes from a uniform prior probability distribution over $[0, 1]$. At times $t = 1, 2, ..., k$ I must select one of the coins to flip (Assume k > n). What strategy would give a maximal expected number of heads over the k flips?

This problem seems so deceptively simple... You obviously need to make some trade-off between flipping the coin that has given the best return so far and trying out others to see if they're better. I'm not sure how to do that.

  • $\begingroup$ Use the weighted majority algorithm (en.wikipedia.org/wiki/Weighted_Majority_Algorithm). $\endgroup$ Sep 12, 2012 at 23:38
  • $\begingroup$ How do I use that? Can you explain? $\endgroup$
    – ezeidman
    Sep 13, 2012 at 22:35
  • $\begingroup$ I think you are looking for the Gittins index, though I wikipedia-ed the term and it did not obviously describe the problem you are talking about. $\endgroup$
    – mike
    Sep 14, 2012 at 0:30

1 Answer 1


Use the multiplicative weights algorithm (also known as weighted majority, boosting [in machine learning], and probably other names as well). See this lecture for example, section 2.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .