Efficient evaluation of the sample variance of an interval-valued dataset
Michal Černý · Journal of Physics Conference Series · 2015
Given a set of interval-valued data, a general problem is to compute bounds for a particular statistic, such as sample mean or variance, variation coefficient or entropy. It is well known that computation of the upper bound of sample variance is an NP-hard problem. Here we consider a variant of an algorithm by Fersonet al., which is exponential in the worst case, and investigate its behavior under a natural probabilistic model. A simulation study shows that the undesirable case, which forces the algorithm to work in exponential time (and which appears in the proof of NP-hardness), occurs very rarely in an environment when the interval data are generated by probabilistic processes which are natural from a statistical viewpoint. The main finding is that the thealgorithm is practically very efficient and that the NP-hardness result usually "does not matter too much".