Accurate Small Tail Probabilities of Sums of iid Lattice-Valued Random Variables via FFT
提出sisFFT算法，利用快速傅里叶变换高效计算独立同分布格值随机变量之和的极小尾概率，同时控制相对误差，比现有精确方法快得多。
Accurately computing very small tail probabilities of a sum of independent and identically distributed lattice-valued random variables is numerically challenging. The only general purpose algorithms that can guarantee the desired accuracy have a quadratic runtime complexity that is often too slow. While fast Fourier transform (FFT)-based convolutions have an essentially linear runtime complexity, they can introduce overwhelming roundoff errors. We present sisFFT (segmented iterated shifted FFT), which harnesses the speed of FFT while retaining control of the relative error of the computed tail probability. We rigorously prove the method’s accuracy and we empirically demonstrate its significant speed advantage over existing accurate methods. Finally, we show that sisFFT sacrifices very little, if any, speed when FFT-based convolution is sufficiently accurate to begin with. Supplementary material is available online.