Population Variance under Interval Uncertainty: A New Algorithm

In statistical analysis of measurement results, it is often beneficial to compute the range V of the population variance \(v=\frac{1}{2}\cdot\sum^{n}_{i=1}(x_{i}-E)^{2}\,(where E=\frac{1}{n}\sum^{n}_{i=1}x_{i})\) when we only know the intervals \([{\tilde x}_{i}-\Delta_{i},{\tilde x}_{i}+\Delta_{i}]\) of possible values of the xi. In general, this problem is NP-hard; a polynomialtime algorithm is known for the case when the measurements are sufficiently accurate, i.e., when \(|{\tilde x}_{i}-{\tilde x}_{j}|\geq\frac{\Delta_{i}}{n}+\frac{\Delta_{j}}{n}\) for all \(i\neq j.\) In this paper, we show that we can efficiently compute V under a weaker (and more general) condition \(|{\tilde x}_{i}-{\tilde x}_{j}|\geq\frac{|\Delta_{i}-\Delta_{j}|}{n}\).