Name
Title | ||
|---|---|---|
Computing Population Variance and Entropy under Interval Uncertainty: Linear-Time Algorithms |
Abstract | ||
|---|---|---|
In statistical analysis of measurement results, it is often necessary to compute the range (V ;V ) of the population variance V = 1 n ¢ n X i=1 (xi ¡ E) 2 ˆ n ¢ n X i=1 xi ! when we only know the intervals (e xi ¡¢i;e xi +¢i) of possible values of the xi. While V can be computed e-ciently, the problem of computing V is, in general, NP-hard. In our previous paper \Population Variance under Interval Uncertainty: A New Algorithm" (Reliable Computing, 2006, Vol. 12, No. 4, pp. 273{280), we showed that in a practically important case, we can use constraints techniques to compute V in time O(n¢log(n)). In this paper, we provide new algorithms that compute V and, for the above case, V in linear time O(n). Similar linear-time algorithms are described for computing the range of the entropy S = ¡ n P i=1 pi ¢ log(pi) when we only know the intervals pi = (pi;pi) of possible values of probabilities pi. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/s11155-007-9045-6 | Reliable Computing |
Keywords | Field | DocType |
symmetric function,entropie,np hard problem,convex function,entropy,variance,linear time,statistical analysis,confidence interval | Discrete mathematics,Symmetric function,Population variance,Algorithm,Convex function,Time complexity,Reliable computing,Mathematics,Statistical analysis | Journal |
Volume | Issue | ISSN |
13 | 6 | 1573-1340 |
Citations | PageRank | References |
7 | 0.63 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gang Xiang | 1 | 77 | 11.18 |
| Martine Ceberio | 2 | 81 | 20.65 |
| Vladik Kreinovich | 3 | 1091 | 281.07 |