Abstract
We revisit the classical problem of approximating a stochastic differential equation by a discrete-time and discrete-space Markov chain. Our construction iterates Caratheodory's theorem over time to match the moments of the increments locally. This allows to construct a Markov chain with a sparse transition matrix where the number of attainable states grows at most polynomially as time increases. Moreover, the MC evolves on a tree whose nodes lie on a "universal lattice" in the sense that an arbitrary number of different SDEs can be approximated on the same tree. The construction is not tailored to specific models, we discuss both the case of uni-variate and multi-variate case SDEs, and provide an implementation and numerical experiments.
Introduction
Stochastic Differential Equations (SDEs) are the mathematical backbone of everything from modeling stock prices to describing particle diffusion. However, SDEs live in continuous space and time. To perform simulations, price complex options, or run formal verification, we need to discretize them into Markov Chains (MCs).
The primary challenge in this discretization is the "curse of dimensionality" and state space explosion. In naive discretizations, the number of possible states can double at every time step ($2^i$), quickly exceeding computational memory. This paper presents a geometric approach to approximate complex SDEs using sparse Markov Chains that recombine on a fixed grid, ensuring that the state space grows only polynomially.
Methodology: Geometry over Algebra
The core innovation of this work is the combination of Local Moment Matching with Convex Geometry to create a structured, manageable grid.
Local Moment Matching and Carathéodory’s Theorem
At each step in time, the algorithm identifies where the SDE "wants" to go by calculating its local moments (mean and covariance). Instead of sampling randomly, the method uses Carathéodory’s theorem—a result from convex geometry—to pick a minimal set of points (at most $d+1$ in $d$ dimensions) on a fixed lattice that perfectly match those moments.
As illustrated in the figure above, the target state (represented by $a$ and its associated variance) is approximated by a combination of neighboring lattice points. By forcing these points to lie on a "universal lattice" (a grid like $\mathbb{Z}^d$), paths that diverge can "recombine" later at the same nodes. This recombination is the "secret sauce" that keeps the state space from exploding; instead of a bushy tree, the process evolves on a structured grid where paths frequently cross.
Algorithm DISCRETIZE
The authors provide a pseudo-code algorithm that builds the transition matrix row-by-row. This ensures the resulting matrix is sparse, meaning most entries are zero, which significantly enhances computational speed and efficiency.
Key Insights and Results
- Universal Lattices: One of the most significant findings is that different SDEs (e.g., representing different assets) can be approximated on the exact same lattice. Only the transition probabilities change, not the nodes themselves, which is a major advantage for multi-asset modeling.
- Guaranteed Non-Negativity: Traditional moment-matching often results in "negative probabilities" between nodes. Because this method relies on convex combinations, probabilities are guaranteed to be between 0 and 1.
- Polynomial Growth: The authors prove that for bounded coefficients, the state space grows at a rate of $O(i^d)$ (where $i$ is time and $d$ is dimension), rather than the exponential $O(2^i)$.
- Numerical Accuracy: In stress tests using the Mean-Reverting Heston Model, relative errors for first and second moments remained low (often < 5%) even with few discretization steps, demonstrating that efficiency does not sacrifice accuracy.
Limitations and Future Work
While the resulting Markov Chain is fast to use, the initial recombination step to find the right points can be computationally expensive. The analytical proof for the existence of these points in higher dimensions ($d \ge 4$) also remains a significant challenge. Future work may involve combining this framework with "cubature" methods or extending it to more complex time-inhomogeneous SDEs and optimal control problems.
Summary updated