Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A question in probability by a non-mathematician:

A fair coin is tossed $2N$ times. Is it unlikely that we get exactly $N$ heads and $N$ tails?

From one side, this must be the most likely result! But intuitively, if someone reports to me that they threw 2,000,000 coins and got exactly 1,000,000 heads and 1,000,000 tails I would be a little suspicious.

If this really is suspicious, how does it compare to biased results? Obviously, 2,000,000 heads is a much more suspicious result. But, for what value of $K$ is $N+K$ heads and $N-K$ tails as suspicious as $N$ heads and $N$ tails?

Equations are very welcome, but please try to provide some aid in understanding them.

ADDED: Henning Makholm's answer helped me understand better what I want to ask: I always assume a fair coin and would like to compare the probability of the split N/N with the probability of getting either more than more than N+K or less than N-K heads. By ncmathsadist's answer , the probability for the N/N split goes like 1 over the square root of N. What about the probability to get more than either more than N+K or less than N-K heads? For what value of K (approximately) does it equal to 1/sqrt(n pi)?

CLARIFICATION: If f(N) is the probability to get an N/N split in 2N tosses of a fair coin, and g(N,K) is the probability to get more that N+K heads or less than N-K heads in 2N tosses of a fair coin, then I am asking for a formula which, given N, approximates the values of K for each f(N) is closest to g(N,K). This is a formula that takes N and returns K so we can call it h(N)=K. Which kind of function is h? My guess from a little experementing with the online software in Brian M. Scott's answer is that the function h is apporximately the SQRT function, multiplied by some constant, or something like that.

share|improve this question
    
If you fix an $\epsilon \in (0, 1]$, then I believe the odds that the number of heads is within $[(1-\epsilon) N, (1 + \epsilon) N]$ converges to 1 as $N$ goes to infinity. –  Hurkyl Jul 6 '12 at 0:47
    
@Hurkyl: Definitely. I'm looking for a quantitive result though. –  Tom Y Jul 6 '12 at 1:01
    
Seems you are not interested anymore but the answer to the question in the Clarification paragraph is $h(N)\sim\sqrt{\frac12N\log N}$ (hence slightly but not much more than $\sqrt{N}$). –  Did Jul 14 '12 at 14:49

5 Answers 5

up vote 11 down vote accepted

It is fairly unlikely if $n$ is large. The probablity of $n$ heads and $n$ tails is $${2n\choose n} {1\over 4^n}.$$

We have $${2n\choose n} = {(2n)!\over n!n!}.$$

Stirling's formula states that as $n$ becomes large, $$n! \sim {n^ne^{-n}\over\sqrt{2\pi n}},$$ where we say $a_n\sim b_n$ if $a_n/b_n \to 1$ as $n\to\infty$. Using this formula,

$${2n\choose n}{1\over 4^n}\sim {1\over 4^n}\left((2n)^{2n}e^{-2n}\over \sqrt{4\pi n}\right) \left(\sqrt{2\pi n}\over n^ne^{-n}\right)^2 $$

Cancel the exponentials and the $n^n$s and we get

$${2n\choose n}{1\over 4^n}\sim {2^{2n}\over 4^n}{2\pi n\over 2\sqrt{\pi n} } = {1\over \sqrt{n\pi}}.$$

So you can see that this probability decays like $1/\sqrt{n\pi}$ as $n$ gets large. So if $n$ gets 100 times larger, this probability diminishes by a factor of 10.

share|improve this answer
1  
Good answer. Incidentally it is worth noting the connections: this is the probability that a random walk is a bridge (that is it begins and ends on the x-axis), and furthermore it is interesting to note that this fact is used to have an entirely discrete and exact simulation of a coin of bias $\sqrt{p}$ given a coin of bias $p$, discovered among others by Johan Wästlund and systematized in a recent wonderful paper by Flajolet et al.. –  Jérémie Jul 5 '12 at 22:54
    
This is a good answer for the part of my question about the N/N split. –  Tom Y Jul 5 '12 at 22:55
    
@Jérémie: Incidentally, you use discovered in the sense of re-discovered after others (in the present case, Keane and O'Brien). –  Did Jul 5 '12 at 23:27
    
@did: I said "discovered among others", so I think my formulation was correct---especially considering Wästlund mentions Keane and O'Brien in the very first page as being the prior publishers. I happen to prefer the former's presentation. Was it really necessary for you to correct me so tersely? –  Jérémie Jul 5 '12 at 23:47
    
My question has not been fully answered (see clarification), but I choose to accept this one. –  Tom Y Jul 8 '12 at 2:20

Based on the binomial distribution, the probability of exactly N heads in 2N coin flips is

P(N) = 2NCN * 0.5N * 0.5N = (2N)!/2(N!) * .52N

For a trial of two coin flips, there are four possible permutations of outcomes (two heads, two tails, head/tail and tail/head) so the probability of exactly one head and one tail is only .5, and that's the simplest non-trivial case. It gets worse from there; with four coin flips the probability of two heads is 6*.25*.25 = .375 = 3/8. With 8 flips, the probability of 4 heads are 70*.0625*.0625 ~= .273. 16 flips, probability of 8 heads = 12870*0.0000152587890625=.19638.

So, yes, for any N>1 it is more likely that you won't get exactly N heads/tails, and as N grows large, the probability of getting exactly N heads/tails from 2N trials converges to zero.

share|improve this answer

The easiest way to answer the second part of your question is to continue along the line of Brian M. Scott's answer.

A fair coin flip is a Bernoulli variable $F$ of parameter $p=1/2$: it returns 0 with probability $1/2$ and $1$ with probability $1/2$. The sum of $2N$ coin flips is the sum of $2n$ Bernoulli variables of parameter $p$, and that is the definition of the binomial distribution $Bin(2n,p)$.

What are you asking, is what is the probability that $Bin(2n,p)=n$, or if we rescale (to consider that the coin flips are valued with $-1$ and $+1$, instead of $0$ and $1$), what is the probability that $(2*Bin(2n,p)-n)=0$. Either way it's a binomial distribution.

Next, if you go to Wikipedia, as previously suggested, you can find two interesting facts:

  • first the PDF $f(k)$ and CDF $F(k)$ of the binomial distribution: basically this gives you the function with which you can tell you both things you've asked, as the probability that the number of heads and tails are exactly the same is $f(n)$, and the probability that it deviates by, say, 10% is $F(1.10*n) - F(0.90*n)$;

  • second, you get an even simpler approximation: the binomial distribution, like all distributions that can be defined as the sum of another, is affected by the Central Limit Theorem, which means that when $n$ is large enough, the distribution is very well approximated by a normal.

share|improve this answer

It is the most likely single outcome, but it is very unlikely, and it becomes less likely as $n$ increases. As $k$ goes from $0$ to $n$, the split $n+k,n-k$ becomes increasingly unlikely. Already with $n=10$ the probability of a $10,10$ split is only

$$\frac{\binom{20}{10}}{2^{20}}\approx 0.1762\;,$$

but an $11,9$ split is less likely, at $$\frac{\binom{20}{11}}{2^{20}}\approx 0.1602\;,$$ and a $12,8$ split is less likely yet, at $$\frac{\binom{20}{12}}{2^{20}}\approx 0.1201\;.$$

By the time you get to $n=100$, the probability of an even split is only about $0.0563$, and the probability of a $120,80$ split is down to about $0.0010$.

For more information, search on binomial distribution; the Wikipedia article to which I linked gives you a starting point.

Added: For large $n$ you can use the normal approximation to the binomial distribution. When tossing $2n$ fair coins, that’s the normal distribution with mean $n$ and standard deviation $\frac1{\sqrt{2n}}$. If $n=10^6$, for instance, the standard deviation is approximately $1414.21$, and the probability of an even split is $\frac1{1000\sqrt{\pi}}\approx 0.000564$. Using the second calculator here, with parameters

$$\begin{align*} \text{Mean:}&1000000\\ \text{Sd.:}&1414.21\\ \text{Shaded Area:}&0.000564\\ \text{Outside:}& \end{align*}$$

returns $995123.2935\text{ or }1004876.7065$, meaning that that the probability of getting fewer than $995123.2935$ or more than $1004876.7065$ heads is about $0.000564$. Thus, the $k$ for which the probability of getting a difference of more than $2k$ in the numbers of heads and tails is the same as the probability of an even split is about $4877$ when $n=10^6$. You can play with the calculator to get $k$ for other values of $n$.

share|improve this answer
    
I should have asked about the probability of getting a difference of more the 2K between the number of heads and the number of tails. –  Tom Y Jul 5 '12 at 22:58
    
Is there a way to approximate K given N? –  Tom Y Jul 6 '12 at 0:05

It depends on what you compare it to.

Getting 1,000,000 heads is slightly more likely than getting 1,000,023 heads. It is also slightly more likely than getting 1,000,282 heads.

But getting either 1,000,023 or 1,000,282 heads is together more likely than getting exactly 1,000,000 heads.

And getting "more than 998,000 and less than 1,002,000 but not 1,000,000 exactly" is much more likely than getting 1,000,000 heads.


However, for any biased coin it is even less likely that you'll get exactly 1,000,000 heads -- so what you should suspect if you experience this is not that the coin is biased, but that somebody is actively manipulating the coin to get heads and tails to even out better than you have a right to expect.

If $N$ is a less nice number than 1,000,000 (such as, say, 1,371,388) one should also be very suspicious of how that particular $N$ was chosen. Perhaps somebody decided to stop the experiment after exactly 2,742,776 throws exactly because at that point in time there happened to be equally many heads and tails. If you're doing a long series of throws, then it is quite likely that there will be some $N$ among all the possible places to stop the series where it will match exactly.

share|improve this answer
    
Thanks. This captures what I intuitively meant to ask. I updated the question accordingly, in hope you may take a look again. –  Tom Y Jul 5 '12 at 22:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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