1

我有一个模型，其中 M 个状态中的状态 j 以概率 p_j 选择。概率可以是任何实数。这指定了 M 个状态的混合模型。我可以在恒定时间内访问所有 j 的 p_j。我想制作大量（N）个随机样本。最明显的算法是

1) 计算累积概率分布 P_j = p_1+p_2+...p_j。（男）

2) 对于每个样本，在 [0,1] 中选择随机浮点 x。上）

3) 对于每个样本，选择 j 使得 min(0,P_j-1) < x <= max(1,P_j)。O(Nlog(M))

所以渐近复杂度为 O(Nlog(M))。N的因素显然是不可避免的，但我想知道log（M）。是否有可能在实际实施中克服这个因素？

4

1 回答 1

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) 的时间，但它确实取决于您的二项式分布和混合模型组件采​​样器的效率。

于 2010-10-25T20:19:00.433 回答