Error in mutual information when using a subset I want to compute the mutual information for ~4000 different pairs, where each pair contains two vectors. Each of these vectors hold 100000 observations, making this computation very computationally intensive when using Minepy. Therefore, it would be nice to just use a sample of these observations to compute the mutual information. How much would it affect the value of mutual information if I only took a random sample of 1000 observations for each of the vectors and used that instead?
 A: Let's look at the formula:

I(X,Y) measures the shared information between X and Y.
p(x,y) is the joint probability density function.
The marginal p(x) describes the relative likelihood for the random variable X to take on a particular value x (also, a probability density function). 

The question is actually whether the random sample is representative of the population marginal distribution.

Each time you take a random sample for one vector you have a different p(x) for vector x. If your sample is large enough and you're lucky, then this should be a good approximation and you're done. 
Now, let's say you want to be more confident about this approximation.
You repeat several times and you get multiple estimations of this distribution. Average these and you have a good approximation of the population distribution, which usually turns out to be a gaussian.
This is called the Central limit theorem which states that if a sufficiently large number of samples is taken from a population (given some conditions), then the distribution will be normal.

TL/DR: You need to randomly sample without replacement multiple times. In your case, this means you randomly select rows from your dataset, let's say S=1000 rows / observations as in your example and repeat this N=10 times. Average the results and you should get an accurate approximation. Adjust S and N according to your computational constraints.

"Dice sum central limit theorem" by Cmglee
shows how the approximation gets better as n increases.

A: You can cope with the running time not by reducing your dataset size but by changing the way you do the computation.
Now you have ~4,000 pairs and you go over 100K samples for each pair , costing ~4*10^9 operations.
Instead, you can do the following:
I assume that you are checking all pairs of variables so the number of variables you have is 
n*(n-1)/2 = ~ 4,000
n ~ 100
Aggregate the samples based on all the features.
Using SQL you can do it by
select f1,f2,....fn, count(*)
from samples
group by f1,f2,....fn
That will cost you a single scan of the 100K samples.
The computation of the 4,000 pairs will cost you the size of the 4,000*|aggregated dataset|
If you have 100 (binary) variables, the size of the aggregated dataset might reach 2^100 ~10^30 >> 10^5 = 100K samples.
However, a combination not supported by any samples wont be in the aggregated dataset so the size of the aggregated dataset is at most as the size of the original one.
It is very likely that the size of the aggregated dataset will be way smaller than the original one.
If it not so it might be due to few variable causing such a spread. These are usually few variables of high entropy. You can remove the from the current list of variables and do the computation on the aggregated dataset for the rest. Then you can compute the mutual information of the high entropy variable in the direct method
You can also approximate the mutual information by removing all combination of low support (in SQL, write something like having count(*) > 10).
I would have try to avoid reducing the sample size.
You want to estimate the mutual information of 4,000 pairs with 100K samples.
More than that, computing MI involves division and log which are sensitive to estimation errors. Hence, you are likely to get some bad estimations even when using all your data.
Assuming that you are mostly interested in pair of high MI, keep a validation set to to verify these pair. It seems the moving samples from the original set to the validation is a zero sum game. However, since you would like to verify much fewer pair you will get a better estimation of the pair the you are interested in.
Another way to validated you results is by using transitivity. In case the you have a high mutual information between A and B and also both A and be have high mutual information with other variables, this is a good indicator of a true connection.
