×

Population variance under interval uncertainty: a new algorithm. (English) Zbl 1098.65006

Summary: In statistical analysis of measurement results, it is often beneficial to compute the range \(\mathbf V\) of the population variance \(V = \frac{1}{n} \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 \(\left[\tilde{x_i}-\Delta_i, \tilde{x_i}+\Delta_i\right]\) of possible values of the \(x_i\). In general, this problem is NP-hard; a polynomial time 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 \(\mathbf V\) under a weaker (and more general) condition \(|\tilde{x_i}-\tilde{x_j}| \geq \frac{|\Delta_i-\Delta_j|}{n}\).

MSC:

65C60 Computational problems in statistics (MSC2010)
62J10 Analysis of variance and covariance (ANOVA)
65G30 Interval and finite arithmetic
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Gormen, Th. H., Leiserson, C. E., Rivest, R. L., and Stein, C.: Introduction to Algorithms, MIT Press, Cambridge, 2001.
[2] Person, S., Ginzburg, L., Kreinovich, V., Longpre, L., and Aviles, M.: Computing Variance for Interval Data Is NP-Hard, ACM SIGACTNews 33 (2) (2002), pp. 108–118.
[3] Person, S., Ginzburg, L., Kreinovich, V, Longpre, L., and Aviles, M.: Exact Bounds on Finite Populations of Interval Data, Reliable Computing 11 (3) (2005), pp. 207–233. · Zbl 1076.65013
[4] Granvilliers, L., Kreinovich, V, and Miiller, N.: Novel Approaches to Numerical Software with Result Verification, in: Alt, R., Frommer, A., Kearfott, R. B., and Luther, W. (eds), Numerical Software with Result Verification, Proceedings of the International Dagstuhl Seminar, Dagstuhl Castle, Germany, January 19–24, 2003, Springer Lectures Notes in Computer Science 2991, 2004. pp. 274–305.
[5] Jaulin, L., Kieffer, M., Didrit, O., and Walter, E.: Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics, Springer Verlag, London, 2001. · Zbl 1023.65037
[6] Kreinovich, V, Xiang, G., Starks, S. A., Longpre, L., Ceberio, M., Araiza, R., Beck, J., Kandathi, R., Nayak, A., Torres, R., and Hajagos, J.: Towards Combining Probabilistic and Interval Uncertainty in Engineering Calculations: Algorithms for Computing Statistics under Interval Uncertainty, and Their Computational Complexity, Reliable Computing (submitted). · Zbl 1104.65010
[7] Rabinovich, S.: Measurement Errors: Theory and Practice, American Institute of Physics, New York, 1993.
[8] Xiang, G.: Fast Algorithm for Computing the Upper Endpoint of Sample Variance for Interval Data: Case of Sufficiently Accurate Measurements, Reliable Computing 12 (1) (2006), pp. 59–64. · Zbl 1088.65008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.