# Random sampling for estimating mutual information - Time complexity and sampling error?

I have a dataset and I want to compute the mutual information (MI) for a selected set of variables. The dataset is large enough so that computation of the MI may take undesirably long time. Can I just take a 10% sample of the data and use it to compute the MI measure?

I am aware of different sampling techniques including random sampling, stratified sampling and bootstrapping. Even though techniques that require computing MI more than once such as bootstrapping or clustering provide good clues about bias and variance, they lead to some extra computational time. I want to compute MI only once. So, preparing a single random sample and using it for estimating MI is a solution. My concern is how accurate is this solution based on a sample size of 10% of data? What about the sampling error and do I have to pay attention to it?

Note: Regarding computing the MI, I do not assume normality for estimating any probability; rather, a non-parametric method (i.e. histogram) is used.

• I would like to share one more idea which came up after posting the question. Since we are using frequency distribution to generate a histogram for probability estimation in the MI, then, as the sample size increases, we will get a better approximation of the probability. Given this assumption, then, a sample size of 10% can be an acceptable sample size. I am still not so certain about this claim and looking for your comments and answers. Dec 28 '12 at 19:48
• Are your variables continuous or discrete valued? MI is notoriously difficult to estimate, even more so in the continuous case. What kind of precision do you require? Apr 22 '13 at 1:48
• also bootstrap doesn't correctly correct bias for MI. Aug 21 '13 at 21:43
• @Memming; I am considering computing MI for continuous variables as for the discrete case, it is much easier. I mentioned in the question, as well, that non-parametric methods such as histogram could be used for discretizing the variable. Aug 25 '13 at 21:16
• unfortunately, histogram based estimation using the plug-in formula is still biased. I guess if you have a lot of data, it shouldn't be too bad. I recommend Paninski 2003. Aug 26 '13 at 14:35