# How to estimate the entropy of a distribution on a power set?

Given a probability distribution $(X,p)$, its entropy is defined as $H=-\sum_{x\in X} p(x)\log p(x)$.

Given a sample of observations $x_n,n=1..N$, one can estimate $p(x)=\frac{\#\{i:x_i=x\}}{N}$ and thus $H$.

Suppose, however, that $X=P(B)$ the power set of set $B$ and the observations are subsets of $B$: $x_n\subset B$ and the number of observations $\#B=k\ll N\ll 2^k=\#P(B)$. E.g., $k=50$ and $N=10^4$.

I.e., there are not enough observations to estimate the probability of every separate subset.

How would I estimate the entropy of the distribution?

E.g., one can define a probability distribution on $B$ as

\begin{align} m(b)&=\sum_{x\ni b}p(x) \\ M &= \sum_{b\in B} m(b) \\ p_B(b) &= \frac{m(b)}{M}. \end{align}

What can be said about entropy of $(X=P(B),p)$ based on the entropy of $(B,p_B)$? (the latter is easy to estimate based on the sample).

• Is it important to the structure of the distribution that the observations are subsets? If we just think of the observations as integers between $1$ and $2^k$, then this sounds very hard: every distribution that is uniform on $\Omega(N^2)$ supports will look the same (no repeated samples), so distinguishing support size of $N^2$ from $2^k$ sounds impossible to me (but their entropies are very far apart).
– usul
Commented Apr 2, 2014 at 19:51
• @usul: yes, it is the critical point
– sds
Commented Apr 2, 2014 at 20:25
• @sds are you saying that every observed count is 1 Commented Apr 2, 2014 at 20:27
• @guest: I am saying that the structure of X as the power set is important for applications.
– sds
Commented Apr 2, 2014 at 20:29
• @sds, then maybe you can make some assumption about the distribution in terms of the subsets. Otherwise it may not be doable....
– usul
Commented Apr 3, 2014 at 2:17

I don't think the power-set structure helps you estimate entropy better. The following extreme cases all give the same entropy for $p_B$, but entropy of the power set observation ranges from 0 to $N$ (the full range).

• Extreme case 1, if you only observe $B$, your entropy $H(X)$ is zero, while entropy of $p_B$ is maximum, $\log_2(N)$.
• Extreme case 2, if you observe $\{1\}, \ldots, \{N\}$ uniformly, entropy is $H(X)=\log_2(N)$, and entropy of $p_B$ is also $\log_2(N)$.
• Extreme case 3, if you observe all subsets equally likely, entropy $H(X)$ is $N$, while the entropy of $p_B$ is $\log_2(N)$

If entropy of $p_B$ is very small, that might restrict the maximum possible entropy for the power set observation, but I do not see an inequality. Even if there's an inequality, I don't think it can be tight.

As @guest suggested, using generic entropy estimators that perform well in the undersampled regime might be the best bet. @guest suggested my paper (thanks!), here are some more choices.

This paper explains entropy estimation without distribution estimation in the undersampled regime.

• thanks, but the paper does not use the power set structure.
– sds
Commented Apr 2, 2014 at 21:17
• and code for the paper: github.com/pillowlab/PYMentropy Commented Apr 2, 2014 at 23:30

If you'd rather use a frequentist method (instead of the Bayesian approach described above), then a recent paper (that also reviews the literature on this) is this one.