Numerical Approximation of Probability Mass Functions via the Inverse Discrete Fourier Transform

摘要

First passage distributions of semi-Markov processes are of interest in fields such as reliability, survival analysis, and many others. Finding or computing first passage distributions is, in general, quite challenging. We take the approach of using characteristic functions (or Fourier transforms) and inverting them to numerically calculate the first passage distribution. Numerical inversion of characteristic functions can be unstable for a general probability measure. However, we show they can be quickly and accurately calculated using the inverse discrete Fourier transform for lattice distributions. Using the fast Fourier transform algorithm these computations can be extremely fast. In addition to the speed of this approach, we are able to prove a few useful bounds for the numerical inversion error of the characteristic functions. These error bounds rely on the existence of a first or second moment of the distribution, or on an eventual monotonicity condition. We demonstrate these techniques with two examples.