Ten coins with bias from a uniform distribution

Question

You have ten coins, each with a bias for head drawn from a uniform distribution [0,1]. For example, a coin with a 0.7 bias means that the probability of flipping a head is 0.7. You are allowed 100 flips and you are free to choose any coins to flip. Each time you flip a head, you get $1. How much money would you pay to play this game and what is your strategy?

Here's what I have in mind so far: The most basic strategy is to each time pick a coin at random and flip it. The expected payoff is $50. To do better than that, I need to know which coins have biases bigger than 0.5. It seems that I could use a Bayesian approach to update my belief about each coin, but doing so would require multiple rounds, and I'm not sure how to actually quantify this.

Answer 1

If you are asking for the optimum strategy, I would also be curious to hear from others. My first instinct would be to identify the coins by number, and flip Coin #1 until it came up tails. Then I would move on to each subsequent coin, flipping until I get the first tails. This would establish a very shaky estimate of their biases. Then it seems smart to "flip them until tails", in order from best to worst performer so far. There should be a cutoff point, based on how many available flips remain, and on how well the best performers did. The cutoff would exclude the worst performers completely, and could also exclude the so-so performers, if the best ones are much better than the rest. Mathematically, the first tails shown will tend to line up with the expected number of flips until tails, over more and more trials. If you estimate the bias as P = 1/E, where P is probability of tails (or heads), and E is expected tries until the first tails (or heads), you can use the first occurrence as a rough estimate of E, giving you a rough estimate of P. After every new instance of tails, reevaluate which coins are better to flip. Concerning the exact worth of playing this game... well, I'm sure its based on the actual best strategy, maybe not mine, and it may involve binomial coefficients. My best guess for the value of the game is $79.17.

Here's my rationale. If you imagine that the coin biases are occupying all ten deciles of unity (0% to 10%, 10% to 20%, etc.), then it's likely that one coin has an approximately 95% chance of showing heads. The chance of stumbling across that one as the first coin is 10%, but it should yield an average of 19 "heads" before showing tails at 20 flips. The 85% coin only yields around 5.67 "heads" in 6.67 flips. The 75% coin yields 3 "heads" before showing tails at 4 flips. The 65% coin yields 1.86 "heads", out of 2.86 flips. The average value for these games is $80,

and multiplied by (.40) gives 32 dollars toward the average value of all possible games. So far, these are 4 out of 10 starting scenarios, where you would not switch coins at all. The reason you would stay with any coin that averages at least 1.582 heads for every 2.582 flips, is that you are above the 63.2% bias level. (This is simply 1 - 1/e.) It doesn't make sense to switch coins when the chance of doing worse is greater by switching. If you start out with a poorly performing coin, you should switch to another coin. This is the case about 6 out of 10 times, starting out. Then, switching until you get the 4 out of 10 better coins gives the rest of the game's value. Averaging the yield for the poor performers gives 52 cents in 1.52 flips, on average, before finding a high performing coin. There's a 5/9 chance of choosing a bad coin again, and then 4/8, 3/7, 2/6, and 1/5.

(6/10) + (6/10)(5/9) + (6/10)(5/9)(4/8) + (6/10)(5/9)(4/8)(3/7) + (6/10)(5/9)(4/8)(3/7)(2/6) + (6/10)(5/9)(4/8)(3/7)(2/6)(1/5) = 1.2

This is 2 times the starting chance of flipping bad coins. This 2 is multiplied with the flips and the yield. (1.52)(2) = 3.04 flips (.52)(2) = 1.04 dollars. In the remaining 96.96 flips, the value is $77.57.

Add that to 1.04 dollars to get $78.61.

Now put the chances with the values, to get a weighted average. (.60)(78.61) + (.40)(80) = 47.17 + 32 = $79.17

Edit: This is below the value of the game, because it costs very few flips to try for the 85% coin or the 95% coin. I would still put it between 80 and 85 dollars.

Answer 2

Let $C$ be the number of coins, and let $N$ be the number of flips (e.g., $C=10,\,N=100$).

Here's a proposed strategy which I think is pretty good, although I'm fairly certain it's not optimal . . .

When there are $n$ flips remaining, choose a coin for which $$ \frac{h+1+\min(1,n-1)}{h+t+2+\min(1,n-1)} $$ is greatest, (where $h,t$ are the prior number of heads, tails, respectively for that coin), and if there's more than one such coin, choose one for which $h$ is greatest.

Let $e(C,N)$ be the value of the game, assuming the above strategy.

For relatively small values of $C,N$, the exact value of $e(C,N)$ can be computed by recursion.

For example, a Maple implementation yields $$ e(4,12) = \frac{1042111771}{129729600} \approx 8.032952934 $$ For larger values of $C,N$, the value of $e(C,N)$ can approximated via simulation.

For example, simulation yields $82 < e(10,100) < 83$.

For reference, here's the Maple code which I used to compute $e(4,12)$.