Estimating mean under interval uncertainty and variance constraint

In many practical situations, we have a sample of objects of a given type. When we measure the values of a certain quantity for these objects, we get a sequence of values x₁, ..., x_n. When the sample is large enough, then the arithmetic mean E of the values x_i is a good approximation for the average value of this quantity for all the objects from this class. The values x_i come from measurements, and measurements are never absolutely accurate. Often, the only information that we have about the measurement error is the upper bound Δ_i on this error. In this case, once we have the measurement result x_i, the condition that |x_i - x_i| ≤ Δ_i implies that the actual (unknown) value x_i belongs to the interval [x_i - Δ_i, x_i + Δ_i]. In addition, we often know the upper bound V₀ on the variance V of the actual values - e.g., we know that the objects belong to the same species, and we know that within-species differences cannot be too high. In such cases, to estimate the average over the class, we need to find the range of possible values of the mean under the constraints that each x_i belongs to the given interval [x_i x_i] and that the variance V(x₁, ..., x_n) is bounded by a given value V₀. In this paper, we provide efficient algorithms for computing this range.