Ancestral Sampling

Ancestral sampling generates exact samples from a joint distribution defined by a directed graphical model by sampling variables in topological order.

1. Algorithm

Given a DAG with variables $x_1, \dots, x_D$ in topological order:

For $d = 1, \dots, D$:

$$x_d \sim p(x_d \mid \text{pa}(x_d))$$

where $\text{pa}(x_d)$ denotes the parents of $x_d$ in the DAG, using the values already sampled.

The resulting $(x_1, \dots, x_D)$ is an exact sample from the joint distribution $p(x_1, \dots, x_D)$.

2. Why It Works

By the chain rule implied by the DAG factorization:

$$p(x_1, \dots, x_D) = \prod_{d=1}^D p(x_d \mid \text{pa}(x_d))$$

Sampling each factor in order produces a sample from the joint.

3. Limitations

  • Only produces samples from the joint distribution $p(x_1, \dots, x_D)$
  • Cannot directly produce samples from a conditional distribution $p(x_A \mid x_B = b)$
  • For conditional sampling, need methods like Rejection Sampling, Importance Sampling, or MCMC

4. Application to HMMs

For a Hidden Markov Model (HMM), ancestral sampling generates a sequence by:

  1. Sample $z_1 \sim \pi$
  2. For $t = 2, \dots, T$: sample $z_t \sim p(z_t \mid z_{t-1})$
  3. For $t = 1, \dots, T$: sample $x_t \sim p(x_t \mid z_t)$