Comparing large categorical data sets with low or zero counts I'm dealing with a biological feature which can be classified into $2^{20}$  categories. I also have two pretty large data sets of 1 and 3 million entries. Actually, only around 30 thousand categories were observed in the latter, and even less in the former. Thus, a lot of categories have zero counts, and a few have rather small ones.
I would like to tell whether the samples come from a different populations, i.e. compare the aforesaid feature distributions. The only test I can think of is Pearson's $\chi^2$, which is (to my knowledge) not applicable in the case of low counts.
Any advice (including literature on the subject) would be appreciated.
 A: I don't completely understand the problem but let me know if this is on the right track and I can get you some more feedback. Think of $2^{20}$ as the number of words in a dictionary. I give you two books, one which has 1 million words containing 30000 unique ones from the dictionary  and the other containing 3 million words and (say) 35000 unique ones from the dictionary. I give you a new set of words (is this what you mean by 'sample'?') and I want to know which book it came from?
If this is case..look up Naive Bayes classifier. It is the simplest one out there. It assumes conditional independence (given the book, words are independent). There are  It does exactly this. There are a lot of software which will fit these models for you. They all have the problem of zero or very small counts. They use a fix around this problem. A point to note that in these models, there is a fail safe..as in what if I observe a word I have not seen so far (i.e. a new one from the $2^{20}$). They call the probability of observing this probability of 'rest'. This means all the ones you do not observe in the training sample will fall into rest.
The accuracy usually falls in the 60% range as far as prediction goes. It is not fantastic but its a start. There are more complex models (look up Lexicalized PCFGs if you think it suits you better though these are very context specific). I strongly suggest you use pre-written software in case you want to use these models and curb the commonly observed urge to code up these dynamic programming problems.
