Standard Markov Chain Monte Carlo (MCMC) algorithms operate under a strict assumption: the parameter space has a fixed, unyielding dimensionality. We define a vector of parameters $\theta \in \mathbb{R}^d$, and the algorithm explores this $d$-dimensional landscape to map out the posterior distribution.
However, many of the most compelling problems in modern Bayesian inference break this assumption. Consider trying to determine the number of principal components in a dataset (Zhang 0004 et al.), tracking an unknown number of people moving through a surveillance camera's field of view (Smith et al.; Yao), or inferring the number of structural blocks that compose a 3D object (Schlecht et al.). In these scenarios, the number of parameters is itself a random variable. The sampler must navigate a state space that is a disjoint union of subspaces of different dimensions—a challenge known as transdimensional inference.
The Core Challenge: The Geometry of Changing Dimensions
Why can't a standard Metropolis-Hastings sampler simply propose adding or removing a parameter? The issue is fundamentally measure-theoretic.
Imagine trying to transition from a two-dimensional model space $\mathcal{X} \subset \mathbb{R}^2$ to a three-dimensional model space $\mathcal{Y} \subset \mathbb{R}^3$. In the eyes of the three-dimensional space, the two-dimensional subspace has a volume (Lebesgue measure) of exactly zero. If a sampler attempts to jump from $\mathcal{X}$ to $\mathcal{Y}$ by simply proposing a value for the new third parameter, the probability of randomly landing exactly on the valid posterior support within that higher-dimensional space is zero. Conversely, jumping downward means collapsing a continuous parameter to a point mass, which disrupts the balance of the acceptance ratio.
Without a mathematical mechanism to reconcile this dimensional mismatch, the chain cannot maintain detailed balance—the core requirement that ensures the sampler converges to the true posterior distribution. As noted by Bardenet, evaluating discrete events or components within noisy signals requires algorithms capable of fluidly jumping between parameter spaces of different sizes without destroying this mathematical validity.
The Mechanism: Dimension Matching and the Jacobian
The breakthrough concept that solves this problem is Reversible Jump MCMC (RJMCMC). The core intuition behind RJMCMC is dimension matching: if the two spaces do not have the same dimension, we artificially create auxiliary randomness to equalize them.
Suppose we want to move from a lower-dimensional state $\theta \in \mathbb{R}^m$ to a higher-dimensional state $\theta' \in \mathbb{R}^n$ (where $m < n$). To bridge the gap of $n - m$ dimensions, we sample a vector of auxiliary random variables $u$ from a known proposal distribution $q(u)$ such that:
$$\dim(\theta) + \dim(u) = \dim(\theta')$$
Now, both sides of the transition have exactly the same number of dimensions. We can then define a bijective, differentiable function $g$—a diffeomorphism—that maps the augmented lower-dimensional space directly to the higher-dimensional space:
$$\theta' = g(\theta, u)$$
Because $g$ is a bijection, the reverse move is perfectly deterministic: if we are at $\theta'$ and want to jump down, we apply the inverse function $g^{-1}(\theta')$ to recover both the lower-dimensional parameter $\theta$ and the auxiliary noise $u$.
To maintain detailed balance during this jump, the acceptance probability must account for how the volume of the space stretches or shrinks under the mapping $g$. This is achieved by multiplying the standard Metropolis-Hastings ratio by the determinant of the Jacobian matrix of the transformation:
$$\alpha = \min\left(1, \frac{p(\theta')}{p(\theta)q(u)} \left| \det \frac{\partial g(\theta, u)}{\partial (\theta, u)} \right| \right)$$
The Jacobian determinant acts as a geometric correction factor. It ensures that even though the sampler is leaping between entirely different model architectures, the total probability mass is conserved.
Overcoming the Acceptance Rate Bottleneck
While RJMCMC provides a mathematically sound framework, implementing it successfully in practice is notoriously difficult. Historically, designing the mapping $g$ and the auxiliary distribution $q(u)$ was an artisanal process. If the proposed jump lands in a region where the higher-dimensional model has low posterior probability, the jump will be rejected. As Pandolfi et al. point out, these low acceptance rates often cause transdimensional samplers to stall, failing to explore the model space fluidly.
To mitigate this, researchers have developed strategies to make smarter, more informed jumps:
- Multiple-Try Proposals: Instead of proposing a single transdimensional jump, the framework can be extended to evaluate multiple candidate jumps simultaneously. As demonstrated by Pandolfi et al., selecting the most promising candidate from a pool of proposals significantly boosts acceptance rates and mixing efficiency.
- Transport-Driven Jumps: Rather than guessing an auxiliary distribution $q(u)$ blindly, modern approaches use machine learning to learn the geometry of the target spaces. Davies et al. introduced Transport Reversible Jump (TRJ), which leverages normalizing flows. By mapping complex, high-dimensional target distributions back to a simple, shared Gaussian reference space, TRJ automates the construction of highly efficient transdimensional moves.
[Low-Dim Space (θ)] + [Auxiliary Noise (u)]
│
▼ (Dimension Matched)
┌───────────────┐
│ Normalizing │ ◄── Learned by Transport Maps
│ Flow │ (Davies et al.)
└───────────────┘
│
▼
[High-Dim Space (θ')] ──► Evaluated via Jacobian Adjustment
Gradient-Based Transdimensional Sampling
Standard RJMCMC typically relies on random-walk proposals, which scale poorly to high-dimensional continuous parameters. In fixed-dimensional settings, Hamiltonian Monte Carlo (HMC) solves this by using the gradient of the target distribution to simulate physical dynamics, allowing the sampler to take long, sweeping paths through the parameter space.
However, gradients cannot naturally flow across disjoint spaces of different dimensions. How can we leverage the power of HMC when the number of variables is unknown?
Mak et al. resolved this tension by introducing Nonparametric HMC (NP-HMC). Instead of forcing the sampler to make sudden, discrete jumps between models, NP-HMC utilizes a mechanism called lazy dimensionality extension.
During the simulation of the Hamiltonian trajectory, the sampler operates in a unified space but only activates parameters as they are needed by the underlying probabilistic program. If a trajectory encounters a stochastic branch or a recursive loop that requires additional random variables, the sampler dynamically instantiates new position and momentum components on the fly. By drawing these new components from an auxiliary distribution mid-trajectory, the particle continues its smooth, gradient-driven motion uninterrupted across what would otherwise be a sharp dimensional boundary.
Automation via Probabilistic Programming
For decades, the adoption of transdimensional MCMC was bottlenecked by the manual labor required to derive the Jacobian determinants for every new model structure. A minor algebraic error in the Jacobian would silently invalidate the entire simulation.
Modern inference engines have abstracted this complexity away through Universal Probabilistic Programming Languages (PPLs). By representing models as execution traces of stochastic programs, the derivation of transdimensional moves can be entirely automated.
For instance, Roberts et al. demonstrated that embedding automated jump logic within a PPL allows the compiler to automatically track structural changes and compute the necessary Jacobian adjustments by hand. Further formalizing this, Mak et al. introduced Nonparametric Involutive MCMC (NP-iMCMC). This framework proves that standard, fixed-dimensional MCMC algorithms can be systematically transformed into nonparametric versions by dynamically padding execution traces with auxiliary randomness until the program terminates.
By shifting the burden of dimension matching from the researcher to the compiler, transdimensional MCMC has evolved from a mathematically delicate statistical trick into a robust, automated engine for open-ended model selection and structural inference.