4
$\begingroup$

Suppose I have two coins, and I don't know what the probability of getting a heads is with either coin. I flip one 60 times, and get heads 36 times. I flip another 20 times, and get heads 18 times. Which coin should I flip next for the highest probability of getting a heads? And how do I answer this more generally (changing # of flips, heads, and increasing the # of coins and ranking them)?

I tried solving this problem using the Maximum Likelihood Estimation function for the Binomial Distribution, but it doesn't behave in a way that I found useful.

Edit: The most extreme example would be to consider I have hundreds of coins, some have only been flipped once, and some have been flipped hundreds of times. How do I rank the coins in order to decide which ones would give me the greatest chance of picking heads? The practical situation I'm looking at actually resembles this situation, after some abstraction!

$\endgroup$
17
  • $\begingroup$ Note hat for the first, you can't discard the hypothesis that the coin is fair. For the second you most certainly can. $\endgroup$
    – lulu
    Apr 13 at 21:31
  • $\begingroup$ To stress: you need to take into account the sample size, not just the observed probability. Getting three $H$ out of four tries is hardly impressive. Getting $75$ out of $100$ is. $\endgroup$
    – lulu
    Apr 13 at 21:40
  • $\begingroup$ Maximum Likelihood seems irrelevant here as we have no idea what the distribution of possible probabilities might be. I would go for crude statistics. For the first coin you can not reasonably reject the hypothesis that the coin is fair (there's like a $7.7\%$ chance of getting at least $36$ Heads). For the second, we can. That's enough. More broadly, you could test the null hypothesis "the first coin has a lower $H$ probability than the second." Of course, you'll need to declare some confidence level, and you'll have to make some assumptions about the underlying distribution. $\endgroup$
    – lulu
    Apr 13 at 21:49
  • 1
    $\begingroup$ Assume a fair coin. Compute $\sum_{k=36}^{60} \binom {60}k\times 2^{-60}\sim .0775$. You could also approximate with a normal distribution. $\endgroup$
    – lulu
    Apr 13 at 22:22
  • 1
    $\begingroup$ Quick approximation: $\sigma=\sqrt {15}=3.87$ so you aren't even looking at a $2\sigma$ event. No big deal. $\endgroup$
    – lulu
    Apr 13 at 22:26

1 Answer 1

4
$\begingroup$

To answer this question rigorously, you need some sort of prior belief about the types of coins in the world.

To illustrate this, consider the extreme example provided by lulu in a comment to this answer:

suppose I flipped one coin a million times and it came up $H$ all but once. And then I flipped a second coin once and got $H$.

Suppose first that your prior belief about the world is that there are only two types of coins: fair coins and 100%-heads coins. With respect to this belief, we can be certain that the first coin is fair, and so it would be correct to prefer the second coin, which could be 100%-heads, and thus guaranteed to be at least as good as the first one.

However, if we modify our belief about the world to the belief that any given coin in the world has a heads-probability that uniformly falls in the range $[0, 1]$, then the first coin would be the better bet. I'll omit an exact calculation here. This similar question should give some hints on what the calculation would look like - there would be a (double)-integral over a triangular region under the line $y=x$ involved if trying to compute the probability that one coin is more biased than the other.

If you are not sure about the exact prior belief that underlies your problem, then you may be interested in some of the general strategies that appear in the multi-armed bandit literature. The multi-armed bandit problem supposes that you are given access to $n$ slot machines, and that at each step you choose a machine to play. At each subsequent step, you want to utilize the data you have seen so far in your ever-growing sample-size to determine which machine to play/replay next. This has a similar flavor to your problem, and the link lists some strategies, some of which have been proven to be optimal in some sense given various assumptions. A difference between the optimization task in the multi armed bandit context and yours is that in the multi armed bandit context, you are faced with a tension of exploration (gather more data) vs exploitation (maximize based on data seen so far), while in the way you phrased your problem, it sounds like the exploration phase is complete.

If you do a Google search for "multi armed bandit weighted coins", you get a variety of links similar to your problem of interest.

$\endgroup$
1
  • $\begingroup$ Thanks, this does give a lot to look at! In the real-world situation I'm looking at (sorry, this is buried quite deep in the comments on the question), there is actually some tension between exploration and exploitation - but other people are doing most of the "exploration". There are other complexities too, which the question omits. The way I've phrased the question is trying to abstract things to a point where things are manageable on a mathematical level. $\endgroup$ Apr 13 at 22:28

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.