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).
 A: 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.
A: This paper explains entropy estimation without distribution estimation in the undersampled regime.
A: 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.
