Computing population variance and entropy under interval uncertainty: Linear-time algorithms
Assume the measurements \(x_1,\dots,x_n\). Unlike as in classical statistics, where the values \(x_i\) are known, the authors assume that they only know the intervals \(\big[\underline x_i, \overline x_i\big]\) of possible values of~\(x_i\). Usually the intervals are of the form \(\big[\widetilde x_i-\Delta_i, \widetilde x_i+\Delta_i\big]\), where \(\widetilde x_i\) is the measurement result and \(\Delta_i\) is the known upper bound on the absolute value \(| \widetilde x_i| \) of the (unknown) measurement error \(\Delta_i=\widetilde x_i-x_i\); \(| \Delta x_i| \leq\Delta_i\). The authors are interested in computing the range \([\underline V,\overline V]\) of the population variance \(V={1\over n} \sum_{i=1}^{n}(x_i-E)^2\), where \(E={1\over n}\sum_{i=1}^n x_i\). While~\(\underline V\) can be computed efficiently, computing~\(\overline V\) is, in general, an NP hard problem. The main result is an algorithm enabling to compute~\(\underline V\) in linear time \(O(n)\) and~\(\overline V\) in \(O(n\log n)\) time in the general case. Moreover, one special situation is discussed when~\(\overline V\) can be also computed in linear time \(O(n)\), too. More precisely, this situation covers the case when no interval is a proper subinterval of another one. Finally, a linear time algorithm is also described for computing the range of the entropy \(S=-\sum_{i=1}^{n} p_i\log\,p_i\).
- Population variance under interval uncertainty: a new algorithm
- Computing mean and variance under Dempster-Shafer uncertainty: towards faster algorithms
- scientific article; zbMATH DE number 5295839
- MAXIMUM ENTROPY ALGORITHMS FOR UNCERTAINTY MEASURES
- Estimating the entropy of an exponential population under the linex loss function
- Statistical Data Processing under Interval Uncertainty: Algorithms and Computational Complexity
- An asymptotic lower bound for the entropy of discrete populations with application to the estimation of entropy for approximately uniform populations
- Entropy estimators with almost sure convergence and an \(\mathcal O(n^{-1})\) variance
- scientific article; zbMATH DE number 7204268
- Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes
- Exact bounds on finite populations of interval data
- scientific article; zbMATH DE number 1595639 (Why is no real title available?)
- scientific article; zbMATH DE number 429516 (Why is no real title available?)
- scientific article; zbMATH DE number 3425889 (Why is no real title available?)
- scientific article; zbMATH DE number 3464251 (Why is no real title available?)
- scientific article; zbMATH DE number 705150 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Hyperbolic 0-1 programming and query optimization in information retrieval
- Introduction to algorithms
- Maximum entropy and interval computations (September notes on summer impressions)
- Outlier detection under interval uncertainty: algorithmic solvability and computational complexity
- Population variance under interval uncertainty: a new algorithm
- Towards combining probabilistic and interval uncertainty in engineering calculations: algorithms for computing statistics under interval uncertainty, and their computational complexity
- Uncertainty and information: foundations of generalized information theory.
- Probabilities, intervals, what next? Optimization problems related to extension of interval computations to situations with partial information about probabilities
- On-line algorithms for computing mean and variance of interval data, and their use in intelligent systems
- Exact bounds on finite populations of interval data
- Fast algorithm for computing the upper endpoint of sample variance for interval data: Case of sufficiently accurate measurements
- Population variance under interval uncertainty: a new algorithm
- Computing mean and variance under Dempster-Shafer uncertainty: towards faster algorithms
- One-way ANOVA based on interval information
- Towards a combination of interval and ellipsoid uncertainty
- scientific article; zbMATH DE number 2129892 (Why is no real title available?)
- scientific article; zbMATH DE number 5295839 (Why is no real title available?)
- Estimating information amount under uncertainty: algorithmic solvability and computational complexity
- Computing the variance of interval and fuzzy data
- Estimating Variance Under Interval and Fuzzy Uncertainty: Case of Hierarchical Estimation
- From Interval Computations to Constraint-Related Set Computations: Towards Faster Estimation of Statistics and ODEs Under Interval, p-Box, and Fuzzy Uncertainty
- Estimating sample mean under interval uncertainty and constraint on sample variance
This page was built for publication: Computing population variance and entropy under interval uncertainty: Linear-time algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2481140)
