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.

$\endgroup$
3
  • $\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

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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