On-line algorithms for computing mean and variance of interval data, and their use in intelligent systems

When we have only interval ranges [x̲i,xi¯] of sample values x1, … , xn, what is the interval [V̲,V¯] of possible values for the variance V of these values? There are quadratic time algorithms for computing the exact lower bound V on the variance of interval data, and for computing V¯ under reasonable easily verifiable conditions. The problem is that in real life, we often make additional measurements. In traditional statistics, if we have a new measurement result, we can modify the value of variance in constant time. In contrast, previously known algorithms for processing interval data required that, once a new data point is added, we start from the very beginning. In this paper, we describe new algorithms for statistical processing of interval data, algorithms in which adding a data point requires only O(n) computational steps.