The numbers below reflect my specific problem, but a general solution will also be appreciated.

You have 23 identical biased coins:

  • $\Pr[\text{Heads}] = 1/6$
  • $\Pr[\text{Tails}] = 5/6$

Desired result: 8 heads and 15 tails

You can flip each coin as many times as you want, but once you "lock" its result, you cannot flip it again in the future. Suppose you have already flipped some coins and "locked" the results. You have gotten $h$ heads and $t$ tails so far. You flip the next coin and get either a head or tail. You must now decide whether to "lock" the result or flip it again. How should you decide what to do to minimize the total number of expected coin flips to get the desired result?


It seems like the right approach here is the greedy one. Lock in a coin if you still need it, and if you no longer need it, don't. It's impossible to win until you have flipped at least 8 heads and at least 15 tails. With this approach, you win immediately once you have satisfied these inequalities. And since all the flips are independent, you don't have to worry about what you have locked in changing the probability of future flips.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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