# Maximize expected heads with biased coins.

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.

-
Use the weighted majority algorithm (en.wikipedia.org/wiki/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