A Simple and Efficient Algorithm to Compute Tail Probabilities from Transforms,

Abstract

We present an algorithm to compute the tail probability that a random variable exceeds a specified number, given only an expression for its transform. Our method consists essentially of summing a power series, so it is easy to perform and requires little memory. Furthermore, any desired degree of accuracy may be specified in advance of the computation, after which the computational effort is nearly linear in the reciprocal of the prespecified error. We also show that the problem is NP-hard, suggesting that there exists no procedure significantly better than ours. Keywords include: Tail probability, Laplace transform, Computational complexity, Fully polynomial approximation scheme, Convolution. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1985
Accession Number
ADA150928

Entities

People

  • J. C. Ammons
  • J. J. Bartholdi Iii
  • L. K. Platzman

Organizations

  • Georgia Tech

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Bandwidth
  • Complex Numbers
  • Computational Complexity
  • Errors
  • Frequency
  • Numbers
  • Operations Research
  • Probability
  • Probability Distributions
  • Random Variables
  • Standards
  • Systems Engineering
  • Test And Evaluation
  • Theorems
  • Truncation

Fields of Study

  • Mathematics

Readers

  • Aerospace Engineering
  • Approximation Theory.
  • Graph Algorithms and Convex Optimization.