Abstract
Many random processes can be simulated as the output of a deterministic model accepting random inputs. Such a model usually describes a complex mathematical or physical stochastic system and the randomness is introduced in the input variables of the model. When the statistics of the output event are known, these input variables have to be chosen in a specific way for the output to have the prescribed statistics. Because the probability distribution of the input random variables is not directly known but dictated implicitly by the statistics of the output random variables, this problem is usually intractable for classical sampling methods. Based on Markov Chain Monte Carlo we propose a novel method to sample random inputs to such models by introducing a modification to the standard Metropolis-Hastings algorithm. As an example we consider a system described by a stochastic differential equation (sde) and demonstrate how sample paths of a random process satisfying this sde can be generated with our technique.
Introduction: The Inverse Problem
In stochastic modeling, a common challenge is the "inverse problem." While the "forward problem" involves finding the output distribution $Y$ given a known input distribution $X$ through a model $h$, the inverse problem asks: how can we sample inputs $X$ such that the resulting outputs $Y = h(X)$ follow a specific target distribution $f_{Yd}$?
This task is complicated by several factors inherent in complex systems:
- Model Complexity: The function $h$ is often a "black box" (e.g., complex simulation code) without an analytical inverse.
- Many-to-One Mappings: Multiple distinct input configurations can yield the same output.
- Volume Distortion: The model may non-linearly stretch or compress regions of the input space, meaning a uniform distribution of inputs does not translate to a uniform distribution of outputs.
Standard Markov Chain Monte Carlo (MCMC) methods fail here because they do not account for these geometric distortions. Sampling the input space based solely on the target output density leads to biased results that reflect the model's internal structure rather than the desired statistics.
Methodology: Modified Metropolis-Hastings
To address these challenges, the authors propose a modified Metropolis-Hastings algorithm. The key innovation is the introduction of a probing term, $f_Q$, which represents the probability density of the output when inputs are sampled uniformly. This term effectively "neutralizes" the model's internal distortions and many-to-one mappings.
The modified acceptance probability $\alpha$ for a transition from state $x$ to $x'$ is defined as: $$\alpha(x, x') = \min \left( 1, \frac{f_{Yd}(h(x'))}{f_{Yd}(h(x))} \cdot \frac{p(x', x)}{p(x, x')} \cdot \frac{f_Q(h(x))}{f_Q(h(x'))} \right)$$ where $p$ is the proposal distribution. If $f_Q$ is not known analytically, it can be estimated using techniques like Kernel Density Estimation (KDE).
Experimental Validation: Stochastic Differential Equations
The method was validated using a synthetic benchmark: Geometric Brownian Motion (GBM). GBM is a stochastic differential equation (SDE) with a known analytical solution, providing a "ground truth" for comparison.
A significant insight for SDE research is that this MCMC approach allows for parallel path sampling. Unlike traditional sequential methods (e.g., Euler-Maruyama) that generate paths step-by-step, this algorithm samples the entire path simultaneously. This makes it particularly well-suited for stochastic boundary value problems where both initial and final conditions are fixed.
Results and Discussion
Testing on a linear SDE ($\mu=1, \sigma=0.5$) yielded the following results:
- Statistical Accuracy: Empirical probability density functions (PDFs) generated via simulation matched the theoretical lognormal distributions at multiple time steps ($t=0.1, 0.5, 1.0$).
- Autocorrelation: The normalized autocorrelation of the generated paths aligned perfectly with theoretical values.
- Convergence: The algorithm demonstrated robust convergence after $5.1 \times 10^6$ samples (including a $10^5$ burn-in period).
Limitations
While powerful, the method has constraints. The mathematical proof assumes a bounded input space $\Omega$, requiring truncation for models with theoretically unbounded inputs. Additionally, MCMC is computationally intensive, and the estimation of the probing term $f_Q$ can become a bottleneck in very high-dimensional spaces. Future research may focus on more efficient density estimation techniques to scale the algorithm further.
Summary updated