Probabilities, intervals, what next? Optimization problems related to extension of interval computations to situations with partial information about probabilities (Q1768614)

Given interval ranges \({\mathbf x}_i= [\underline x_i,\overline x_i]\) of sample values \(x_1,\dots, x_n\), the author considers the interval \({\mathbf V}= [\underline V, \overline V]\) of possible values for the variance \(V\) of \(x_1,\dots, x_n\). He states that computing \(\overline V\) is NP-hard and he mentions an algorithm which results in \(\overline V\) in \(O(2^n)\) computational steps. In contrast to this he presents a quadratic time algorithm for computing \(\underline V\). For a large class of ranges \({\mathbf x}_i\) he shows that NP-hardness for \(\overline V\) can be weakened to quadratic time. To this end he describes an algorithm which only requires \(O(n^2)\) computational steps for \(\overline V\). Another quadratic time algorithm is implicitly given for \(\overline V\) if interval uncertainty is introduced to maintain privacy in a statistical database. Similar ideas can be developed when computing the exact range of covariance between two interval-valued data sequences. For `op' denoting addition, subtraction or multiplication the main formulas of the interval operation \({\mathbf x}_1\) op \({\mathbf x}_2\) are extended to the case where together with \(x_i\in{\mathbf x}_i\) also its mean \(E_i\) or an enclosing interval \({\mathbf E}_i\) is known. Here, bounds for the mean of \(y= x_1\) op \(x_2\) are of interest. The corresponding optimization problems are formulated and solved. An analogous result for general continuous functions \(f\) is cited and some open problems are described.