= 27d567bc2d48d9f40e9ccc20ea370b15)
CCC comments on Anticipating critical transitions - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (52)
The Perl code that you provide will depend a lot on your random number generator. It's worth remembering that most random-number generators aren't; they're pseudo-random-number generators, which are defined in such a way that they mimic a lot of the properties of truly random numbers. (Some random number generators take advantage of external events to generate random numbers - like the timing of keypresses on the keyboard. This type of generator tends to fall back on pseudorandom numbers if it runs out of keyboard-timing-generated random numbers; and for the Perl program that you gave, this type of generator will run out of keyboard-generated random numbers with very high probability).
One property of genuine random numbers that any pseudo-random number generator won't have is the vanishingly small possibility of a sequence of N heads for large N. A pseudo-random number generator will hold a certain amount of state - say, 64 bits. A well-designed 64-bit generator will, in a sequence of 2^64 coinflips, include all possible reasonably short sequences, and a number of suitably random-looking longer ones, with a believable distribution (which means very close to 2^63 heads and 2^63 tails). After that, it will start to repeat itself. What you will not get is 2^64 heads (or 2^64 tails).
So. While the sequence that the Perl program above simulates is potentially infinite, the Perl program itself is not potentially infinite. There is a maximum number of terms that it will consider; therefore a maximum possible value of $sum. And no matter where that maximum value is, such a truncated series does have a finite expected value. Given the results of your run, and this sequence, I expect that your computer's random number generator allows for a series of more or less 1674 'heads' in a row; that would give a truncated series with an expected sum of near to 8.
So the repeatability that you see there is a function of the limitations of the technology, not a function of the problem itself.
Run length finiteness will kick in long before program size finiteness. How long do you expect to have to run before you hit 100 heads in a row by flipping fair coins a trillion times a second?
Roughly speaking, we're talking multiples of the age of the universe so far.
An excellent point. I didn't even think of time.
Whenever you’re thinking that a 64-bit state might not be enough for something counter-like, it’s a good thing to think about time. I remember thinking once for more than half a minute how to handle overflow of a 64-bit variable. It was used to pass the number of files extracted from an archive. On an iPad.
What you say about random number generators is true, but it can't be the explanation, because there were nowhere near enough samples to get a run of 1674 heads in a row. I ran 5 tests with 1 million sequences of coin flips, so the longest run of heads we expect is 21 heads.
The sum would be near 8 even if the numbers were random. I chose that particular series to make that happen. The sum of the entire series diverges, but it diverges slowly enough that sometimes getting 24 heads in a row doesn't change the output a great deal, as you can see from this table showing # of heads, 1/p(getting that many heads in a row), and the resulting contribution to the sum.
Sorry the post originally didn't say there were 1 million trials per run. I had that in the code, but lost it while trying to reformat the code.
You'd have to take more than 5 million trials to see much different numbers. Here's all cases in a series of 240 runs of 1 million trials each where the average sum was greater than 9:
Yes... at one million trials per run, you wouldn't expect much more than 20 flips in a run in any case. By my quick calculation, that should result in an average around 3.64 - with perhaps some variability due to a low-probability long string of, say, 30 heads turning up.
Yet you got an average around 8. This suggests that a long chain of heads may be turning up slightly more often than random chance would suggest; that your RNG may be slightly biased towards long sequences.
So, I wrote a similar program to Phil and got similar averages, here's a sample of 5 taken while I write this comment
8.2 6.9 7.7 8.0 7.1
These look pretty similar to the numbers he's getting. Like Phil, I also get occasional results that deviate far from the mean, much more than you'd expect to happen with and approximately normally distributed variable.
I also wrote a program to test your hypothesis about the sequences being too long, running the same number of trials and seeing what the longest string of heads is, the results are
19 22 18 25 23
Do these seem abnormal enough to explain the deviation, or is there a problem with your calculations?
It's not the highest that matters; it's the distribution within that range.
There was also a problem with my calculations, incidentally; a factor-of-two error, which is enough to explain most of the discreprency. What I did to calculate is, was to add up the harmonic sequence, up to around 24 (1+1/2+1/3+...+1/24), then doubling the last term (1+1/2+1/3+...+1/23 + 2/24). However, the code as given starts out with a 2, and then doubles the numerator with each added term; the calculation I should have used is (2+2/2+2/3+2/4+...+2/23+4/24). That leads to me expecting a value just a little over 7, which is pretty close.
...
I also ran a similar program. I copied and pasted Phil's, then modified it as slightly. My results were:
1 500523
2 250055
3 124852
4 62067
5 31209
6 15482
7 7802
8 4011
9 1978
10 1006
11 527
12 235
13 109
14 68
15 41
16 19
17 10
18 5
21 1
...where the left-hand column is the number of terms in a given sequence, and the right-hand column is the number of times that number of terms came up. Thus, there were 500523 runs of one term each; an insignificant distance from the expected number (500000). Most of the runs were very close to the expected value; interestingly, everything from 14 terms upwards for which there were any runs was above the expected number of runs, and often by a significant margin. The most significant is the single 21-term run; I expect to see 0.476 of those, and I see 1, slightly over twice the expectation. At 15 terms, I expected to see 30.517 runs; I saw 41 of those. At 17 terms, I expect to see 7.629 on average; I see 10 this time.
My final average sum is 7.25959229425851; a little higher than expected, but, now that I've corrected the factor-of-two error in my original calculation, not unexpectedly far off.
So most of the deviation is due to an error in my calculation. The rest is due to the fact that a 21-term or longer run turning up - which can easily happen - will probably pull the average sum up by 1 or more all by itself; it's easier for the average sum to be increased than decreased.