1. Composition Method
Assume we have a joint probability density function \(\overline{\pi}\) with marginal distribution \(\pi\), i.e., \[\pi(x)=\int \overline{\pi}_{X, Y}(x, y)\text{d}y\] where \(\overline{\pi}(x, y)\) can be decomposed as \[\overline{\pi}_{X, Y}(x, y)=\overline{\pi}_Y(y)\overline{\pi}_{X \mid Y}(x \mid y).\]
It might be easy to sample from \(\overline{\pi}(x, y)\) whereas it is difficult to compute \(\pi(x)\). In this case, it is sufficient to sample \(Y \sim \overline{\pi}_Y\) and \(X \mid Y \sim \overline{\pi}_{X \mid Y}(\cdot \mid Y)\). Then \((X, Y) \sim \overline{\pi}_{X, Y}\) and hence \(X \sim \pi\).
2. Example
Example 2.1 (Finite Mixture of Distributions) Assume we want to sample from \[\pi(x)=\sum_{i=1}^P \alpha_i\pi_i(x)\] where \(\alpha_i>0\), \(\displaystyle \sum_{i=1}^P \alpha_i=1\), \(\pi_i(x) \geq 0\) and \(\displaystyle \int \pi_i(X)\text{d}x=1\). We can introduce \(Y \in \{1, \ldots, P\}\) and \[\overline{\pi}_{X, Y}(x, y)=\alpha_y \pi_y(x).\] We first sample \(Y\) from a discrete distribution s.t. \(\mathbb{P}(Y=y)=\alpha_y\), then sample from \(\pi_Y\): \[X \mid (Y=y) \sim \pi_y.\] Then \(X \sim \pi\).
3. Comment
The composition method requires a representation of \(\pi\) in terms of more simple distributions that can be readily sampled.