The draws aimed at the tail

The probability that a standard normal variable exceeds 5 is 2.8665×10⁻⁷, about three in ten million. It is not an exotic number. It is the far end of the normal curve itself, the region where every approximation in the subject converges last, and the region a rare-event probability — a failure rate, an extreme loss, a false alarm at a strict threshold — lives in.

A simulation that draws standard normals and counts how many exceed 5 is correct in principle and useless in practice. The essays before this one on a simulation’s own error assumed the event of interest happened often enough to be counted. Here it happens so rarely that a very large simulation sees it a handful of times, and a smaller one never.

The standard repair is to draw from a distribution aimed at the tail and to weight each draw back by how much likelier the aimed distribution made it. Done well it is one of the largest free improvements in computation. Done slightly wrong it produces an estimate that looks stable, an interval that does not cover, and a diagnostic that says everything is fine.

What plain draws cannot see #

A plain simulation estimates the probability by the share of draws past 5. Its relative error per draw is $\sqrt{(1-p)/p}$, which at this probability is about 1,868, so a ten per cent relative error needs 348,855,479 draws. In the figure, a hundred thousand plain draws produce nothing past 5 at all, and the plain estimate sits at zero the whole way.

Zero is also where its interval sits. With no draw past the threshold the estimate is 0 and the usual standard error, $\sqrt{\hat p(1-\hat p)/R}$, is 0 too, so the nominal 95% interval is the single point zero — the degenerate case of the interval for a proportion that misses at the edges. A simulation of a thousand draws sees nothing on 99.97% of runs and its interval covers the truth 0.029% of the time. At a million draws it still sees nothing on 75.08% of runs and covers 24.9%. The method is not biased; it is blind, and its interval reports the blindness as certainty.

Drawing where the event is, and weighting it back #

Importance sampling draws x from a proposal density q instead of the normal, and counts each draw past 5 not as one but as $w(x) = \varphi(x)/q(x)$, the ratio of how likely the draw was under the normal to how likely it was under the proposal. The average of those weighted indicators is an unbiased estimate of the tail probability for any proposal that puts density everywhere the normal does past 5.

Unbiasedness is cheap. What decides whether the method works is the variance, and the variance is set by one integral, the second moment of a weighted draw:

$$m_2 = \int_5^\infty \frac{\varphi(x)^2}{q(x)}\,dx .$$

For a normal proposal $N(m, s^2)$ that integral has a closed form, and the closed form contains a condition. The exponent of the integrand has a term in $x^2$ with coefficient $1/(2s^2) - 1$, so the integral is finite only when $s > 1/\sqrt 2$. A proposal narrower than about 0.707 has an infinite variance, whatever its centre. Everything below is a consequence of those two facts: a finite second moment in closed form for wide enough proposals, and none at all for narrow ones.

The error of a shift, in closed form #

For a unit-variance proposal centred at m, the relative error per draw is $\sqrt{e^{m^2}Q(5+m)/p^2 - 1}$, with Q the upper normal tail — a curve that can be drawn exactly.

At m = 0, plain simulation, the error per draw is 1,868. Centred at 3 it is 7.768; at 4, 3.347; at 5, on the threshold, 2.383. The best centre on a fine grid is 5.097, just past the threshold, where the error per draw is 2.376 and a ten per cent relative error needs 565 draws. Against 349 million for plain simulation that is a saving of a factor of more than six hundred thousand, from a single change of distribution.

The position of that optimum is not arbitrary, and it says where the probability being estimated actually is. Given that a standard normal exceeds 5, its expected value is $\varphi(5)/Q(5)$, which is 5.187: the event almost always happens within a fraction of a unit past the threshold, because the normal density falls so steeply out there that most of its remaining mass is crowded against the edge. The best unit-variance proposal sits between the threshold and that conditional mean — close enough to the edge to land draws where the mass is, far enough past it that half its draws are not wasted below 5. A proposal is good exactly to the extent that it looks like the normal restricted to the event, and the rest of this essay is what happens when it does not.

It is worth setting this beside the other way of reaching past the observations. A return level read beyond the longest record has to extrapolate a fitted shape into a region with no data in it, and inherits every error in the fit. Importance sampling needs no extrapolation at all, because the distribution is known and only its integral is hard; what it needs instead is a proposal whose tails are no lighter than the target’s where the integral lives. The two methods fail in opposite places — one where the model is uncertain, the other where the proposal is too confident — and the second failure is the one that looks like success.

Past the optimum the error rises again, and fast: 3.004 at 6, 6.343 at 7, 21.52 at 8 and 119.5 at 9. Aiming too far is a failure of its own, taken up below, and it is already visible in the closed form.

The closed form has a route that shares nothing with it. Six hundred runs of ten thousand draws from the proposal centred at 5, each recovering its own second moment from its sample variance, average 5.4715×10⁻¹³ against a closed form of 5.4867×10⁻¹³ — three parts in a thousand apart. And the proposal’s nominal interval covers 94.3% at a thousand draws and 94.7% at ten thousand, as it should.

Aimed past the tail #

A proposal centred at 9 has a finite second moment — its spread is one — and a relative error per draw of 119.5, which in principle only means it needs more draws. In practice it fails in a way the error formula does not predict at the sizes anyone would run.

Nearly every one of its draws lands past 5, but almost all of them land far past 5, where the normal’s density is negligible and the weights are tiny. The rare draw that lands just past 5, where most of the probability actually is, carries an enormous weight. So a typical run has not yet drawn the draws that matter: at a thousand draws the median run estimates 0.0325 of the true probability, and at ten thousand, 0.4986. The mean is right, carried by a few runs that happened to land near the threshold; the typical run is off by an order of magnitude, and 100.0% of the interval’s misses are underestimates.

Its interval covers 19.3% at a thousand draws and 54.5% at ten thousand. Here the standard diagnostic does its job. The effective sample size of the weights, $(\sum w)^2/\sum w^2$ — the number of equally weighted draws the weighted sample is worth — is 0.16% of the draws at a thousand and 0.02% at ten thousand, and in the median run a single draw carries 76.6% of the total weight at a thousand. Any analyst who printed it would stop. The failure in this case is loud.

Too narrow: an infinite variance that shows #

Take a proposal centred just below the threshold with a small spread, $N(4.5, 0.25^2)$. It looks careful — it concentrates draws where the event begins — and its spread is under 0.707, so its second moment is infinite. Where that infinity lives can be located exactly: the integrand stops falling and turns upward at $x^* = m/(1 - 2s^2)$, which for this proposal is 5.143, just past the threshold.

Its interval covers 85.2% at a thousand draws, 86.0% at ten thousand and 81.3% at a hundred thousand. More draws do not help; the coverage does not climb, and at the largest size it is lowest. Every miss at ten thousand and a hundred thousand draws is an underestimate, and the typical run estimates 0.900, 0.958 and 0.983 of the truth at the three sizes — closing on the answer slowly, from below, while the interval around it stays too narrow.

The mechanism is the one a sum of Cauchy draws has: a variable with no finite variance has no central limit theorem at the usual rate, and a standard error computed from its sample is an estimate of a quantity that does not exist. Each run’s sample variance is finite, so each run reports a finite interval, and that interval is built from the part of the weight distribution the run happened to draw. The rare, very large weights that would have widened it are exactly the ones a run of any given size usually lacks, which is why the typical run is low and its interval does not reach up to the truth.

The diagnostic that reads healthy #

The effective sample size flagged the proposal aimed past the tail. It does not flag this one, and a control makes the failure precise.

The control is $N(3, 1)$. It lands exactly the same share of its draws past the threshold as the narrow proposal — 2.28%, since both centres sit two of their own spreads below 5 — and it has a finite second moment. At ten thousand draws its effective sample size is 1.62% of all draws and 71.6% of those that landed, and its interval covers 93.3%. The narrow proposal’s effective sample size is 1.20% of all draws and 52.9% of those that landed, and its interval covers 86.0%. By the diagnostic the two are nearly the same, and the narrow one looks only modestly worse; by the coverage, one works and the other does not.

The proposal that works best is worse again by the diagnostic. $N(5, 1)$ has an effective size of 14.96% of all draws and 29.9% of those that landed — lower, as a share of useful draws, than the failing narrow proposal — and covers 94.7%. A reader ranking these three proposals by effective sample size among the draws that landed would put the failing one in the middle and the best one last.

The effective sample size measures how unequal the weights that were drawn are. An infinite variance is a statement about weights that were mostly not drawn, and no statistic computed from a run’s own weights can see a draw that did not happen. That is the same limit as a resample that cannot contain a value larger than the largest one observed, arriving in a method whose whole purpose was to see past the observations.

An infinity that does not show #

The last proposal separates two things that the previous section might suggest are the same: having an infinite variance, and failing because of it. $N(5, 0.3^2)$ is narrower than 0.707, so its second moment is infinite too. Its interval covers 94.3%, 95.0% and 95.3% at the three sizes, and its effective sample size is a healthy 86.3% of its landed draws. By every measure a run can compute, it is the best proposal in the set.

The difference is where each infinity starts. This proposal’s integrand turns upward only past 6.098, and its draws, centred at 5 with a spread of 0.3, almost never reach that far: the typical largest of a hundred thousand of them is 6.279, barely into the region, where the integrand has only begun to rise. So the part of the second moment a run can see is finite and stable. Integrated up to each run’s reach, it implies a relative error per draw of 1.135 at a thousand draws and 1.148 at a hundred thousand, and the second moments counted from the runs themselves move by a factor of 1.046 over that range.

The narrow proposal’s integrand turns upward at 5.143, inside the region its draws reach, so every increase in the number of draws uncovers more of the divergence. Its visible relative error per draw rises from 5.456 at a thousand draws to 9.488 at a hundred thousand, and the counted second moments grow by a factor of 6.550. For comparison, the two finite proposals settle where their closed forms say: $N(3, 1)$ at 7.768 and $N(5, 1)$ at 2.383.

So an infinite variance is not what makes a proposal fail at a given size. What fails is a divergence that sits inside the region the draws reach, where it keeps adding weight that the run’s variance estimate chases and never catches. A divergence beyond reach is a real mathematical property of the proposal and an invisible one in practice — invisible until some run large enough to reach it, of a size this essay does not attempt, finally draws a weight out there.

Which of these are theorems and which are counts #

Proved. The weighted estimator is unbiased for any proposal with density wherever the normal has it past 5. The second moment of a normal proposal is finite if and only if its spread exceeds $1/\sqrt 2$, and when finite it has the closed form used for every error-per-draw figure. The point where an infinite integrand turns upward is exact.

Computed exactly. The tail probability, by a continued fraction checked against the incomplete gamma function at 3, 4 and 5 and against the asymptotic series at 10, where the ordinary normal distribution function has run out of digits. The plain simulation’s blindness at a thousand and a million draws, by summing the binomial. The visible second moment, by integration in logarithms up to the typical reach of R draws.

Counted. Every coverage, median ratio, share of misses below the truth and effective sample size is a count over runs from stated seeds, with the numbers of runs given in each figure. The claim that the hidden proposal covers is a count at three sizes and no more; nothing here shows that it covers at every size, and it cannot at a size large enough for its draws to reach the divergence.

What a report of an importance-sampling estimate should carry #

Four things, of which the usual report carries one.

The proposal, and whether its variance is finite. For normal proposals that is a single inequality on the spread. For a proposal chosen by fitting, it is a condition on the tails of the proposal against the tails of the target, and it should be checked rather than assumed.

The largest single weight as a share of the total. It was the loud signal for the proposal aimed past the tail, and unlike the effective sample size it does not average away the draws that matter.

The estimate at more than one number of draws. The narrow proposal’s typical estimate rose from 0.900 to 0.983 of the truth between a thousand and a hundred thousand draws while its interval stayed confident at each size. A trend in the estimate with the number of draws is the symptom a single run hides.

A check against a case with a known answer. Everything in this essay was possible because the tail of a normal is known exactly. A proposal family used for an unknown probability should first be run on a known one of similar shape, which is the discipline a stated seed exists to make checkable.

Where this goes next: a proposal chosen by the draws it weights #

Every proposal here was fixed before any draw was made. In practice the proposal is usually chosen adaptively: draw a batch, find where the draws past the threshold landed, move the proposal there, and repeat — the cross-entropy method and its relatives. That makes the proposal a function of the same random draws it is then used to weight, which is the pattern of a rule that looks at the data before deciding in a new place.

The measurement that would settle whether adaptation is safe is the coverage of the final estimate’s interval, counted at a known tail probability, when the proposal was fitted from earlier batches of the same run, against the same proposal fixed in advance — and, in particular, whether an adaptive scheme can fit its way into the narrow, infinite-variance region that looked so reasonable here. It is distinct from this essay because the question is no longer which proposal fails, but whether a procedure that chooses its own proposal can be trusted to avoid the ones that do.