An approximation built at the threshold

A correction that goes below zero measured the Edgeworth expansion on an exponential sum and found the reason it cannot reach far into a tail: every correction is a polynomial times the normal density, built at the mean, so its error is organised in powers of $z^3/\sqrt{n}$ and grows with the threshold. Two terms at a hundred draws were good to 4.11 standard deviations and gave a fifth of the true tail at six.

The tail converges last says that saddlepoint methods “do substantially better again”. This essay measures how much better, on the same source, and asks why.

The number first #

At ten draws, six standard deviations above the mean, the exact tail of the standardised sum is $1.47 \times 10^{-5}$ — about one and a half in a hundred thousand. The three approximations give:

The normal is short by a factor of fifteen thousand. Two Edgeworth terms are short by a factor of sixty. The saddlepoint is seven hundredths of a per cent too large.

At five draws the gap is wider still. Six standard deviations out the saddlepoint’s ratio is 1.0019 while the normal’s is $1.63 \times 10^{-5}$ — short by a factor of more than sixty thousand — and the saddlepoint’s error at one standard deviation is 0.035%, so moving the threshold out by five standard deviations has multiplied its error by about five, and the normal’s — read as a fold, how many times too small — by more than a million.

What the approximation does #

The normal approximation to a sum is good near the mean and bad far from it. The saddlepoint’s idea is to avoid asking the normal about a place it is bad at, by moving that place to the mean.

A sum’s distribution can be tilted: reweight every outcome $s$ by $e^{ts}$ and renormalise. Tilting by a positive $t$ shifts the whole distribution upward. For each threshold there is exactly one tilt that makes the threshold the tilted distribution’s mean, and it is found by solving

$$K'(\hat t) = s$$

where $K(t) = \log E\,e^{tS}$ is the cumulant generating function of the sum. For $n$ unit exponentials $K(t) = -n\log(1 - t)$ and the equation has the closed-form root $\hat t = 1 - n/s$.

Under that tilt, the threshold sits at the centre, where the normal approximation is at its most accurate, and a tail probability can be read off and tilted back. Lugannani and Rice’s version does the tilting and un-tilting in one formula:

$$P(S \ge s) \;\approx\; 1 - \Phi(w) + \varphi(w)\left(\frac{1}{u} - \frac{1}{w}\right), \qquad w = \operatorname{sign}(\hat t)\sqrt{2\bigl(\hat t\, s - K(\hat t)\bigr)}, \quad u = \hat t\sqrt{K''(\hat t)}$$

The normal is still being used. What has changed is where. The Edgeworth expansion corrects the normal at the mean and extrapolates the correction to the threshold. The saddlepoint uses a fresh normal approximation at every threshold, so no reading is ever an extrapolation, and the error at six standard deviations has the character of the error at the centre.

Why the error does not grow #

The relative error of the saddlepoint approximation is of order $1/n$ and, over a range of thresholds that grows with $n$, that order holds uniformly in the threshold. It is a theorem about the method rather than a finding here; what is measured is how close to flat the error is in practice on this source:

The saddlepoint’s error grows as the threshold moves out — by a factor of ten on a single draw and five at five draws — and the growth is bounded. The normal’s grows by a factor of two hundred thousand over the same range. The ratio of the two numbers is the difference between an approximation whose error is an expansion about the threshold and one whose error is an expansion about the mean.

The same fact shows in how far each method stays within a tolerance of the truth.

At 5% tolerance the normal reaches a little over one standard deviation at a hundred draws and two Edgeworth terms reach between three and four. The saddlepoint was searched out to twelve standard deviations at every size from ten draws to a hundred thousand and never left the band. There is no sample size in the range at which the other methods catch it, because its range is not a function of the sample size in the same way.

Why the order is one over n with nothing attached #

The normal approximation’s relative error at a fixed threshold is of order $1/\sqrt{n}$, and one Edgeworth term brings it to $1/n$ — but a $1/n$ multiplied by a polynomial in $z$ that grows as the threshold moves out. The saddlepoint’s error is also of order $1/n$, with no polynomial attached. The reason is an Edgeworth expansion hiding inside the saddlepoint, evaluated at the one place it is kindest.

After tilting, the approximation reads the tilted distribution’s density at that distribution’s own mean. An Edgeworth expansion of a density at its mean has a first correction proportional to the skewness times $(z^3 - 3z)$, and at $z = 0$ that polynomial is exactly zero. The skewness term vanishes identically at the centre. The first correction that survives is the $1/n$ one, carrying the kurtosis and the square of the skew.

So the saddlepoint is not a different theory from the expansion measured in the essay before this one. It is that expansion used only at $z = 0$, where the term that made the one-term correction overshoot and go negative contributes nothing, and it is used there at every threshold by moving the threshold to the centre first. The price of the move is the cumulant generating function, which is what the tilt needs and the plain expansion does not; the reward is that the growing polynomials in $z$ never appear, because $z$ is always zero where the expansion is read.

One draw, where there is nothing to average #

The central limit theorem is a statement about sums of many things, and the normal approximation is only as good as the sum is long. So the sharpest test of whether the saddlepoint is riding the limit theorem or doing something else is a sum of one.

A single exponential draw has a tail of $e^{-(1+z)}$ above its mean plus $z$ standard deviations. It is as far from a normal as a continuous distribution on the positive half-line gets; the normal approximation to its tail at four standard deviations is off by a factor of more than two hundred. The saddlepoint approximation, applied to that single draw, gives

Within 2.2% at ten standard deviations, with no averaging at all. Nothing about that can be a consequence of the limit theorem, because there is no limit being approached. It is a consequence of the tilt. Tilting an exponential gives another exponential, so at every threshold the approximation is the same normal approximation to the same shape, made at its mean — and its error cannot grow without bound however far out the threshold is.

The bound can be named. Far enough out the ratio settles on $\Gamma(n)$ divided by Stirling’s approximation to it, which is 1.0844 for a single draw, 1.0422 for two and 1.0168 for five; at three hundred standard deviations the single draw has reached 1.0653 and is still climbing towards it. So the saddlepoint’s error on a gamma sum is never worse than Stirling’s error at the same $n$, and Stirling’s error shrinks like $1/(12n)$ — which is the $1/n$ in the table above, arrived at from the other end.

The gamma family is the saddlepoint’s best case, and it would be misleading to stop there. The saddlepoint density of a gamma sum is exact up to a constant — Stirling’s approximation to the gamma function — which is part of why these numbers are so good.

A source that is not the best case #

A binomial is a lattice, it is skewed away from a proportion of one half, and its moment generating function does not give the saddlepoint a closed-form root in the convenient way a gamma does. It is also the distribution on which a proportion’s interval oscillates and on which the Berry–Esseen bound is nearly tight, so it is a fair place to look for the method failing.

The continuity correction matters here — it is applied to both methods, since without it the normal is unfairly handicapped by the half-step that the Berry–Esseen constant was written for. With it:

The last row is a binomial with an expected count of one. Its whole distribution sits on the values 0, 1, 2 and a thin tail, and the upper tail at five standard deviations is the probability of six or more events. The normal gives 0.59% of it. The saddlepoint is within 1.1% at every threshold.

The pattern across the rows is the one the gamma showed. The error of the saddlepoint grows as the source gets more skewed and more discrete — from 0.02% to 1.1% — and it does not grow as the threshold moves out: at a proportion of 0.02 its error is largest at one standard deviation and smallest at five.

Two readings a decision would make #

The ratios are abstractions until a decision hangs on one, so here are two.

Thirty waiting times. The essay on the Edgeworth correction took thirty measurements from an exponential source and a one-sided test whose statistic landed 2.58 standard errors above the null mean. The normal table reported a p-value of 0.50%; the exact tail is 1.031%; one Edgeworth term with the true skewness gave 1.00% and two gave 1.06%. The saddlepoint gives 1.031% — the same to three significant figures, an error of five thousandths of a per cent of the p-value. At a threshold this close in, the Edgeworth correction was already good enough for any decision, so the saddlepoint’s advantage is invisible here. It is worth seeing that it costs nothing either: the method that is right six standard deviations out is also right at two and a half.

Nine adverse events in a hundred patients. A background rate of 2% predicts two events in a hundred, and a trial reports nine. The question is how surprising nine is if nothing has changed — the upper tail of a binomial at a hundred trials and a proportion of 0.02, from nine. The exact answer is $1.89 \times 10^{-4}$, a little under two in ten thousand.

The continuity-corrected normal approximation gives $1.72 \times 10^{-6}$. It says the observation is a hundred and ten times more surprising than it is — the difference between a signal that warrants a look and one that would stop a trial. The saddlepoint gives $1.90 \times 10^{-4}$, three tenths of a per cent from the exact sum.

Neither reading is exotic. Small counts against a small background rate are the ordinary shape of safety monitoring, of a rare event in a large sample, and of every surveillance statistic that flags a cluster. They are also exactly where the normal approximation is furthest from the truth and where a skewness correction built at the mean has the least room to work, because the expected count is so close to the floor at zero that the whole distribution is a short tail and a long one.

What it costs #

If the saddlepoint is this good, the question is why a normal table is what everyone uses. The answer is three things the normal approximation does not need.

It needs the cumulant generating function. The normal approximation needs a mean and a variance, which can be estimated from almost anything. The saddlepoint needs $K(t)$ as a function, which is available in closed form for sums of known distributions — gamma, binomial, Poisson, negative binomial, the weighted sums of chi-squares that quadratic forms produce, compound sums in insurance — and not otherwise.

It needs a root at every threshold. $K'(\hat t) = s$ is solved afresh for each reading. For the gamma it has a closed form; for most sources it is a one-dimensional root-find, which costs nothing on a computer and is exactly the sort of step a printed table could never contain. That is the historical reason the method is little taught, and it is the same reason the exact binomial sum was once avoided.

It is an approximation to a known distribution, not an estimate of an unknown one. Every number above takes the source’s distribution as given and approximates the distribution of its sum. When the source is unknown and only a sample is available, the cumulant generating function has to be estimated from the sample, and then the approximation is only as good as that estimate — which, in the far tail, depends on large values the sample may never have contained. That is the same wall the bootstrap runs into, and it is not a property of the saddlepoint.

Where this leaves the normal approximation #

The three measurements — the bound, the expansion and the saddlepoint — make a single statement between them. The normal approximation’s error on a skewed sum is set by the skewness and lives at the centre, where a uniform bound cannot distinguish it from a tail error. A correction built at the centre fixes the centre and a band around it that widens as the sixth root of the sample. An approximation rebuilt at each threshold has an error that barely depends on the threshold at all.

So the choice is not between the normal and something more complicated. It is between an approximation built in one place and read everywhere, and one built where it is read. When the distribution of the thing being summed is known — a p-value computed from a model, a count under a hypothesised rate, a sum of squared normal scores — the second is available at the cost of one root-find, and every figure on this page says what it buys.

The measurements, and their limits #

The saddlepoint’s relative error stays under half a per cent out to six standard deviations at five, ten, thirty and a hundred exponential draws, and at each of those sizes the normal’s error six standard deviations out is more than twenty times the saddlepoint’s worst.

On a single draw it stays under 2% and grows by less than a factor of twelve from one to six standard deviations. That is the comparison that separates the tilt from the limit theorem, and it is stated with the single draw’s own larger error rather than borrowed from the larger sums.

On a lattice it is at least as close as the continuity-corrected normal at every threshold measured, across five proportions at a hundred trials.

Not claimed: that the saddlepoint is this accurate on sources whose generating function is not known, or on a statistic that is not a sum — a studentised mean or a maximum likelihood estimate needs a different construction, which exists and is not measured here. And not claimed that the uniform $1/n$ order holds at every threshold whatever: the theory gives it over a range growing with $n$, and the twelve-standard-deviation edge of the search is where this measurement stops, not where the method does.

Every number is exact on both sides of each ratio — an incomplete gamma function or a binomial sum for the truth, a closed formula or a one-dimensional root for the approximation — so nothing here carries simulation error.

Still open: the saddlepoint with only a sample #

The limit named above is the practical one. A reader with thirty observations and no model has an empirical cumulant generating function, $\hat K(t) = \log \frac{1}{m}\sum e^{t x_i}$, and can run the same tilt on it. That empirical saddlepoint is known to approximate the bootstrap distribution of the mean without resampling, so it inherits the bootstrap’s accuracy rather than the saddlepoint’s.

What that accuracy is in the tail is measurable against exact tails like the ones above, and has not been measured. The empirical tilt cannot move past the largest observation, since no reweighting of a sample can make its mean exceed its maximum, so there is a hard edge to the thresholds it can read at all. Inside that edge, the question is how much of the saddlepoint’s flat error survives the estimation of $K$, and whether a far-tail reading from a sample is better served by an empirical tilt or by a fitted tail model that extrapolates on purpose.

The second open question is a statistic that is not a sum. A t statistic divides by an estimated spread, and the coupling between the two is what unbalances an interval’s tails on skewed data. Saddlepoint approximations for such ratios exist and are harder to write down; how far their error stays flat, on the same exponential source where the t interval misses low four times as often as high, would join the two halves of this collection’s account of skew.