Complexity of samping from mixture model...
I have a model where state j among M states is chosen with probability p_j. The probability could be any real number. I can access p_j for all j in constant time.
I want to make a large number (N) of random samples. The most obvious algorithm is 

1) Compute the cumulative probability distribution P_j = p_1+p_2+...p_j. O(M) 
2) For each sample choose random float x in [0,1]. O(N)
3) For each sample choose j such that min(0,P_j-1) < x <= max(1,P_j). O(Nlog(M))

So the asymptotic complexity is O(Nlog(M)). The factor of N is obviously unavoidable, but I am wondering about log(M). Is it possible to beat this factor in a realistic implementation? 



Complexity of samping from mixture model...
===

I have a model where state j among M states is chosen with probability p_j. The probability could be any real number. I can access p_j for all j in constant time.
I want to make a large number (N) of random samples. The most obvious algorithm is 

1) Compute the cumulative probability distribution P_j = p_1+p_2+...p_j. O(M) 
2) For each sample choose random float x in [0,1]. O(N)
3) For each sample choose j such that min(0,P_j-1) < x <= max(1,P_j). O(Nlog(M))

So the asymptotic complexity is O(Nlog(M)). The factor of N is obviously unavoidable, but I am wondering about log(M). Is it possible to beat this factor in a realistic implementation? 


