
12 Knowledge Discovery from Data Streams
interval estimators that compute an interval for the true value of the param-
eter, associated with a confidence 1 − δ. Two types of intervals are:
• Absolute approximation: X − ≤ µ ≤ X + , where is the absolute
error;
• Relative approximation: (1−δ)X ≤ µ ≤ (1+δ)X, where δ is the relative
error.
An interesting result from statistics is the Chebyshev Inequality.
Theorem 2.2.1 (Chebyshev) Let X be a random variable with standard
deviation σ, the probability that the outcome of X is no less than kσ away
from its mean is no more than 1/k
2
:
P (|X − µ| ≤ kσ) ≤
1
k
2
No more than 1/4 of the values are more than 2 standard ...