原则上可以预先选择要从每个子分布中抽取的样本数量，然后只访问每个子分布一次并抽取多个点。

那是

1. 找到随机集使得并尊重权重。$<n_1, n_2, \dots, n_k>$$n = \sum_{i=1}^k n_i$

   我相信您可以通过绘制泊松分布的多项分布（参见注释），然后将总和归一化为。$w_i * n$$n$

   这里的工作是$\mathcal{O}(k) * \mathcal{O}(n)$

2. 然后做

   for (i=1; i<=k; ++i)
      for (j=1; j<=n[i]; ++j)
         theta ~ N(mu[i],sigma[i])
   

   这里的工作是$\mathcal{O}(n)$

虽然这意味着您不会以随机顺序获得。如果需要随机顺序，您必须然后洗牌（也是大）。$\mathcal{O}(n)$

看起来第一步在运行时占主导地位并且与朴素算法的顺序相同，但是如果您确定所有您可以使用正态分布近似泊松分布并加快第一步。$w_i * n \gg 1$

注意：这个问题的原始版本询问了“正态分布的加权和”，以下答案可能有用。然而，在对这个答案、@Geoff 的答案以及问题本身进行了大量讨论之后，很明显，这个问题实际上是关于对这个答案不适用的“正态分布的混合”进行抽样。

---

正态分布的总和是一个正态分布，所以你可以计算这个单一分布的参数，然后简单地从中抽取样本。如果我们称这个分布为那么，$N(\mu_{sum},\sigma_{sum}^2)$

$$\mu_{sum} = \sum_{i=1}^k w_i\mu_i$$

$$\sigma_{sum}^2=\sum_{i=1}^k w_i^2 \sigma_i^2$$

更新：此答案不正确，源于术语混淆（有关详细信息，请参阅下面的评论链）；我只是把它作为一个路标，这样人们就不会重新发布这个答案（除了巴伦）。请不要投票赞成或反对。

我只是使用随机变量的属性将其减少为单个正态分布的随机变量。两个独立的、正态分布的随机变量之和本身就是一个随机变量，所以如果和，然后$X_{1} \sim N(\mu_{1}, \sigma_{1}^{2})$$X_{2} \sim N(\mu_{2}, \sigma_{2}^{2})$

$$X_{1} + X_{2} \sim N(\mu_{1} + \mu_{2}, \sigma_{1}^{2} + \sigma_{2}^{2}).$$

此外，如果，那么$w_{1} \in \mathbb{R}$

$$w_{1}X_{1} \sim N(w_{1}\mu_{1}, w_{1}^{2}\sigma_{1}^{2}).$$

结合这两个结果，然后

$$Pr(\theta | \rm{data}) \sim N\big(\sum_{i=1}^{k}w_{i}\mu_{i}, \sum_{i=1}^{k}w_{i}^{2}\sigma_{i}^{2}\big).$$

所以在这种情况下，您只需要从单个分布中提取样本，这应该更容易处理。