(Mathematicians may find this post painfully obvious.)

I read an interesting puzzle on Stephen Landsburg's blog that generated a lot of disagreement. Stephen offered to bet anyone $15,000 that the average results of a computer simulation, run 1 million times, would be close to his solution's prediction of the expected value.

Landsburg's solution is in fact correct. But the problem involves a probabilistic infinite series, a kind used often on less wrong in a context where one is offered some utility every time one flips a coin and it comes up heads, but loses everything if it ever comes up tails. Landsburg didn't justify the claim that a simulation could indicate the true expected outcome of this particular problem. Can we find similar-looking problems for which simulations give the wrong answer?  Yes.

Here's Perl code to estimate by simulation the expected value of the series of terms 2^k / k from k = 1 to infinity, with a 50% chance of stopping after each term.

my $bigsum = 0;
for (my $trial = 0; $trial < 1000000; $trial++) {
&nbsp; &nbsp; my $sum = 0;
&nbsp; &nbsp; my $top = 2;
&nbsp; &nbsp; my $denom = 1;
&nbsp; &nbsp; do {
&nbsp; &nbsp; &nbsp; &nbsp; $sum += $top / $denom;
&nbsp; &nbsp; &nbsp; &nbsp; $top *= 2;
&nbsp; &nbsp; &nbsp; &nbsp; $denom += 1;
&nbsp; &nbsp; }
&nbsp; &nbsp; while (rand(1) < .5);
&nbsp; &nbsp; $bigsum += $sum;
}
my $ave = $bigsum / $runs;
print "ave sum=$ave\n";

(If anyone knows how to enter a code block on this site, let me know. I used the "pre" tag, but the site stripped out my spaces anyway.)

Running it 5 times, we get the answers

ave sum=7.6035709716983

ave sum=8.47543819631431

ave sum=7.2618950097739

ave sum=8.26159741956747

ave sum=7.75774577340324

So the expected value is somewhere around 8?

No; the expected value is given by the sum of the harmonic series, which diverges, so it's infinite. Later terms in the series are exponentially larger, but exponentially less likely to appear.

Some of you are saying, "Of course the expected value of a divergent series can't be computed by simulation! Give me back my minute!" But many things we might simulate with computers, like the weather, the economy, or existential risk, are full of power law distributions that might not have a convergent expected value. People have observed before that this can cause problems for simulations (see The Black Swan). What I find interesting is that the output of the program above doesn't look like something inside it diverges. It looks almost normal. So you could run your simulation many times and believe that you had a grip on its expected outcome, yet be completely mistaken.

In real-life simulations (that sounds wrong, doesn't it?), there's often some system property that drifts slowly, and some critical value of that system property above which some distribution within the simulation diverges. Moving above that critical value doesn't suddenly change the output of the simulation in a way that gives an obvious warning. But the expected value of keeping that property below that critical value in the real-life system being simulated can be very high (or even infinite), with very little cost.

Is there a way to look at a simulation's outputs, and guess whether a particular property is near some such critical threshold?  Better yet, is there a way to guess whether there exists some property in the system nearing some such threshold, even if you don't know what it is?

The October 19, 2012 issue of Science contains an article on just that question: "Anticipating critical transitions", Marten Scheffer et al., p. 344. It reviews 28 papers on systems and simulations, and lists about a dozen mathematical approaches used to estimate nearness to a critical point. These include:

• Critical slowing down: When the system is near a critical threshold, it recovers slowly from small perturbations. One measure of this is autocorrelation at lag 1, meaning the correlation between the system's output at times T and T-1. Counterintuitively, a higher autocorrelation at lag one by itself suggests that the system is more predictable than before, but may actually indicate it is less predictable. The more predictable system reverts to its mean; the unpredictable system has no mean.
• Flicker: Instead of having a single stable state that the system reverts to after perturbation, an additional stable state appears, and the system flickers back and forth between the two states.
• Dominant eigenvalue: I haven't read the paper that explains what this paper means when it cites this, but I do know that you can predict when a helicopter engine is going to malfunction by putting many sensors on it, running PCA on time-series data for those sensors to get a matrix that projects their output into just a few dimensions, then reading their output continuously and predicting failure anytime the PCA-projected output vector moves a lot. That probably is what they mean.

So if you're modeling global warming, running your simulation a dozen times and averaging the results may be misleading. [1] Global temperature has sudden [2] dramatic transitions, and an exceptionally large and sudden one (15C in one million years) neatly spans the Earth's greatest extinction event so far on the Permian-Triassic boundary [3]. It's more important to figure out what the critical parameter is and where its critical point is than to try and estimate how many years it will be before Manhattan is underwater. The "expected rise in water level per year" may not be easily-answerable by simulation [4].

And if you're thinking about betting Stephen Landsburg $15,000 on the outcome of a simulation, make sure his series converges first. [5]

[1] Not that I'm particularly worried about global warming.

[2] Geologically sudden.

[3] Sun et al., "Lethally hot temperatures during the early Triassic greenhouse", Science 338 (Oct. 19 2012) p.366, see p. 368. Having just pointed out that an increase of .000015C/yr counts as a "sudden" global warming event, I feel obligated to also point out that the current increase is about .02C/yr.

[4] It will be answerable by simulation, since rise in water level can't be infinite. But you may need a lot more simulations than you think.

[5] Better yet, don't bet against Stephen Landsburg.