Digital Commons Network^™

Estimating Information Amount Under Interval Uncertainty: Algorithmic Solvability And Computational Complexity, Gang Xiang, Olga Kosheleva, George J. Klir

Departmental Technical Reports (CS)

In most real-life situations, we have uncertainty: we do not know the exact state of the world, there are several (n) different states which are consistent with our knowledge. In such situations, it is desirable to gauge how much information we need to gain to determine the actual state of the world. A natural measure of this amount of information is the average number of "yes"-"no" questions that we need to ask to find the exact state. When we know the probabilities p1,...,pn of different states, then, as Shannon has shown, this number of questions can be determined as S=-p1 …

Computing Variance Under Interval Uncertainty: A New Algorithm And Its Potential Application To Privacy In Statistical Databases, Richard Aló, Mohsen Beheshti, Gang Xiang

Departmental Technical Reports (CS)

Computation of population mean E=(x1+...+xn)/n and population variance V=(x1^2+...+xn^2)/n -E^2 is an important first step in statistical analysis. In many practical situations, we do not know the exact values of the sample quantities xi, we only know the intervals [Xi-Di, Xi+Di] that contain the actual (unknown) values of xi. Different values of xi from these intervals lead, in general, to different value of population variance. It is therefore desirable to compute the range [V]=[V-,V+] of possible values of V.

This problem of computing population variance under interval uncertainty is, in general, NP-hard. It is known that in some reasonable cases, …