Number of samples needed for same accuracy mutual information estimate

Question

I'm trying to compare my work to another work that uses an discrete estimation of Mutual Information. I'll try to keep the example as short as possible.

Let there be a population (n=1000) of solutions, each solution has 3 locations and each location can contain one of 4 symbols. Then the estimated mutual information among the symbols has a certain 'accuracy' as to how close it is to the true mutual information (I don't know what the right term is here). If there were more samples the estimate would improve.

Now I wonder if I don't use 4 symbols but 20 (or any other number) symbols by how much should I increase the population to get a similar accuracy as with just 4 symbols? The symbols come from a random uniform distribution. I'm fairly certain a larger population is needed as the odds of a certain combination of symbols diminishes with the number of possible symbols.

Answer 1

This is my understanding of the problem: There are three locations (X, Y, Z) and 4 symbols. X $\in$ {A,B,C,D} and Y $\in$ {A,B,C,D}. I am dropping one of the locations for simplicity and to talk about pairwise MI. And we have $N_{T}$=1000 samples for estimating mutual (shared) information i.e. H(X)+H(Y)-H(X, Y).

X	Y	P(X,Y)
A	D	$N_{AD}/N_T$
B	C	$N_{BC}/N_T$
C	B	$N_{CB}/N_T$
D	A	$N_{DA}/N_T$
.	.	..
.	.	..

You are trying to have a maximum likelihood estimate of $\mathbf{I}$ i.e. $\hat{I}=\hat{H}(X)+\hat{H}(Y)-\hat{H}(X,Y)$. Your specific question: The support of the distribution for which you are estimating mutual information is at max $k=4^2=16$ i.e. all possible permutations. Simple empirical estimation of entropy can be as hard as estimating the distribution. So increasing the number of symbols will increase the number of samples needed with support ($k=20^2=400$), naively you will need 400/16 more samples since the scaling of sample complexity with k is O(k). See paper by [Paninski].
I would like to add that a loose bound on the variance in your MLE estimate will be $\frac{log(N^2)}{N}$ if we didn't know much about the distributions. [Paninski]
[Paninski]: https://www.stat.berkeley.edu/~binyu/summer08/L2P2.pdf