We then describe how to obtain an ( ε,δ )-approximation of H(p), i.e., an estimate ˜H(p) that satisfies |˜H(p) − H(p)| ≤ εH(p) with probability at least 1 − δ

We first check that the expected value of Xq is indeed the desired quantity E[Xq] = 1 m n∑ i=1 ∑ q:xq=i Xq = 1 m n∑ i=1 ∑ q:xq=i λ m(rq) − λ m(rq − 1) = 1 m n∑ i=1 mi log m mi =H(p)