APB9999 got me thinkin’ in this thread. He/she mentioned that even though the most likely outcome of a roll of two dice is seven, it is more likely that the outcome will be some other number.
This started me thinking about the old, “If you flip a coin an infinite number of times, you’ll end up with half heads and half tails.” Of course, this is just the most likely outcome. It seemed to me (or it least it did a few hours ago) that with an infinite number of possible outcomes, any particular outcome would have zero probability of occuring. So I set out to prove this, and came up with the following.
If you flip a 2*n coins where n is a positive integer, the chance that you’ll end up with half heads and half tails is:
F(n)=((2n)!)/(((n!)[sup]2[/sup])(2sup[/sup])) (Enough with the parentheses already!)
This is where I ran into a snag. I have know idea how to take the limit of that as n approaches infinity.
I did determine that F(n+1)/F(n) = 1 as n approaches infinity, which seems to indicate that the limit of F(n) as n approaches infinity may be non-zero.
Also, for shits and giggles (or my total lack of a life), I determined F(n) for the first 65000 or so terms to see if it looked like it might converge on zero. I found that it doesn’t seem to be in any hurry to get to zero, and, in fact, seems damn comfortable at a smidgen* above .002
So, what’s the straight dope on this? And does anyone have an infinite number of coins that I can borrow so I can put this theory into practice?
My result was, for large numbers, F(n) = 1/Sqrt(n*Pi), which clearly tends to zero. This actually leads me to believe that your F(n) must be incorrect, since statistical mechanics depends rather heavily on the fact that the likelihood of the equilibrium (highest entropy) state of a system tends strongly to one in the limit of large numbers. Since the 50% heads/50% tails state is the highest entropy state of this system (the result with the most ways of being obtained), its probability should tend to one as n -> infinity.
OK, I’ve got a little bit more time now. First off, I don’t really see any reason to expect, a priori, that the limit will be zero. Any particular outcome will have zero probability of occuring, but there are many different ways you can have exactly half of the flips come up heads. If you flip 4 times, for example, there are 6 different ways:
HHTT,HTHT,HTTH,THHT,THTH,TTHH.
Also, it doesn’t really make sense to say, “If you flip a coin an infinite number of times, you’ll end up with half heads and half tails”. But you can certainly look at the limit as the number of flips increases.
If you take the limit as n goes to infinity of my F(n) up there, you do actually end up with a zero probability of having exactly half of the flips come up heads.
I’m not sure what the statistical mechanics and entropy has to do with this. It is true that (# of heads)/(# of flips) will tend to 1/2, if that’s what you mean, but that’s different from saying the number of heads will be exactly half the number of flips.
Actually, I don’t see that your expression for F(n) goes to zero as we approach infinity at all. If we use Lance’s notation, in which the number of flips is 2n, and the definition of the binomial coefficient: (size of set)!/(size of sample)!, I get:
F(n) = 2n!/(n!*2^2n)
which makes sense: if you think of the 2n flips as 2n boxes into which you are trying to fit n heads (or n tails), then 2n!/n! is the number of ways that you can select those boxes. Divide that by the total number of possible outcomes, 2^2n, and you’ve got the probability of getting exactly 50% heads and 50% tails.
Using Stirling’s approximation again gives
lim(F(n))= lim((n/e)^n * 2/Sqrt(2))
which actually tends to infinity, since the powers of infinity are infinitely larger than the powers of e.
Now I admit this doesn’t help much as far as showing that lim(F(n)) -> 1/2, but at least it shows that it doesn’t tend to zero.
OK, earlier I had just glanced at Lance Turbo’s expression for F(n). Now that I look at it again, I see that we actually had the same formula, only his was based on 2n flips, mine was based on n flips. Won’t make a difference either way.
So, after flipping an infinite number of coins, the most likely outcome is that you’ll have a 50/50 ratio of heads to tails, and this outcome has zero probabilty of occurring.
PaulT, your equation is incorrect, Lance Turbo’s was correct. (2n)!/(n!)^2 is the number of ways in your boxes analogy for distinct boxes. A trivial example: N=2. Your formula, using (2n)! instead of 2n!, which is the order of operations I think you intended, gives:
4!/(22^4) = 24/32 = 3/4 probability.
Lance Turbo’s gives 4!/(2^22^4)=12/32 = 3/8 probability.
Cabbage pointed out that there are 6 of the 16 combinations that work in for N=2. This means the actual probability is 6/16= 3/8.
(that’s why your calculations gave a probability > 1, which is simply impossible.)
My intuition is that the probability should tend to zero; I see this as analogous to a summation of errors. I’ll use a physical analogy: say you are measuring N with a method giving a standard deviation of n. Ten thousand measurements gives a number = 10000N with a standard deviation of 100n. In other words, the estimate for the value of N is one hundred times as precise as for a single measurement, but the actual measured error is also 100 times larger.
If the analogy holds, after many flips the total difference from 50/50 will increase, but the average difference per flip will also decrease. This average difference is what you are thinking of, I think.
I must concede the incorrectness of my own equation (mental note: always test with real numbers) but in defense of my work, I must point out that your value for F(25) is very close to the approximation I gave above, 1/Sqrt(n*Pi) -> .1128.
If n is the number of times you flip a coin, and f(n) is the difference between numbers of occurrences of heads and tails, then for very large, or very small values of n in half the cases f(n) is not zero by definition since half the iterations are an odd number of results. Some proportion of the remainder will be equal, but not all, therefore not equal is overwhelming in probability. I don’t know how to do the math.
The reason why I based my equation on 2n coin flips where n is positive integer was to eliminate odd numbers of coin flips in which there was always a zero probabilty of heads and tail being equal.
Lance Turbo: Yep, the most likely event has probabilty zero, just like all the (infinitely many) other possibilities. Just as you said in your initial post. The joy of calculus!
PaulT, I agree with the first approximation you gave, which was based on Lance Turbo’s original formula, so I’m happy to see that the number which results from it was a good approximation to a known number. (Your second approximation was what I disagreed with.) More importantly, Lance mentioned that for N=65000 F(N) was ‘a smidgen above .002’ and your first formula gives F(n)=1/sqrt(N*pi) =.0022 for N=65000. Sounds like that approximation is working, and 1/sqrt(N) certainly goes to zero as N-> infinity.
I only wish I could show it without the approximation…
Thanks for straightening me out on the binomials – been a while since Calc III.
As for Stirling’s approximation, don’t sweat it too much. #1, it’s accurate enough for large numbers that all of statistical mechanics is based on it. #2, since infinity is the ultimate in large numbers, there, the approximation is perfect =)
Stirling’s approximation is just that, an approximation. However, Stirling’s formula is another matter entirely. (Follow the Stirling’s approximation link above for details)
If you substitute either equation into my F(n), F(n) approaches zero as n approaches infinity. Therefore F(n) approaches zero as n approaches infinity. Provided that Stirling’s formula has been proven, this is proof that if you were to flip a coin forever there is no chance that you would end up with as many heads as tails.
It would be nice if someone checked my manipulation of messy equation #2, but I’m pretty sure that I’m right on.
It would also be nice if parenthetical Tim would pose a question instead of lurking and looking like a genius every couple months. What say you, (Tim)?
Here’s another approach that avoids Stirling’s approximation and ties in an archaic evaluation of pi.
With a little algebra you can find the ratio of f(n+1) to f(n) to be (2n - 1) to (2n).
So since f(1) = 1/2, f(n) = 1/2 * 3/4 * 5/6 * … *(2n-1)/2n.
Compare this to John Wallis’ presentation of 1655: 2/pi = 2/1 * 2/3 * 4/3 * 4/5 * 6/5 * 6/7 * 8/7…
It’s then easy to combine the 2 results and verify PaulT’s approximation of 1/sqrt(n * pi).
I have not been able to find details of Wallis’ derivation. Newton/Leibniz had yet to invent integral calculus and one note I found said he used a ‘cumbersome series of interpolations and inductive procedures.’ Now I can relate to that.