Computing Variance under Interval Uncertainty: A New Algorithm and its Potential Application to Privacy in Statistical Databases
Richard Aló, Mohsen Beheshti, Gang Xiang · scholarworks - UTEP (The University of Texas at El Paso) · 2006
Computation of population mean E=(x1+...+xn)/n and population variance V=(x1^2+...+xn^2)/n -E^2 is an important first step in statistical analysis. In many practical situations, we do not know the exact values of the sample quantities xi, we only know the intervals [Xi-Di, Xi+Di] that contain the actual (unknown) values of xi. Different values of xi from these intervals lead, in general, to different value of population variance. It is therefore desirable to compute the range [V]=[V-,V+] of possible values of V. This problem of computing population variance under interval uncertainty is, in general, NP-hard. It is known that in some reasonable cases, there exist feasible algorithms for computing the interval [V]: e.g., such algorithms are known for the case when for some constant c, any collection of more than c "narrowed" intervals [Xi - Di/n, Xi + Di/n] has no common intersection, and for the case when none of the two narrowed intervals are subsets of each other. In this paper, we provide a new polynomial time algorithm for computing population variance under interval uncertainty, an algorithm that is applicable to all situations where previously, feasible algorithms were known.