Efficient evaluation of the sample variance of an interval-valued dataset

[摘要] 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".

[发布机构] Department of Econometrics, University of Economics Prague, Winston Churchill Square 4, Prague; 13067, Czech Republic^1

[效力级别] 化学

[关键词] Exponential time;Interval-valued;Interval-valued data;Np-hardness results;Probabilistic modeling;Probabilistic process;Simulation studies;Variation coefficient