Computing mean and variance under Dempster–Shafer uncertainty: Towards faster algorithms

In many real-life situations, we only have partial information about the actual probability distribution. For example, under Dempster–Shafer uncertainty, we only know the masses m1, … ,mn assigned to different sets S1, … ,Sn, but we do not know the distribution within each set Si. Because of this uncertainty, there are many possible probability distributions consistent with our knowledge; different distributions have, in general, different values of standard statistical characteristics such as mean and variance. It is therefore desirable, given a Dempster–Shafer knowledge base, to compute the ranges and of possible values of mean E and of variance V.In their recent paper, Langewisch and Choobineh show how to compute these ranges in polynomial time. In particular, they reduce the problem of computing to the problem of minimizing a convex quadratic function, a problem which can be solved in time O(n2 · log(n)). We show that the corresponding quadratic optimization problem can be actually solved faster, in time O(n · log(n)); thus, we can compute the bounds V and in time O(n · log(n)).