📊 statistics

Lattice Random Walk Discretisations of Stochastic Differential Equations

This paper introduces a lattice random walk discretisation scheme for stochastic differential equations that replaces complex floating-point computations with simple binary or ternary increments, offering advantages such as compatibility with stochastic computing, elimination of Gaussian sampling, and robustness to quantisation errors while maintaining weak convergence.

Original authors: Samuel Duffield, Maxwell Aifer, Denis Melanson, Zach Belateche, Patrick J. Coles

Published 2026-02-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Samuel Duffield, Maxwell Aifer, Denis Melanson, Zach Belateche, Patrick J. Coles

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Navigating a Stormy Sea

Imagine you are trying to predict the path of a boat drifting across a stormy ocean. The boat is pushed by two forces:

The Current (Drift): A predictable wind or current pushing it in a specific direction.
The Waves (Diffusion): Random, chaotic splashes of water hitting the boat from all sides.

In the world of math and computer science, this is called a Stochastic Differential Equation (SDE). It's the math behind everything from how molecules move in your body to how AI generates pictures of kittens on skateboards.

To simulate this on a computer, we have to break time down into tiny steps (like frames in a movie). The problem is that computers are terrible at handling the "infinite precision" of real numbers and the "perfect randomness" of Gaussian (bell-curve) noise. They usually approximate, which leads to errors, crashes, or slow performance.

The authors of this paper propose a new way to navigate these stormy seas: The Lattice Random Walk (LRW).

The Old Way: The "Perfect" but Fragile Boat

Method: Euler-Maruyama (The Standard)
Analogy: Imagine a captain who tries to calculate the boat's next move using a super-precise calculator.

They calculate exactly how much the wind pushes.
They generate a "perfect" random wave height from a complex mathematical bell curve.
They add them together to get a new position.

The Problem:

Fragile: If the wind gets too strong (a "non-Lipschitz" drift), the calculation can explode, sending the boat off the map.
Expensive: Generating those "perfect" random waves requires heavy math (Gaussian sampling) that slows down computers.
Fussy: It assumes the computer has infinite precision. In the real world, computers round numbers (quantization), and these tiny rounding errors pile up, making the simulation inaccurate.

The New Way: The "Pixelated" Grid Walk

Method: Lattice Random Walk (LRW)
Analogy: Instead of a boat moving smoothly through water, imagine the ocean is a giant grid of tiles (like a chessboard or a Minecraft world).

At every step, the boat doesn't calculate a complex new coordinate. Instead, it flips a coin (or a three-sided die) to decide:

Move Left (1 bit of randomness)
Move Right (1 bit of randomness)
Stay Put (0)

The "wind" (drift) and "waves" (diffusion) are no longer complex calculations; they are just used to tune the odds of the coin flip.

If the wind is strong to the right, the coin is weighted to land on "Right" more often.
If the waves are huge, the coin is more likely to land on "Move" rather than "Stay."

Why is this cool?

It's Digital Native: Computers love 1s and 0s. This method only needs to flip a coin (binary) or a three-sided die (ternary). No complex math, no heavy floating-point numbers.
It's Bulletproof: Because the boat can only move one tile at a time, it can never "explode" and fly off the map, even if the wind is hurricane-force. The grid acts as a safety net.
It Ignores Rounding Errors: Since the boat must land on a tile, it doesn't matter if the computer's math is slightly off. The result snaps to the nearest valid tile. It's robust against "noise."

The Superpower: Stochastic Computing

The paper highlights a massive bonus. There is a special type of computer hardware called Stochastic Computing that doesn't use standard math. Instead, it processes streams of random bits (like a stream of 1s and 0s) to represent numbers.

The Old Problem: Usually, to get a real number out of a stochastic computer, you have to count a huge stream of bits to find the average. This is slow and cancels out the speed benefits.
The LRW Solution: Because the LRW output is already a simple bit (Left/Right/Stay), you don't need to do any counting! The answer is the bit itself. This unlocks the potential for massive speedups on specialized hardware, potentially making AI image generation or scientific simulations thousands of times faster and more energy-efficient.

Real-World Proof: The "Kitten on a Skateboard"

The authors didn't just do math; they tested it on Stable Diffusion 3.5, a famous AI that generates images.

They replaced the standard "perfect" math with their "grid walk" method.
Result: The AI still generated beautiful images of a kitten on a skateboard holding tea.
Even with fewer steps (coarser grid), the images looked great. This proves the method works even for the most complex, modern AI models.

Summary

The paper introduces a way to simulate complex, random systems by trading "perfect precision" for "digital simplicity."

Instead of trying to calculate the exact, smooth path of a particle (which is hard and error-prone), they force the particle to hop along a grid of integer steps.

Old Way: "Calculate the exact angle and force, then move 0.0000432 units." (Fragile, slow, needs perfect math).
New Way: "Flip a coin. If heads, hop one square right. If tails, hop left." (Robust, fast, works on simple hardware).

This simple shift allows us to run complex simulations on cheaper, faster, and more energy-efficient hardware, potentially revolutionizing how we build AI and simulate the physical world.

1. Problem Statement

Stochastic Differential Equations (SDEs) are fundamental to modeling phenomena in physics, finance, and machine learning (notably diffusion models for image generation). However, simulating SDEs on digital hardware presents significant challenges:

Discretization Errors: Traditional methods like Euler–Maruyama (EM) assume infinite numerical precision. In practice, finite precision (quantization) leads to error accumulation.
Non-Lipschitz Drifts: Many modern applications involve drift functions that grow faster than linearly (non-globally Lipschitz). Standard EM schemes often fail catastrophically (explode) under these conditions.
Hardware Inefficiency: SDE simulation requires Gaussian sampling and floating-point arithmetic, which are computationally expensive and energy-intensive. This makes SDEs poorly suited for emerging stochastic computing architectures, which manipulate probability distributions of bitstreams rather than real numbers.
Sequential Nature: SDE simulation is inherently sequential, limiting the benefits of parallel GPU acceleration.

2. Methodology: Lattice Random Walk (LRW)

The authors propose a novel discretization scheme called Lattice Random Walk (LRW) that fundamentally changes how SDEs are simulated.

Core Concept:
Instead of calculating continuous updates with floating-point numbers, LRW discretizes the SDE by sampling ternary (or binary) increments at each step. The state $x_t$ evolves on an integer lattice.

The Update Rule:
For an SDE $dx = f(x, t)dt + \sigma(x, t)dw$ , the LRW update at time step $\delta t$ is:
$x_{t+\delta t} = x_t + \Delta(x_t, t)$
where the increment $\Delta$ is a random variable taking values in $\{-\delta x, 0, +\delta x\}$ with probabilities $p_-, p_0, p_+$ defined as:
$p_{\pm}(x, t) = \frac{1}{2\delta t \delta x} \left[ \pm f(x, t) + \frac{\sigma(x, t)^2}{\delta x} \right]$
(Note: The paper assumes a diagonal diffusion matrix $\sigma$ .)

Key Design Choices:

Spatial Step Size ( $\delta x$ ): Must satisfy specific constraints to ensure probabilities are valid ( $0 \le p \le 1$ ). A "rule of thumb" is $\delta x = \sqrt{\delta t \sigma_{max}}$ .
Binary vs. Ternary: Under certain conditions (specifically when $\delta x = \sqrt{\delta t \sigma}$ ), the probability of staying at 0 becomes zero, reducing the update to a binary random walk ( $\pm \delta x$ ).
Convergence: The scheme is proven to have weak order 1 convergence, matching the rate of Euler–Maruyama, provided $\delta x = \Theta(\sqrt{\delta t})$ .

3. Key Contributions

A. Theoretical Advancements

Weak Convergence Proof: The authors prove that the LRW scheme converges to the true SDE solution in the weak sense (convergence of expectations) with order 1.
Stability for Non-Lipschitz Drifts: Unlike EM, where the second moment of the update grows with the square of the drift ( $E[(\Delta x)^2] \propto f^2$ ), the LRW second moment is independent of the drift ( $E[(\Delta x)^2] \propto \sigma^2$ ). This bounded step size prevents the "explosive" behavior seen in EM for non-Lipschitz drifts.
Handling Time-Inhomogeneity: The method supports time-varying diffusion coefficients, making it applicable to modern flow-matching and diffusion models.

B. Hardware and Computational Advantages

Elimination of Gaussian Sampling: LRW removes the need for transcendental functions (like Box-Muller) to generate Gaussian noise. It only requires sampling simple binary or ternary variables.
Robustness to Quantization: Because the output is discrete (lattice-based), small errors in the calculation of drift/diffusion probabilities do not accumulate as continuous errors. They are absorbed into the probability distribution of the discrete steps.
Enabling Stochastic Computing: This is the most significant contribution. LRW maps perfectly to stochastic computing architectures.
- Traditional SDE solvers require aggregating bitstreams to get a real number, negating speedups.
- LRW is the bitstream. The output of the simulation is inherently a sequence of binary/ternary bits, eliminating the need for aggregation and allowing for massive energy/latency savings on specialized hardware.

4. Experimental Results

The authors validated LRW across three distinct domains:

Ornstein-Uhlenbeck (OU) Process (Quantization Robustness):
- Setup: Simulated a multivariate OU process using 8, 16, and 32-bit floating-point arithmetic.
- Result: LRW maintained high accuracy even at 16-bit precision, whereas Euler–Maruyama performance degraded significantly. LRW was also less sensitive to the choice of time step $\delta t$ .
Poisson Random Effects Model (Non-Lipschitz Drift):
- Setup: Sampled from a Bayesian model with a non-globally Lipschitz drift function (common in finance and biology).
- Result: Euler–Maruyama diverged (exploded) for larger time steps. LRW remained stable and accurate across all tested step sizes, confirming the theoretical stability advantage.
Stable Diffusion 3.5 (Scalability):
- Setup: Applied LRW to generate images using the state-of-the-art Stable Diffusion 3.5 model (8 billion parameters).
- Result: With 50 steps, LRW generated images visually indistinguishable from Euler–Maruyama. With 25 steps, LRW produced high-quality images with slightly more noise (graininess), demonstrating scalability to massive, complex machine learning pipelines.

5. Significance and Future Impact

Paradigm Shift: LRW moves SDE simulation from a "floating-point arithmetic" problem to a "probabilistic sampling" problem.
Hardware Acceleration: By removing Gaussian sampling and floating-point operations, LRW unlocks the potential for dedicated stochastic computing hardware (ASICs) to simulate SDEs orders of magnitude faster and more efficiently than current GPUs.
Robustness: The method offers a practical solution for running SDEs on low-precision hardware (e.g., edge devices) without catastrophic failure.
Future Work: The authors identify extending the method to dense (non-diagonal) diffusion matrices and developing specialized hardware implementations as the next critical steps.

In summary, this paper introduces a mathematically rigorous, hardware-native discretization scheme that solves the stability and efficiency bottlenecks of current SDE solvers, paving the way for next-generation stochastic computing in AI and scientific simulation.