On Multivariate Discrete Moment Problems and Their Applications to Bounding Expectations and Probabilities

• Published in: Mathematics of operations research 2004-05, Vol.29 (2), p.229-258
• Main Authors: Madi-Nagy, Gergely, Prekopa, Andras
• Format: Article
• Language: English
• Subjects: Binomials; Discrete functions; Discrete mathematics; discrete moment problem; expectation bounds; Lagrange multiplier; Linear programming; Management science; Mathematical functions; Mathematical moments; Mathematical sets; Mathematical theorems; Mathematics; Multivariate analysis; multivariate Lagrange interpolation; Objective functions; Polynomials; probability bounds; Studies
• ISSN: 0364-765X; 1526-5471
• DOI: 10.1287/moor.1030.0064

The discrete moment problem (DMP) has been formulated as a methodology to find the minimum and/or maximum of a linear functional acting on an unknown probability distribution, the support of which is a known discrete (usually finite) set, where some of the moments are known. The moments may be binomial, power, or of more general type. The multivariate discrete moment problem (MDMP) has been initiated by the second-named author, who developed a linear programming theory and methodology for the solution of the DMPs and MDMPs under some assumptions that concern the divided differences of the coefficients of the objective function. The central results in this respect are those that concern the structure of the dual feasible bases. In this paper, further results are presented in connection with MDMPs for the case of power and binomial moments. The main theorem (Theorem 3.1) and its applications help us to find dual feasible bases under the assumption that the objective coefficient function has nonnegative divided differences of a given total order, and further divided differences are nonnegative in each variable. Any dual feasible basis provides us with a bound for the discrete function that consists of the coefficients of the objective function and also for the linear functional. The latter bound is sharp if the basis is primal feasible as well. The combination of a dual feasible basis structure theorem and the dual method of linear programming is a powerful tool to find the sharp bound for the true value of the functional, i.e., the optimum value of the objective function. The lower and upper bounds are frequently close to each other even if the number of utilized moments is relatively small. Numerical examples are presented for bounding the expectations of functions of random vectors as well as probabilities of Boolean functions of event sequences.