4
$\begingroup$

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.

  • 0
    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.2012-09-14

1 Answers 1

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.