How to determine if coin comes up heads more often than tails?

Not a math student, so forgive me if the question seems trivial or if I pose it "wrong". Here goes...

Say I'm flipping a coin a n times. I am not sure if it's a "fair" coin, meaning I am not sure if it will come up heads and tails each with a propability of exactly 0.5. Now, if after n throws it has come up heads exactly as many times as it has come up tails, then obviously there's nothing to indicate that the coin is not fair. But my intuition tells me that it would be improbable even for a completely fair coin to come up with heads and tails an exact even number of times given a large amount of tosses. My question is this: How "off" should the result be for it to be probable that the coin is not fair? IOW, how many more tosses should come up heads rather than tails in a series of n throws before I should assume the coin is weighted?

Update

Someone mentioned Pearson's chi-square test but then for some reason deleted their answer. Can someone confirm if that is indeed the right place to look for the answer?

-
Seems like a good candidate for Fisher's exact test. –  Larry Wang Aug 6 '10 at 19:48
I think this is a fantastic math question for a non-math person to ask. –  Pete L. Clark Aug 6 '10 at 20:54
re: Fisher exact test --- that is for a different type of problem, where you have two (or higher) dimensional tables of data. Here we have a one-dimensional 2x1 matrix of data that records the number of Heads and of Tails. –  T.. Aug 7 '10 at 6:40
Pearson's chi-square statistic is used in some similar problems but it is not the right tool here, because (1) it assumes normal distribution (we might want the exact, binomial distribution); (2) it is unable to perform a one-sided test. The natural setting for the problem is that of inferring a proportion from samples, with confidence intervals, etc. –  T.. Aug 8 '10 at 8:06
The coin is "almost surely" not fair. (There is a zero percent chance that it is fair.) I have added an answer if you want to know how unfair it is. –  Neil G Aug 28 '10 at 8:55

Given your prefatory comment, I'm going to avoid talking about the normal curve and the associated variables and use as much straight probability as possible.

Let's do a side problem first. If on a A-D multiple choice test you guess randomly, what's the probability you get 8 out of 10 questions right?

Each problem you have a 25% (.25) chance of getting right and a 75% (.75) chance of getting wrong.

You want to first choose which eight problems you get right. That can be done in 10 choose 8 ways.

You want .25 to happen eight times [$(.25)^8$] and .75 to happen twice [$(.75)^2$]. This needs to be multiplied by the possible number of ways to arrange the eight correct problems, hence your odds of getting 8 out of 10 right is

${10 \choose{8}}(.25)^8(.75)^2$

Ok, so let's say you throw a coin 3000 times. What's the probability that it comes up heads only 300 times? By the same logic as the above problem that would be

${3000 \choose{300}}(.5)^{300}(.5)^{2700}$

or a rather unlikely 6.92379... x 10^-482.

Given throwing the coin n times, the probability it comes up heads x times is

${n \choose{x}}(.5)^n$

or if you want to ask the probability it comes up heads x times or less

$\sum_{i=0}^{x}{{n \choose{i}}(.5)^n}$

so all you have to do is decide now how unlikely are you willing to accept?

(This was a Binomial Probability if you want to read more and all the fancier methods involving an integral under the normal curve and whatnot start with this concept.)

-
Jason Dyer's last formula is essentially calculating a $p$-value for a one-sided test of significance. While you probably want a two-sided test of significance, I think this is the right way to go. –  Mike Spivey Feb 13 '11 at 0:06

This question is one of statistics (esp. statistical inference), not probability per se. Keywords: "binomial sampling"; "confidence interval for a proportion". Asking this at http://stats.stackexchange.com will get more complete answers.

The related probability fact is: if a coin has probability $p$ of coming up heads and is tossed $n$ times, then the observed number of heads will on average be $np$, but we expect the observed number to fluctuate (if the experiment with $n$ tosses is repeated many times) around the average by an amount on the order of $\sqrt{np(1-p)}$. Keywords: normal distribution, bell curve, Central Limit Theorem, binomial distribution, convergence of binomial distribution to normal (Gaussian) distribution.

-
This is definitely a inference problem, but I'm not sure if that means it is outside the realm of probability. What is your take on using probability as it was here to answer an inference question: math.stackexchange.com/questions/707/… –  Jonathan Fischoff Aug 7 '10 at 5:45
I couldn't make sense of the question: too much detail, too little overview. Every statistics calculation is ultimately a probability calculation, but the questions asked and the framework within which the calculations are organized, are different. –  T.. Aug 7 '10 at 6:09
Gotcha, that's in line with my thoughts. I thought were trying to express something else. –  Jonathan Fischoff Aug 7 '10 at 6:49

This problem is a Bayesian probability problem. You can never know whether or not the coin is fair because, as you point out yourself, even if the first n flips come up equally head and tails, you would merely have "nothing to indicate [yet] that the coin is unfair".

You can calculate the probability that the coin's bias is, say between 49% and 51%, by evaluating the following:

$I_{0.51}(h+1,t+1) - I_{0.49}(h+1,t+1)$

where $I$ is the incomplete beta function.

This follows from the definition of the Beta distribution as the conjugate prior of the Bernoulli distribution and the definition of the incomplete beta function as its cdf.

-

I am surprised that no one has mentioned Hypothesis Testing so far. Hypothesis testing lets you to decide, with a certain level of significance, whether you have sufficient evidence to reject the underlying (Null) hypothesis or you have do not sufficient evidence against the Null Hypothesis and hence you accept the Null Hypothesis.

I am explaining the Hypothesis testing below assuming that you want to determine if a coin comes up heads more often than tails. If you want to determine, if the coin is biased or unbiased, the same procedure holds good. Just that you need to do a two-sided hypothesis testing as opposed to one-sided hypothesis testing.

In this question, your Null hypothesis is $p \leq 0.5$ while your Alternate hypothesis is $p > 0.5$, where $p$ is the probability that the coin shows up a head. Say now you want to perform your hypothesis testing at $10\%$ level of significance. What you do now is to do as follows:

Let $n_H$ be the number of heads observed out of a total of $n$ tosses of the coin.

Take $p=0.5$ (the extreme case of the Null Hypothesis). Let $x \sim B(n,0.5)$.

Compute $n_H^c$ as follows.

$$P(x \geq n_H^c) = 0.1$$

$n_H^c$ gives you the critical value beyond which you have sufficient evidence to reject the Null Hypothesis at $10\%$ level of significance.

i.e. if you find $n_H \geq n_H^c$, then you have sufficient evidence to reject the Null Hypothesis at $10\%$ level of significance and conclude that the coin comes up heads more often than tails.

If you want to determine if the coin is unbiased, you need to do a two-sided hypothesis testing as follows.

Your Null hypothesis is $p = 0.5$ while your Alternate hypothesis is $p \neq 0.5$, where $p$ is the probability that the coin shows up a head. Say now you want to perform your hypothesis testing at $10\%$ level of significance. What you do now is to do as follows:

Let $n_H$ be the number of heads observed out of a total of $n$ tosses of the coin.

Let $x \sim B(n,0.5)$.

Compute $n_H^{c_1}$ and $n_H^{c_2}$ as follows.

$$P(x \leq n_H^{c_1}) + P(x \geq n_H^{c_2}) = 0.1$$

($n_H^{c_1}$ and $n_H^{c_2}$ are symmetric about $\frac{n}{2}$ i.e. $n_H^{c_1}$+$n_H^{c_2} = n$)

$n_H^{c_1}$ gives you the left critical value and $n_H^{c_2}$ gives you the right critical value.

If you find $n_H \in (n_H^{c_1},n_H^{c_2})$, then you have do not have sufficient evidence against Null Hypothesis and hence you accept the Null Hypothesis at $10\%$ level of significance. Hence, you accept that the coin is fair at $10\%$ level of significance.

-
While he doesn't mention the term, Jason Dyer's answer involves an implicit one-sided hypothesis test. Still, +1. –  Mike Spivey Feb 13 '11 at 0:03
@Mike: I just did a Command F to find out if the word Hypothesis was mentioned. Yes Jason's answer implicitly is a one-sided hypothesis test. –  user17762 Feb 13 '11 at 0:05
my wife always tries to kill me every time I accept the null hypothesis. jerrydallal.com/LHSP/sigtest.htm has an interesting explanation, in terms of confidence intervals, of the difference between accept and failure to reject. –  uncle brad Feb 17 '11 at 20:53
@uncle brad: True. Hypothesis testing and Confidence intervals are the dual of each other in some sense. –  user17762 Feb 17 '11 at 20:56

In typical math problems involving coins we know the probability ahead of time. If you know the probability of heads and tails with absolute certainty the sequence of heads and tails you get from flipping the coin tells you nothing about the what the probability should be (because you already know it).

On the other hand if you have absolutely no idea what the probability is, and all you know is that the there are two sides you will end up with something called the "Rule of Succession" or $\frac{Heads + 1}{Total + 2}$. http://en.wikipedia.org/wiki/Rule_of_succession for assigning the probability.

In your case it sounds like you are in between the two. You have some information that leads you to believe that the coin is balanced but you are not positive, and the thus the frequencies from flipping will affect your probability assignment.

This is why this question is tricky. You have to take everything you know about the coin and encode mathematically.

One why to think about doing that is assume that you have already flipped the coin x number of times. So in the case of knowing the probability for certain, it is as though we have flipped the coin an infinite number of times.

So maybe you would start by assuming that your prior knowledge is equivalent to having flipped the coin 10,000 times with half heads and half tails. That way the frequency will still will affect it, but not so much initially.

I don't of any mathematically texts that have attempted at solving anything but the two extreme cases (complete information, zero information). A physicist, Jaynes attempted to broach this problem here http://www-biba.inrialpes.fr/Jaynes/cc18i.pdf (I can only partially follow his reasoning), but I don't know if there is an accepted mathematically rigorous way to solve this type of problem.

-
The structure of the coin doesn't matter as long as you assume independent identically-distibuted coin tosses. In that case, the probability model for the outcomes is a coin flip with probability $p$. The internal mechanism of the coin and its flips would be relevant in determining whether an observed value (in a large experiment) of $p = 0.1$ comes from rigging the coin and tossing fairly, or rigging the tosses of a fair coin. –  T.. Aug 7 '10 at 9:21
Its not the structure of the coin that I was trying to emphasize. There is a difference between being sure of $p$, being pretty sure of $p$ and being completely ignorant to $p$. Only in the last two cases will recording the frequencies cause any adjustment in the value you are assigning to $p$. In the limit the probability will approach the frequency regardless of your initial assumptions. The difference is just how fast that convergence occurs. –  Jonathan Fischoff Aug 7 '10 at 9:38
Sure. As your comments indicate these are considerations in statistics that go beyond probability per se (though any statistical calculation will then be a question in probability theory). The usual formal framework for incorporating prior knowledge is Bayesian statistics where you put a probability distribution on the set of possible $p$, and experiments update this distribution, eventually concentrating it near the true value of $p$. Full knowledge means 100% probability of a single value of $p$, no knowledge is the uniform distribution on $[0,1]$. –  T.. Aug 7 '10 at 10:03
Agreed......... –  Jonathan Fischoff Aug 7 '10 at 10:10
btw, re: Jaynes, the main thing is that he was advocating Maximum Entropy (or max-ent given known information) as a principled ansatz for choosing the "prior knowledge". Other than that his approach may be philosophically different from others, I don't know for sure, but the calculations should be the same. –  T.. Aug 7 '10 at 10:13

Others have provided fine answers for the standard method of calculating the probability of getting k or more heads in n tosses.

However, I think you are approaching the question from the wrong direction. Few people have tossed a single coin enough times. Pearson did it around 1900: He tossed a coin 24,000 times and came up with 12,012 heads. Count Buffon tossed one 4040 times and got 2048 heads and Kerrich did it 10,000 times in a German POW camp and got 5067 heads. (Moore et al. "Introduction to the Practice of Statistics", 6th ed, p.240).

If you want to make sure a given coin is fair, you should use physical measurements and analyze the surface and composition of the coin to make sure its weight is uniformly distributed, it's not bent etc.

If someone offers you a bet where you pay 10 dollars if the coin comes up heads, and he pays 10,000 dollars if it comes up tails, you can be assured that the coin is not fair ;-)

Otherwise, we assume a generic coin picked without any special procedure is fair. Without that assumption, life as we know it would not be possible.

For example, casinos are not required to roll their dice thousands of times to ascertain their fairness. In fact, doing so may wear out the corners or edges. Rather, there are specific manufacturing process requirements that need to be met.

Similarly, no one wastes time trying to ensure that the coin used to determine who gets the ball at the start of a football game is fair. NFL's rules on the coin flip are simple and they do not involve ascertaining the fairness of the coin.

Probability will tell you that if 1,000 people each toss their fair coins 30 times, most of the percentages will be very close to 50%. Determining whether an individual coin is fair is not a task for Statistics.

See also Dynamical Bias in Coin Tossing and Chance News 11.02 referenced in that article.

-
I have not downvoted, but in my opinion this is missing the point of the question, in which the coin is just an example. The question is a more fundamental one: given a sequence of independent events with a fixed probability ("Bernoulli trials"), if you begin with the assumption that this probability is $p$, how do you gain or lose confidence in this asssumption by looking at a finite number of trials, and how many such trials are necessary? –  Pete L. Clark Aug 8 '10 at 9:36
Also, I find your suggestion that the number of people in history who have flipped a coin 4,000 or more times is on the order of 3 to be rather implausible. (And also, statistics tells us that 12,012 heads after 24,000 flips is somehwat fishily close to 50%.) –  Pete L. Clark Aug 8 '10 at 9:47
@Pete I did not suggest that the set of people who flipped a coin many times to be limited to the three I mentioned. Those are the ones that I know are documented. However, I hope you would agree that FEW would be the appropriate adjective to describe the number of people who have tossed the same coin repeatedly that many times. I used to assign a homework where students were required to toss a coin 20-30 times. I know most of them could not be bothered with that. –  Sinan Ünür Aug 8 '10 at 14:42
@Pete: Why would 12,012 heads after 24,000 flips be fishy? I just asked my computer to flip the coins and got 11,996. How else would the LLN work? –  Sinan Ünür Aug 8 '10 at 14:48
Well, I would have expected the deviation from 50% after $n$ flips to be of order of magnitude $\sqrt{n}$, and 12 is a good bit smaller than $\sqrt{24000}$. But I just opened up an online coin-toss simulator and flipped $24000$ coins about a dozen times. As I suspected, most of the time the deviation between H and T was more than $50$, but the first time I ran it I got...$12012$ heads exactly. –  Pete L. Clark Aug 8 '10 at 21:10

I'm also not a math student, but a software engineer student, I can tell you that I do not know the exact answer, but I might know enough to get an upvote for my effort, so:

Assuming it is a fair coin

Fair coin means, that probability to get result 'head' in a single toss is 50%.

Sample questions you could ask at search engine wolfraalpha.com to get answer :

Assuming it is a unfair coin

Fair coin means, that probability to get result 'head' in a single toss is less or greater then 50% and if you add probability to get result 'tail' you still get 100%. So basically you still have a fair coin with a tilted probability, for example {64% to get head;36% to get tail} - you can use same equations, just shift the probability.

Assuming it is a unfair coin with undetermined probability

I do not even understand, how anyone could determine that coin has a fixed probability fixed number of from samples of coin tosses. For example, I could make a function, that would change coin toss probability by after each toss or some number of tosses - you as the user, can not determine that by any number of sample sequence tosses.

Conclusion - Answer to "How 'off' should the result be, for it to be probable, that the coin is not 'fair'"?

From definition of fair coin toss, it is more probable, that coin is 'unfair' as soon as:

'head results'!='nr. tail results'.

For example, you do 1 million coin tosses with a 'fair' coin (but you do not know that), and end up with all heads, then what could you tell me about how 'fair'/'unfair' is the coin?

You can conclude indirectly, that the probability of the coin being 'fair' is 1.0100 x 10^-301030. To get probability that coin is unfair, you solve 100%-'fair coin toss probability'.

If this is a physics problem, then addition to measurement you also need to add combined uncertainty (Uc). So, if combined uncertainty exceeds the probability of the coin being 'fair', you can conclude that it is 'unfair' or at least - acts as one.

To get combined uncertainty there are at least 3 ways I am aware of:

1. multiple measurements
U c ⁢ ( x ) = U A 2 ⁢ ( x ) + U B 2 ⁢ ( x ) m
1. 1-measurement
U c ⁢ ( x ) = U B 2 ⁢ ( x ) M + U B 2 ⁢ ( x ) b
1. indirect measurements
U c ⁢ ( y ) = ∂ y ∂ x 1 ⁢ U C ⁢ ( x ) 2 + … + ∂ y ∂ x n ⁢ U C ⁢ ( x ) 2

Where Ua and Ub are uncertainty components: Type A and B.

-

I think mathematics/statistics will give us a lot of nice continuous analyses of the data, including quantitative measures of confidence, but the discrete decision to presume that the coin is loaded is arbitrary, even if based on those measures of confidence.

-