Vaniver comments on Anticipating critical transitions - Less Wrong

17 Post author: PhilGoetz 09 June 2013 04:28PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (52)

You are viewing a single comment's thread. Show more comments above.

Comment author: CCC 10 June 2013 08:54:56AM 4 points [-]

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.

Comment author: Luke_A_Somers 10 June 2013 01:12:44PM *  6 points [-]

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.

Comment author: CCC 11 June 2013 09:36:41AM 0 points [-]

An excellent point. I didn't even think of time.

Comment author: bogdanb 15 June 2013 09:17:43PM *  3 points [-]

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.