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$ – Yuval Filmus Sep 12 '12 at 23:38
  • $\begingroup$ How do I use that? Can you explain? $\endgroup$ – ezeidman Sep 13 '12 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 '12 at 0:30

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.


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.