Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Use the weighted majority algorithm ( – Yuval Filmus Sep 12 '12 at 23:38
How do I use that? Can you explain? – ezeidman Sep 13 '12 at 22:35
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. – mike Sep 14 '12 at 0:30
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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