Computing best-possible bounds for the distribution of a sum of several variables is NP-hard

DOI10.1016/J.IJAR.2005.06.009MaRDI QIDQ2489265zbMATH OpenOpenAlexFDO

Authors Scott A. Ferson, Vladik Kreinovich

Publication date 16 May 2006

Published in International Journal of Approximate Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ijar.2005.06.009

zbMATH Keywords

Best-possible boundsNP-hardSum of random variables

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Reasoning under uncertainty in the context of artificial intelligence (68T37)

Recommendations

• Unimodality, independence lead to NP-hardness of interval probability problems
• Best-possible bounds for the distribution of a sum -- a problem of Kolmogorov
• Extremal probability bounds in combinatorial optimization
• On computing the distribution function of the sum of independent random variables
• Polynomially computable bounds for the probability of the union of events

Cites work

• An extreme limit theorem for dependency bounds of normalized sums of random variables
• Best-possible bounds for the distribution of a sum -- a problem of Kolmogorov
• Computational complexity and feasibility of data processing and interval computations
• Equivalence of methods for uncertainty propagation of real-valued random variables
• Estimates for the Distribution Function of a Sum of Two Random Variables When the Marginal Distributions are Fixed
• Estimating and validating the cumulative distribution of a function of random variables: Toward the development of distribution arithmetic
• scientific article; zbMATH DE number 1595639 (Why is no real title available?)
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1183717 (Why is no real title available?)
• scientific article; zbMATH DE number 1484385 (Why is no real title available?)
• scientific article; zbMATH DE number 869746 (Why is no real title available?)
• Interval analysis and fuzzy set theory
• Numerical Software with Result Verification
• Probabilistic arithmetic. I: Numerical methods for calculating convolutions and dependency bounds
• Probabilities, intervals, what next? Optimization problems related to extension of interval computations to situations with partial information about probabilities

Cited in

(11)

• A fully polynomial-time approximation scheme for approximating a sum of random variables
• Robustness to dependency in portfolio optimization using overlapping marginals
• Engineering design under imprecise probabilities: computational complexity
• Extremal probability bounds in combinatorial optimization
• Complementarity and identification
• Imprecise expectations for imprecise linear filtering
• A note on variability of interval data
• Efficient optimal Kolmogorov approximation of random variables
• Verified propagation of imprecise probabilities in non-linear ODEs
• Interval time series analysis with an application to the sterling-dollar exchange rate
• Unimodality, independence lead to NP-hardness of interval probability problems

This page was built for publication: Computing best-possible bounds for the distribution of a sum of several variables is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489265)