We address the problem of evaluating the expected optimal objective value of a discrete optimization problem under uncertainty in the objective coefficients. The probabilistic model we consider prescribes limited marginal distributional information for the objective coefficients in the form of moments. We show that for a fairly general class of marginal information, a tight upper (lower) bound on the expected optimal objective value of a discrete maximization (minimization) problem can be computed in polynomial time if the corresponding deterministic discrete optimization problem is solvable in polynomial time. We provide an efficiently solvable semidefinite programming formulation to compute this tight bound. We use the insights from this analysis to: a) understand the percistency of a decision variable, i.e., the probability that it is part of an optimal solution; for instance, in project scheduling, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path; b) to analyze the asymptotic behavior of a general class of combinatorial problems that includes the linear assignment, spanning tree and traveling salesman problems, under knowledge of complete marginal distributions, with and without independence. We calculate the limiting constants exactly. (joint work with Karthik Natarajan and Chung Piaw Teo)