Computing Population Variance and Entropy under Interval Uncertainty: Linear-Time Algorithms

In statistical analysis of measurement results, it is often necessary to compute the range [V-,V+] of the population variance V=((x1-E)^2+...+(xn-E)^2)/n (where E=(x1+...+xn)/n) when we only know the intervals [Xi-Di,Xi+Di] of possible values of the xi. While V- can be computed efficiently, the problem of computing V+ is, in general, NP-hard. In our previous paper Population Variance under Interval Uncertainty: A New Algorithm (Reliable Computing, 2006, Vol. 12, No. 4, pp. 273-280), we showed that in a practically important case, we can use constraints techniques to compute V+ in time O(n*log(n)). In this paper, we provide new algorithms that compute V- and, for the above case, V+ in linear time O(n). Similar linear-time algorithms are described for computing the range of the entropy S=-p1*log(p1)-...-pn*log(p_n) when we only know the intervals [pi-,pi+] of possible values of probabilities pi. In general, a statistical characteristic f can be more complex so that even computing f can take much longer than linear time. For such f, the question is how to compute the range [y-,y+] in as few calls to f as possible. We show that for convex symmetric functions f, we can compute y+ in n calls to f