Сложность выборки из смеси модели

Question

У меня есть модель, в которой состояние j среди M состояний выбрано с вероятностью p_j. Вероятностью может быть любое действительное число. Это задает модель смеси по M состояниям. Я могу получить доступ к p_j для всех j в постоянное время. Я хочу сделать большое количество (N) случайных выборок. Наиболее очевидным алгоритмом является

1) Вычислить распределение кумулятивной вероятности P_j = p_1 + p_2 + ... p_j. O (M)

2) Для каждого образца выбирайте случайное поплавок x в [0,1]. O (N)

3) Для каждого образца выберите j так, чтобы min (0, P_j-1) < x < = max (1, P_j). O (Nlog (M))

Таким образом, асимптотическая сложность O (Nlog (M)). Коэффициент N, очевидно, неизбежен, но мне интересно о log (M). Можно ли превзойти этот фактор в реалистичной реализации?

Answer 1

Я думаю, что вы можете сделать лучше использовать что-то вроде следующего алгоритма, или любого другого разумного полиномиального пробоотборника распределения,

// Normalize p_j 
for j = 1 to M 
    p_hat[j] = p[j]/P_j 

// Place the draws from the mixture model in this array 
draws = []; 

// Sample until we have N iid samples 
cdf = 1.0; 
for (j = 1, remaining = N; j <= M && remaining > 0; j++) 
{ 
    // p_hat[j] is the probability of sampling item j and there 
    // are (N - count) items remaining to sample. This is just 
    // (N - count) Bernoulli trials, so draw from a 
    // Binomial(N - count, p_hat[j]/cdf) distribution to get the 
    // number of items  
    // 
    // Adjusting the probability by 1 - CDF ensures that *something* 
    // is sampled because p_hat[M]/cdf = p_hat[M]/p_hat[M] = 1.0 
    items = Binomial.sample(remaining, p_hat[j]/cdf); 
    remaining -= items; 
    cdf -= p_hat[j]; 

    for (k = 0; k < items; k++) 
     draws.push(sample_from_mixture_component(j))   
} 

Это следует принимать близко к O (N) времени, но это зависит от того, насколько эффективно вашего Пробоотборники компонентов биномиального распределения и смеси.