Saddlepoint Approximation
和Edgeworth展开相比，鞍点近似是更加精细的分布近似方法，鞍点近似同时适用于连续和离散的分布。在许多极端的条件下，鞍点近似都表现出惊人的精度。鞍点近似有许多角度的理解，然而下面的推导展示了鞍点近似和Edgeworth的关系，以及它为什么具有高精度。
Tilted Exponential Families
设 $f(x)$ 是一个密度函数，在区间 $(a,b)$ 具有矩母函数 $M(s) = E e^{sX} $ 和累量母函数 $ K(s) = \log M(s) $。则下列指数分布族称为 tilted 正则指数族 $$ f(x;s) = \exp \{ sx - K(s) \} f(x), \qquad s \in (a,b) $$
$f(x;s)$ 称作 s-tilted 密度，用 $X_s$ 表示服从此密度的一个随机变量。容易推导 $X_s$ 的 均值和方差满足
$$ E(X_s) = K’(s)$$ $$ Var(X_s) = K’’(s)$$
以及 $X_s$ 的高阶标准化累量
$$ \kappa_i(s) = {K^{(i)}(s) \over \{ K’’(s) \}^{i/2} }, \qquad i \geq 3 $$
Saddlepoint Approximation
由 tilted 指数族定义可知
$$ f(x) \equiv \exp \{ K(s) -sx \} f(x;s), \qquad \forall s \in (a,b) $$
注意这里是对任意的 s，两边都是一样的密度函数。所以我们可以针对不同的 x，选择不同的 s，使近似效果达到最佳。
考虑 $ f(x;s) $ 的Edgeworth 展开
$$ f(x;s) = \phi \left( {x -\mu_s \over \sigma_s} \right) \left\{ 1 + {\kappa_{3}(s) \over 6 } \left[ \left( {x -\mu_s \over \sigma_s} \right)^3 - 3 \left( {x -\mu_s \over \sigma_s} \right) \right] + O \left( {1 \over n} \right) \right\} $$
对于固定的 x，若选择s，使得 $\mu_s =x$，则在x点上的近似具有 $O(1/n)$ 的精度。现在对不同的x，我们始终选择 $\hat s$ 满足
$$ K’(\hat s(x)) = x $$
从而可以使 $O(1/n)$ 的精度是全局的。上面的方程被称作鞍点方程。将 $ f(x;s) $ 的近似带入到 $ f(x) $ 中
$$ f(x) \approx \hat f(x) = {1 \over \sqrt{2 \pi K’’(\hat s (x)) }} \exp \{ K(\hat s(x)) -\hat s(x)x \} $$
上式称为 $ f(x) $ 的（一阶）鞍点近似。要注意的是 $ \hat f(x) $ 并不是真正的密度函数，因为
$$ c := \int_{\Bbb R} \hat f(x) dx \neq 1 $$
正规化的鞍点近似密度函数为
$$ \bar f(x) = c^{-1} \hat f(x), \qquad x \in \mathcal X $$
连续分布的鞍点近似
设 $X_i, i \in \Bbb{N}$ 是独立同分布的连续随机变量，具有累量母函数 $K(s)$。则均值 $ \bar X =1/n \sum_{i=1}^n X_i$ 密度函数的鞍点近似为
$$ \hat f _{\bar X}(x) = \sqrt{ { n \over 2 \pi K’’(\hat s (x)) } } \exp \{ K( \hat s(x)) -\hat s(x)x \} $$
$X$ 分布的函数的鞍点近似为
$$ \hat F_{\bar X}(x) = \begin{cases}
\Phi(\hat w) + \phi(\hat w) \left( {1 \over \hat w} - {1 \over \hat u} \right) & \text{if }x \neq \mu \\
{1 \over 2} + { K’’’(0) \over 6 \sqrt{2} \pi K’’(0)^{3/2} } & \text{if }x = \mu
\end{cases} $$
其中
$$\begin{align}
\hat w &= \text{sgn}(\hat s) \sqrt{ 2 \{ \hat s x -K(\hat s) \} } \\
\hat u &= \hat s \sqrt{ K’’(\hat s) }
\end{align} $$
$\Phi(\cdot),\phi(\cdot) $ 分别为标准正态分布的分布函数和密度函数，$\hat s$ 是鞍点方程 $K’(s) =x $ 的解。
离散分布的鞍点近似
设 $X$ 是整数集 $\Bbb{Z}$ 上的随机变量， $p(k)$ 是其质量函数，则 $p(k) $ 具有鞍点近似
$$ \hat p(k) = {1 \over \sqrt{ 2 \pi K’’(\hat s) }} \exp \{ K(\hat s) - \hat s k \} $$
其中 $\hat s$ 是鞍点方程 $K’(\hat s) = k, \quad k \in \mathcal{I_X} $的解， $\mathcal{I_X} $ 是 supp X 延展的内点集。
定义 $ k^- =k-1/2 \in \mathcal{I_X} $ 是 k的偏置，$\hat s$ 是鞍点方程 $K’(\hat s) = k^-$ 的解，则$X$ 生存函数的（第二连续性矫正）鞍点近似为
$$ \hat{Pr}(X \geq k) = \begin{cases}
1 - \Phi(\hat w) - \phi(w)(1/2 - 1/u) & \text{if } k^- \neq \mu \\
1/2 - { K’’’(0) \over 6 \sqrt{2} K’’(0)^{3/2} } & \text{if } k^- = \mu
\end{cases} $$
其中
$$\begin{align}
\hat w &= \text{sgn}(\hat s) \sqrt{2 \{ \hat s k^- -K(\hat s) \}} \\
\hat u &= 2 \text{sinh}(\hat s/2) \sqrt{K’’(\hat s)}
\end{align}$$
Sum of Binomials
设 $X_i,i=1,2,3$ 是独立随机变量，$X_i \sim \text{Binomial}(m_i,\theta_i) $，其中 $ m_i = 8-2i, \theta_i = 2^i/30 $。现在考虑 $ X = \sum_i X_i $ 的质量函数和分布函数。相信这样的事情能让几乎每一个人抓狂。
$X$ 的CGF为
$$ K(s) = 2 \sum_{i=1}^3 (4-i) \log \left\{ {2^i \over 30} (e^s -1) +1\right \}, \quad s \in \Bbb{R} $$
对应的鞍点方程为
$$ K’(s) = {6\hat t \over \hat t +14} + {8\hat t \over 2\hat t +13} +{8\hat t \over 4\hat t +11} $$
其中 $ \hat t = \exp(\hat s) $。下表展示了上述的鞍点近似质量函数 $\hat p(k)$，和对应的归一化鞍点近似 $ \bar p(k) $
| $k$ | $p(k) $ | $ \hat p(k) $ | $ \bar p(k) $ | $ \text{Poisson}(\mu) $ |
|---|---|---|---|---|
| $1$ | $.3552$ | $.3845$ | $.3643$ | $.3384$ |
| $3$ | $.1241 $ | $.1273$ | $.1206$ | $.1213$ |
| $5$ | $.0^2 7261$ | $.0^2 7392$ | $.0^2 7004$ | $.01305$ |
| $7$ | $.0^3 1032$ | $.0^3 1052$ | $.0^4 9963$ | $.0^3 6682$ |
| $9$ | $.0^6 3633$ | $.0^6 3738$ | $.0^6 3541$ | $.0^4 1996$ |
| $11$ | $.0^9 2279$ | $.0^9 2472$ | $.0^9 2342$ | $.0^6 3904$ |
在k=1,3时，Poisson近似差强人意，更大的k时，Poisson近似就稀烂了。而（对这个问题）鞍点近似在全局都保持着惊人的精度，注意 $ 0 \leq X \leq 12 $。通常情况下，对密度进行归一化能得到更好的近似，但是归一化常数的计算可能并不直接。
另一方面，对于分布函数，下表展示了鞍点近似的生存函数（右尾概率）
| $k$ | $Pr(X \geq k) $ | $ \hat {Pr}(X \geq k) $ | $ \text{Poisson}(\mu) $ |
|---|---|---|---|
| $1 $ | $.7994$ | $.8064$ | $.7693$ |
| $2 $ | $.5558$ | $.5531$ | $.4310$ |
| $3$ | $.1687$ | $.1695$ | $.1828$ |
| $4$ | $.04464$ | $.04483$ | $.06153$ |
| $5$ | $.0^2 8397$ | $.0^2 8428$ | $.01705$ |
| $6$ | $.0^2 1137$ | $.0^2 1140$ | $.0^2 4003$ |
| $7$ | $.0^3 1109$ | $.0^3 1112$ | $.0^3 8141$ |
| $8$ | $.0^5 7732$ | $.0^5 7742$ | $.0^3 1458$ |
| $9$ | $.0^6 3753$ | $.0^6 3751$ | $.0^4 2334$ |
| $10$ | $.0^7 1205$ | $.0^7 1199$ | $.0^5 3372$ |
| $11$ | $.0^9 2299$ | $.0^9 2266 $ | $.0^6 4441$ |
| $12$ | $.0^{11} 1973$ | $.0^{11 }1861$ | $.0^7 5373$ |
Gumbel(0,1) Distribution
设 $ X \sim \text{Gumbel}(0,1) $，具有分布函数 CDF
$$ F(x) = e^{- e^{-x}}, \qquad x \in (-\infty, \infty) $$
和累量母函数 CGF
$$ K(s) = \log \Gamma (1-s), \qquad s \in (-\infty, 1) $$
鞍点方程为
$$ -\digamma(1- \hat s) = x, \qquad s < 1 $$
其中 $ \digamma(\cdot) $ 是digamma函数 (gamma 函数对数的一阶导数，$ \digamma(z) = { \text d \over \text{dz} } \log \Gamma(z) = {\Gamma’(z) \over \Gamma(z)} $)。
于是 $f(x)$ 鞍点近似为
$$ \hat f(x) = {1 \over \sqrt{2 \pi K’’(\hat s (x)) }} \exp \{ K(\hat s(x)) -\hat s(x)x \} $$
正规化的鞍点近似为
$$ \bar f(x) = c^{-1} \hat f(x) $$
其中
$$ c = \int_{\Bbb R} \hat f(x) dx \approx 0.9792 $$
另一方面，$ EX = \gamma := \lim_{n \rightarrow \infty} (-\log n + \sum_{k=1}^n 1/k) \approx 0.5772 $， $\gamma$ 是 Euler–Mascheroni 常数， $ Var X = \pi^2/6$，高阶标准化累量满足
$$ \kappa_n = { K^{(n)}(0) \over \sigma^n } = {1 \over \sigma^n} (n-1)! \zeta(n) $$
其中 $\zeta (s) = \sum_{n=1}^{\infty} n^{-s} $ 是 Riemann zeta 函数。特别地 $\kappa_3 \approx 1.14, \kappa_4 \approx 2.40 $。$X$ 的Edgeworth近似为
$$ f(x) = \phi(z) \left[ 1+ {\kappa_3 \over 6 } H_3(z) +
\left\{ {\kappa_4 \over 24}H_4(z) + {\kappa_3^2 \over 72}H_6(z) \right\} + O(n^{-3/2}) \right] $$
其中 $\phi(\cdot)$ 是标准正态分布的密度函数，$z=(x-\mu)/\sigma $，$H_k(\cdot)$ 是 Hermite 多项式。
下图展示了鞍点近似和 Edgeworth 近似，鞍点近似的效果非常惊人，正规化的鞍点近似更是（视觉上）与真实的密度无法区分。
1 | g = function(s, x) { |