random numbers, large sets, and distribution

[CycloWizard]

Originally posted by: TuxDave
I'm just doing: Limit as n goes to infinity of

[number of situations of n heads in 2n tosses]/[total number of possibilities].

to prove that as you go to an infinite number of tosses, the probability of getting n heads out of 2n coin tosses does not go to 1.

I'm not clear on where and how I'm using an incorrect distribution type.

I wasn't sure, and I can't seem to find a statistics book anywhere around here, so I (being SuperDork®), decided I'd write a MATLAB program that tested it really quickly. I had 1000 sets of coin tosses with each set containing 1,000,000 tosses. This lets you look at the results from a smaller sample (a million tosses) and the results from a larger sample (a billion tosses). The results:
1000 sets of tosses:
More Heads: 483
More Tails: 517

Overall count:
Heads: 499975993
Tails: 500024007

The code I used:
<code>
for j=1:10^3
for i=1:10^6
seed=rand();
if seed<0.5
Heads(j)=Heads(j)+1; %heads
else
Tails(j)=Tails(j)+1; %tails
end
end
end

sumHeads=0;sumTails=0;
Headswins=0;Tailswins=0;
for k=1:10^3
if Heads(k)>Tails(k)
Headswins=Awins+1;
else
Tailswins=Tailswins+1;
end
sumHeads=Heads(k)+sumA;
sumTails=Tails(k)+sumB;
end
[Headswins,Tailswins]
sumHeads
sumTails
</code>

edit: Do the code tags only work in software, or did I forget what the right tag is?

 

[PowerEngineer]

Originally posted by: TuxDave
I'm not so sure that the probability of getting a perfect distribution goes to 1 as your number of samples goes to infinity. Look at a case of a coin toss where the perfect distribution is half heads and half tails.

Given 2n tosses, the total combinations where exactly half are heads is (2n)!/(n!*n!)

The total number of possible results is 2^2n.

Therefore the probability of exactly half heads is 2n!/[n!*n!*2^2n] and as n goes to infinitely the probability goes towards 0. (ok I'm not 100% sure it goes to zero but it looks like it)

Intuatively, this result seems wrong. Here's a link that uses a somewhat different calculation. I'm way too rusty on probability to comment.

 

[TuxDave]

Originally posted by: PowerEngineer

Originally posted by: TuxDave
I'm not so sure that the probability of getting a perfect distribution goes to 1 as your number of samples goes to infinity. Look at a case of a coin toss where the perfect distribution is half heads and half tails.

Given 2n tosses, the total combinations where exactly half are heads is (2n)!/(n!*n!)

The total number of possible results is 2^2n.

Therefore the probability of exactly half heads is 2n!/[n!*n!*2^2n] and as n goes to infinitely the probability goes towards 0. (ok I'm not 100% sure it goes to zero but it looks like it)

Intuatively, this result seems wrong. Here's a link that uses a somewhat different calculation. I'm way too rusty on probability to comment.

Um, the link you provided uses the same equation that I use and if you're willing to extrapolate, the conclusions are the same. We know that getting 1 head in 2 tosses is equal to 50%. From the link, getting 10 heads in 20 tosses is 17.62% so you see it supports my trend that the larger the sample size, the lower the probability of getting exactly half heads.

 

[TuxDave]

Originally posted by: CycloWizard

Originally posted by: TuxDave
I'm just doing: Limit as n goes to infinity of

[number of situations of n heads in 2n tosses]/[total number of possibilities].

to prove that as you go to an infinite number of tosses, the probability of getting n heads out of 2n coin tosses does not go to 1.

I'm not clear on where and how I'm using an incorrect distribution type.

I wasn't sure, and I can't seem to find a statistics book anywhere around here, so I (being SuperDork®), decided I'd write a MATLAB program that tested it really quickly. I had 1000 sets of coin tosses with each set containing 1,000,000 tosses. This lets you look at the results from a smaller sample (a million tosses) and the results from a larger sample (a billion tosses). The results:
1000 sets of tosses:
More Heads: 483
More Tails: 517

Overall count:
Heads: 499975993
Tails: 500024007

The code I used:

...

Edit: Woops, I misunderstood your results. So in your 1000 set of coin tosses each one containing 1mil tosses, you got NONE of them to be an equal number of heads and tails. If you choose to use my equation, the probability of that happening is a hellishly small number that I have no idea how to calculate due to my usage of factorials.

Edit x2: You may want to fix your code and rerun.

if Heads(k)>Tails(k)
Headswins=Awins+1;
else
Tailswins=Tailswins+1;
end

You need to keep 3 tallies. Heads > Tails, Tails > Heads, Tails = Heads. Otherwise you bias your results slightly towards Tails.

 

[CSMR]

Originally posted by: TuxDave
Um, the link you provided uses the same equation that I use and if you're willing to extrapolate, the conclusions are the same. We know that getting 1 head in 2 tosses is equal to 50%. From the link, getting 10 heads in 20 tosses is 17.62% so you see it supports my trend that the larger the sample size, the lower the probability of getting exactly half heads.

Not hard to show the probability is decreasing, just divide the nth term by the (n-1)th.
To show it goes to zero, you can:
-Use stirlings formula which gives the asymptotic approximation 1/(root(n*pi)).
-Use the central limit theorem (root n) times P(proportion of heads=1/2) -> P(N=0) where N is normal(0,1)=0.
-Do this:
P(n heads out of 2n) tends to some l because it is a decreasing sequence.
P(n+k heads out of 2n)=(2n)!/((n+k)!(n-k)!2^(2n))
P(n+k heads out of 2n)/P(n out of 2n heads)=(n!^2)/((n+k)!(n-k)!)=[(n-1)(n-2)...(n-k)]/[(n+1)...(n+k)] tends to 1 as n->inf for any k.
So P(n+k heads out of 2n) tends to l as n tends to infinity for any k.
P(between n+1 and n plus p heads out of 2n) tends to p*l which must be less than 1. This happens for any p so l must be 0.

 

[PowerEngineer]

Originally posted by: TuxDave
Um, the link you provided uses the same equation that I use and if you're willing to extrapolate, the conclusions are the same. We know that getting 1 head in 2 tosses is equal to 50%. From the link, getting 10 heads in 20 tosses is 17.62% so you see it supports my trend that the larger the sample size, the lower the probability of getting exactly half heads.

Dang...

On further review, I guess that does make sense. As the number of flips increases towards infinity then the number of possible outcomes also goes to infinity. It follows that the probability of any single outcome (not just the "exactly half heads" outcome) must go towards zero. I'd hope that the outcomes nearer to "exactly half heads" would have greater probablities than those further away (even as they approached zero).

I'll try to remove more "rust" before posting next time.

 

[nortexoid]

It is possible in the logical sense (since space and time are finite, so not in the physical sense) to flip heads infinitely many times. Now, it is only possible because of the randomness of the event (assuming that it is random). According to a probability calculus, however, the probability tends to zero as the tosses approach omega (the "limit"). (I'm not sure if that previous statement makes sense when substituting an ordinal larger than omega for omega. Recall that the set of natural numbers forms an omega sequence of the least infinite cardinality.) That's a low probability. But nobody said that the concepts denoted by the terms "possibility" and "probability" were equivalent, neither extensionally nor, surely, intensionally.

 

[TuxDave]

Originally posted by: CSMR

Originally posted by: TuxDave
Um, the link you provided uses the same equation that I use and if you're willing to extrapolate, the conclusions are the same. We know that getting 1 head in 2 tosses is equal to 50%. From the link, getting 10 heads in 20 tosses is 17.62% so you see it supports my trend that the larger the sample size, the lower the probability of getting exactly half heads.

Not hard to show the probability is decreasing, just divide the nth term by the (n-1)th.
To show it goes to zero, you can:
-Use stirlings formula which gives the asymptotic approximation 1/(root(n*pi)).
-Use the central limit theorem (root n) times P(proportion of heads=1/2) -> P(N=0) where N is normal(0,1)=0.
-Do this:
P(n heads out of 2n) tends to some l because it is a decreasing sequence.
P(n+k heads out of 2n)=(2n)!/((n+k)!(n-k)!2^(2n))
P(n+k heads out of 2n)/P(n out of 2n heads)=(n!^2)/((n+k)!(n-k)!)=[(n-1)(n-2)...(n-k)]/[(n+1)...(n+k)] tends to 1 as n->inf for any k.
So P(n+k heads out of 2n) tends to l as n tends to infinity for any k.
P(between n+1 and n plus p heads out of 2n) tends to p*l which must be less than 1. This happens for any p so l must be 0.

I like the 'i put in a large number for 2n and it looked really small and therefore we can conclude zero'. I kid I kid...

 

[CycloWizard]

Originally posted by: TuxDave
Edit: Woops, I misunderstood your results. So in your 1000 set of coin tosses each one containing 1mil tosses, you got NONE of them to be an equal number of heads and tails. If you choose to use my equation, the probability of that happening is a hellishly small number that I have no idea how to calculate due to my usage of factorials.

Edit x2: You may want to fix your code and rerun.

if Heads(k)>Tails(k)
Headswins=Awins+1;
else
Tailswins=Tailswins+1;
end

You need to keep 3 tallies. Heads > Tails, Tails > Heads, Tails = Heads. Otherwise you bias your results slightly towards Tails.

Right - none of them are exactly equal. But, if you look at the net tally of head vs tails, they are only different by 24,000 or so out of 10^9 samples. If I could spare the CPU time, I'd run a larger number of samples and see how it comes out. I doubt it would ever be an exact match, but I don't think there will be a runaway trend, either. You're right about the code too... I just got lazy. I'll try again with 10^12 or so after my current simulation is done, since I think that's the last sim I can run for a while anyway.