Is it absurd to estimate entropy from a sample?

Question

To tell the exact entropy of a source, all I need to do is to use Shannon's formula $\sum -p(i) \lg p(i)$, where $i$ is the $i$-th element of the alphabet emitted by the source. Therefore, the only thing that keeps me from telling the exact entropy is not knowing $p$. So, the problem of estimating entropy reduces to the problem of estimating $p$.

I have studied Reid's answer to this question. Reid seems to say that you get the sample 1011 you could have 0 to 4 bits of entropy. Why would it be absurd to estimate the probability distribution from this sample? It turns out we get three ones and one zero. Is it absurd to guess that $p(1) = 3/4$ and $p(0) = 1/4$, therefore an estimate for the entropy of the source is $0.8111 = 1/4 \times (-\lg(1/4)) + (3/4 \times (-\lg(3/4)))$, and the amount of information in the sample is $3.244$ bits.

Answer 1

Theoretically, you can break down the question of estimating the entropy of a given collection of (assumed to be independent and identically distributed) samples into two steps:

1. Estimating the distribution of the underlying random variable

2. Computing that random variable's entropy

Generally you can do the first by "counting". If you see the collection of 4 samples $0, 0, 0, 1$, you can set $\Pr[X = 0] = 3/4$, and $\Pr[X = 1] = 1/4$ (this is generally known as the "empirical distribution"). You can then easily compute the entropy.

Note that the rest of the question has a large caveat, in that you need a source of independent and identically distributed samples to apply it. If you see $1011$, is this a single sample, or four independent, identically distributed samples? To answer this you need to think carefully about how the samples are generated, but regardless I'll continue with discussing things assuming you can generate i.i.d. samples.

How accurate the entropy computation is therefore reduces to how close the empirical distribution is to the "true" underlying distribution. For "large enough" sample sizes, it will converge to the true distribution, but quantifying the rate of convergence becomes important. There are various ways to do this, a few are summarized in the empirical distribution function wikipedia page. One particularly useful way to quantify this is via the DKW inequality.

Let $\mathcal{X}$ be the underlying (unknown) distribution, and let $X_1,\dots, X_n$ be $n$ i.i.d. samples from $\mathcal{X}$. Let $F(x)$ be the cumulative distribution function of $\mathcal{X}$. We define the empirical cumulative distribution function of the samples $X_1,\dots, X_n$ via: $$F_n(x) = \frac{1}{n}\sum_{i = 1}^n \mathbf{1}_{X_i \leq x}$$ Here $\mathbf{1}_{X_i \leq x}$ is an "indicator function", which is 1 if $X_i \leq x$, and 0 otherwise. So $F_n(x)$ counts how many of the $X_i$ are less than $x$ (and then normalizes it to be in $[0,1]$ by dividing by $n$).

The DKW inequality then states that for any $\epsilon > \sqrt{\frac{\ln(2)}{2n}}$: $$\Pr[|\sup_{x\in \mathbb{R}} (F(x) - F_n(x))| > \epsilon] \leq 2\exp(-2n\epsilon^2)$$ This gives a "Chernoff-like" bound on how far the cumulative distribution function can be from the empirical cumulative distribution function.

After estimating the empirical cumulative distribution function, you can convert this into estimates for the various probabilities. This is because $p_i = \Pr[X = i] = \Pr[X \leq i] - \Pr[X \leq i-1] = F(i) - F(i-1)\approx F_n(i) - F_n(i-1) \pm 2\epsilon = \tilde{p}_i \pm 2\epsilon$. More formally, by applying the DKW inequality we will get that $|p_i - \tilde{p}_i| \leq 2\epsilon$ with probability all but $2\exp(2n\epsilon^2)$.

We can then compute the entropy of this: \begin{align*} \mathbb{H}[\tilde{X}] &= \sum_{i\in\mathsf{supp}(\tilde{X})} \tilde{p}_i(-\log_2(\tilde{p_i}))\\ &= \sum_{i\in\mathsf{supp}(\tilde{X})} (p_i\pm 2\epsilon)(-\log_2(p_i\pm 2\epsilon)) \end{align*} From here you could try to bound how close this is to the true entropy. Unfortunately the only ways I currently see to do it are rather handwavy --- $-\log_2(x)$ is convex so $-\log_2(2(x+y)/2) \leq -1 -\log_2(x)/2 - \log_2(y)/2$, but $\pm\epsilon$ may be negative, so you start running into issues along those lines.

Anyway, you can proceed as you mention, but to get an accurate estimation of the entropy:

1. You need to be able to "break" your random source into independent and identically distributed samples
2. You need a large sample size (so the probability an estimate falls outside of the DKW inequality, $2\exp(-2n\epsilon^2)$, is "small").

Answer 2

This answer is complementary to the others.

In the paper "The Complexity of Approximating the Entropy", available here Tugkan Batu et al have given a complexity theoretic approach to this problem. The focus on distributions supported on $[n]=\{1,2,\ldots,n\}.$ Interestingly, one of their results is that a multiplicative estimate for entropy, which will work for any distribution for $n$ does not exist.

In particular, they are interested in estimating entropy with high efficiency, in sublinear time (in support size $n$). They look at both the black-box model [considered in the answer by @Mark] and another model where they can actually query "give me $p_i$" f for some $i\in [n],$ and build up the estimate that way.

They define a multiplicative factor estimate with multiplicative factor $\gamma>1,$ as an algorithm whose output $\hat{H}$ satisfies $$ \frac{H}{\gamma} \leq \hat{H} \leq \gamma H. $$

Then, given any $\gamma>1,$ and $0<\epsilon_0<1/2,$ they prove that they can approximate the entropy of a distribution on $[n]$ to within a multiplicative factor $(1+2\epsilon_0)\gamma,$ with probability at least $3/4,$ in $$O((n^{1/\gamma^2}/\epsilon_0^2)\cdot \mathrm{poly}(\log n))$$ time, as long as the entropy of the distribution is at least $\frac{3\gamma}{2\epsilon_0(1-2\epsilon_0)}.$

As for the non-existence result, for any $\gamma>1,$ there is no algorithm which approximates the entropy of every distribution multiplicatively to within $\gamma.$ The neat proof first assumes that the algorithm has runtime $\leq c n^{\alpha},$ for some $\alpha>0,$ and some $c\in (0,1),$ It then points out that such an algorithm would need to distinguish two distributions $$ \mathbb{p}=(1-n^{-\alpha},n^{-\alpha-1},\ldots,n^{-\alpha-1}) $$ and $$ \mathbb{q}=(1,0,\ldots,0) $$ by outputting $\hat{H}\geq \frac{1}{\gamma}n^{-\alpha} \log n>0,$ for $\mathbb{p}$ and $\hat{H}=0$ for $q$ (since $\gamma 0=0/\gamma=0.$) But any algorithm using only $c n^{\alpha}$ samples cannot reliably distinguish between $\mathbb{p},$ and $\mathbb{q}$ as $n$ increases.

Answer 3

Then entropy if a function, which takes as input a random variable. If this random variable is a string of four bits. Then the four bits doesn't give any information about the entropy. Because it's possible that $\mathbb{P}(X=1011)=1$ or $\mathbb{P}(X=1011)=\frac{1}{2^4}$. If you consider your string as $4$ samples of the same variable: It's alittle bit different: You know that your entropy is not $zero$: $\mathbb{P}(X=0)\neq 0$ and $\mathbb{P}(X=1)\neq 0$. But you don't have more information. Because maybe: $\mathbb{P}(X=0)\neq 0.999999$ and $\mathbb{P}(X=1)= 0.000001$ or $\mathbb{P}(X=0)=\mathbb{P}(X=1)=\frac{1}{2}$.

Or to be more general, with $1>\epsilon > 0$: $\mathbb{P}(X=0)=\epsilon$ and $\mathbb{P}(X=1)= 1 -\epsilon$ is possible.

Then entropy $H$ verifies: $0<H\leq1$.

It doesn't help you...

If you want to describe this variable as a Bernoulli variable entropy is not the good tool. It's better to use Estimator (in statistics). But in theory you can't use this estimation as a cryptographic purpose.