Computing best-possible bounds for the distribution of a sum of several variables is NP-hard |
| |
Institution: | 1. Department of Computer Science, University of Texas at El Paso, El Paso, TX 79968, USA;2. Applied Biomathematics, 100 North Country Road, Setauket, NY 11733, USA |
| |
Abstract: | In many real-life situations, we know the probability distribution of two random variables x1 and x2, but we have no information about the correlation between x1 and x2; what are the possible probability distributions for the sum x1 + x2? This question was originally raised by A.N. Kolmogorov. Algorithms exist that provide best-possible bounds for the distribution of x1 + x2; these algorithms have been implemented as a part of the efficient software for handling probabilistic uncertainty. A natural question is: what if we have several (n > 2) variables with known distribution, we have no information about their correlation, and we are interested in possible probability distribution for the sum y = x1 + ? + xn? Known formulas for the case n = 2 can be (and have been) extended to this case. However, as we prove in this paper, not only are these formulas not best-possible anymore, but in general, computing the best-possible bounds for arbitrary n is an NP-hard (computationally intractable) problem. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|