Auxiliary Variable Sampler

Definition

The auxiliary variable sampler (Damien-Wakefield-Walker, DWW, 1999) is a Gibbs sampling technique for drawing from a target density $f(x) \propto \pi(x)\prod_{i=1}^N \ell_i(x)$ that cannot be sampled directly. For each factor $\ell_i$ , a uniform latent variable $U_i \sim \text{Uniform}(0, \ell_i(x))$ is introduced. The resulting Gibbs scheme cycles: (a) $U_i \mid x \sim \text{Uniform}(0, \ell_i(x))$ — trivial draw; (b) $x \mid u \sim \pi(\cdot)$ restricted to the truncation set $A_u = \{x: \ell_i(x) > u_i,\; \forall i\}$ — a draw from the prior truncated to a computable interval. The marginal distribution for $x$ is exactly $f$ .

Key Ideas

Theorem 1 (general form): If each $\ell_i$ is invertible, the set $A_u$ is analytically computable as an intersection of intervals. All full conditionals except the last are uniform; the final conditional is a truncated version of $\pi$ .
Always-moves property: The auxiliary Gibbs dominates an independence Metropolis-Hastings (M-H) chain that uses $\pi$ as the proposal. The M-H chain accepts with probability $\min(1, \ell(\tilde{x})/\ell(x))$ and sometimes stays; the auxiliary Gibbs, by sampling $u$ before $x$ , always samples from within the acceptance region — equivalent to always accepting. This holds exactly for the independence chain and yields improved mixing in practice.
Non-uniqueness of decomposition: The factorization $f(x) \propto \ell(x)\pi(x)$ is not unique. Choosing different $\ell$ and $\pi$ changes the shape and size of $A_u$ . Strategic decomposition — e.g., absorbing some terms into $\pi$ or splitting $\ell = \ell_1 \cdot \ell_2$ — makes truncation sets tractable at the cost of extra auxiliary variables.
Multivariate extension: When $x$ is multivariate and $A_u$ is intractable jointly, the sampler iterates through components $x_k \mid x_{-k}, u$ — each a truncated draw from $\pi(x_k \mid x_{-k})$ . This requires only that $\ell_i(x_k, x_{-k})$ be invertible in $x_k$ for fixed $x_{-k}$ .

How It Works

Non-Conjugate Models

For $f(x) \propto \ell(x)\pi(x)$ , introduce $U \sim \text{Uniform}(0, \ell(x))$ . The joint density $p(x, u) \propto \pi(x) \mathbf{1}[u < \ell(x)]$ has marginal $f(x)$ .

Examples:

Model	$\ell(x)$	$\pi(x)$	Full conditional for $x \mid u$
Poisson–log-normal	$\exp(rx - e^x)$	$\mathcal{N}(0,1)$	Truncated normal
Bernoulli–logistic	$\prod_i h_i(x)^{w_i} b_i(x)^{1-w_i}$	$\mathcal{N}(0,1)$	Truncated normal on interval $A_u$
Weibull hazards	$\prod_i \exp(-u_i t_i^a e^{z_i\beta})$	$\mathcal{N}(\mu, \Sigma)$	Truncated normal

Generalized Linear Mixed Models (GLMM)

For the random-effects Poisson model $y_i \mid \theta_i \sim \text{Poisson}(e^{\theta_i})$ , $\theta_i = w_i\beta + b_i$ :

Introduce $U_i \sim \text{Uniform}(0, \exp(-y_i \theta_i))$ and $V_i \sim \text{Exp}(1)$ restricted to $(e^{\theta_i}, \infty)$ .
Full conditional for each $\beta_k \mid \beta_{-k}, b, \Lambda, u, v$ is a truncated normal.
Full conditional for $b_i \mid \beta, \Lambda, u, v$ is a truncated normal.
Full conditional for precision $\Lambda$ is unchanged (Wishart or inverse-gamma).

Non-Linear Mixed Effects

For individual random effects $\theta_i$ with non-log-concave conditional $f(\theta_i) \propto \prod_j \exp(-\frac{1}{2\sigma^2}[y_{ij} - g(\theta_i)]^2) \cdot \pi(\theta_i)$ :

Introduce gamma latent effects $u_{ij} \sim \text{Gamma}(3/2, 1/2)$ restricted to $(g(\theta_i)^2, \infty)$ . Each component $\theta_{ik} \mid \theta_{i,-k}, u$ becomes a draw from $\pi(\theta_{ik} \mid \theta_{i,-k})$ truncated to an analytically computable interval — no ratio-of-uniforms tuning required.

Numerical example (Lindstrom-Bates 1990 orange trees, $n=7$ , $T=5$ obs each):

Algorithm	Lag-1 autocorrelation (ACF)	ACF at lag 40
Auxiliary Gibbs	0.75	~0 (by lag 9)
Random-walk M-H	0.79	0.39

Why It Matters

No tuning: Unlike random-walk M-H, the auxiliary variable sampler requires no proposal covariance or acceptance-rate calibration. Once the decomposition $\ell_i$ is chosen, the sampler is automatic.
Non-log-concave posteriors: Adaptive rejection sampling (Gilks-Wild 1992) requires log-concavity; the auxiliary Gibbs does not. This makes it applicable to non-linear mixed models with arbitrary mean functions $g(\theta_i)$ .
Precursor to slice sampling: Neal (2003) formalized the "slice sampler" as a uniform-auxiliary Gibbs scheme; DWW (1999) contains the same core idea applied to structured Bayesian models.
Complements data augmentation: Data augmentation (Tanner-Wong 1987) introduces latent variables to make $p(\theta \mid z, y)$ conjugate. The auxiliary variable sampler introduces uniform $U$ to make the full conditional a truncated standard distribution — both are latent-variable Gibbs tricks, but the auxiliary approach is more explicit about the truncation geometry.

Open Questions

The efficiency advantage over M-H holds exactly for the independence chain with $\pi$ as proposal; for well-tuned random-walk M-H, the comparison is problem-specific.
Optimal decomposition choice (which terms to absorb into $\pi$ vs. $\ell$ ) remains heuristic; no general theory for minimizing autocorrelation.
High-dimensional $x$ with dependent components requires coordinate-wise sampling, losing the joint-update efficiency of blocking strategies.