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](http://en.wikipedia.org/wiki/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).



How to estimate the entropy of a distribution on a power set?
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](http://memming.wordpress.com/2014/02/09/a-guide-to-discrete-entropy-estimators/).


