Exact bounds on finite populations of interval data (Q2484079)

The aim of this paper is to describe several new methods for computing the variance of finite population in the framework of interval arithmetics, and to provide basic results concerning the computational complexity when computing other finite population parameters over interval data. In descriptive statistics, the (simple, real) points are replaced with interval data (of bounded measurement errors), computing various population parameters (in particular, the finite population variance) requires to calculate the interval \([\min\sigma^2, \max\sigma^2]\) of the possible values of the parameter \(\sigma^2\). The main results exposed and proved within this paper are the following: (1) A feasible algorithm is proposed for computing the exact lower bound \(\min\sigma^2\) of the finite population variance \(\sigma^2\). The algorithm is of quadratic-time complexity, i.e. it requires \(O(n^2)\) computational steps (arithmetic operations or comparisons) for \(n\) interval data points. The algorithm was implemented in C++ and is reported to work really fast. (2) The general problem of computing \(\max\sigma^2\) from the given interval data points is NP-hard, i.e. is computationally intractable. (3) However, for many practical situations one may solve the problem at (2) above in tractable time. Namely, the authors propose an efficient algorithm that computes \(\max\sigma^2\) for the case when all the interval midpoints are definitely different from each other. (4) The paper examines the question of exact computing other finite population parameters, and provides the following findings: the problems of exact computing the finite population covariance and the finite population correlation on interval data points are NP-hard problems, while computing the finite population median is of \(O(n \log n)\) time computational complexity.