FAST ALGORITHMS FOR COMPUTING POPULATION VARIANCE, ENTROPY, AND CONVEX SYMMETRIC FUNCTIONS IN GENERAL UNDER INTERVAL UNCERTAINTY

Gang Xiang
Dept. of Computer Science, UTEP
Philips Healthcare Informatics
gxiang@acm.org

In statistical analysis of measurement results it is often necessary to compute the range [underline_V, overline_V] of the population variance V of measurement results x_1,..., x_n, when we only know the intervals [underline_x_i, overline_x_i] of possible values of the x_i. In this presentation, we provide the latest algorithms that compute underline_V (in all cases) and overliner_V (for a practically important case) in linear time O(n).

Similar linear-time algorithms are described for computing the range of the entropy S = - sum( p_i * log p_i) when we only know the intervals [underline_p_i, overline_p_i] of possible values of probabilities p_i.

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 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.