Draft:Duffield Discretization

• Comment: Wikipedia is not a place to advertise your recent math results, particularly when the work has not passed peer review. We only have established material which multiple, independent reputable sources have shown to be notable. If the paper is accepted and in 2 years has multiple citations (> 100) then revise and resubmit. Ldm1954 (talk) 14:58, 21 September 2025 (UTC)

---

The Duffield discretization (also called lattice random walk discretization) is a method for approximately sampling trajectories from stochastic differential equations (SDEs). It is related to not to be confused with distinct from lattice random walk models of physical processes; in contrast the Duffield discretization samples to generic SDEs in the same way as the Euler-Maruyama discretization. The method was introduced by Samuel Duffield (and coauthors) at Normal Computing.

The method differs notably from Euler-Maruyama (and discretizations such as Runge-Kutta methods) through sampling increments in a binary $\{-{\delta }_x,{\delta }_x\}$ or ternary $\{-{\delta }_x,0,{\delta }_x\}$ space for some specified parameter ${\delta }_x$ rather than the full continuum $[-\mathrm{\infty },\mathrm{\infty }]$. Yet has the same weak order 1 convergence as the Euler-Maruyama method.

Definition

Consider a multivariate SDE$$d{X}_t=a(X_t,t)dt+b(X_t,t)d{W}_t,$$with intial condition $X_0=x_0$, Weiner process $W_t$ and we want to solve the SDE on some time interval $[0,T]$. The Duffield discretisation requires the restriction that the diffusion matrix $b(X_t,t)$ is diagonal.

The Duffield discretisation in its more general ternary definition has two hyperparameters. The first is a scalar temporal stepsize ${\delta }_t$ which is shared by all SDE discretizations and recovers the true SDE as ${\delta }_t\to 0$. The second is a spatial vector ${\delta }_x(X,t)$ which controls the size of the ternary steps.

Binary case

The simplest form of the Duffield discretization sets ${\delta }_x(X,t)=\sqrt{{\delta }_t}b(X,t)$. The binary Duffield approximation to the true solution $X$ is the Markov chain $Y$ defined as follows:

• Partition the interval $[0,T]$ into $N$ equal subintervals of width ${\delta }_t=T/N$:

$0={\tau }_0<{\tau }_1<\dots <{\tau }_N=T.$

• Set $Y_0=x_0$.
• Recursively set $Y_n$ for $0\le n\le N-1$ by$$Y_{n+1}=Y_n+\Delta (Y_n,{\tau }_n),$$where for each coordinate $i$ we have an independent binary random variable$$\mathbb{P}[{\Delta }_i(Y,\tau )={\Delta }_i]=\{\begin{array}{cc}1-p_i(Y,\tau ),& \text{if }{\Delta }_i=-\sqrt{{\delta }_t}{b}_i(Y,\tau ),\\ p_i(Y,\tau ),& \text{if }{\Delta }_i=\sqrt{{\delta }_t}{b}_i(Y,\tau ).\end{array}$$Here the probability vector is defined as$$p(Y,\tau )=\frac{1}{2}+\frac{1}{2}\sqrt{{\delta }_t}b(Y,\tau {)}^{-1}a(Y,\tau ).$$

Ternary case

The more general ternary form allows the user to set ${\delta }_x(X,t)$ although weak order 1 convergence requires ${\delta }_x(X,t)=\Theta (\sqrt{{\delta }_t})$, that is ${\delta }_x(X,t)$ as a function of ${\delta }_t$ grows on the same order as $\sqrt{{\delta }_t}$.

The ternary Duffield approximation is the Markov chain defined as above but with more general random increments

• For each coordinate $i$ we have an independent ternary random variable$$\mathbb{P}[{\Delta }_i(Y,\tau )={\Delta }_i]=\{\begin{array}{cc}{p}_{-,i}(Y,\tau ),& \text{if }{\Delta }_i=-{\delta }_{x,i},\\ 1-p_{-,i}(Y,\tau )-p_{+,i}(Y,\tau ),& \text{if }{\Delta }_i=0,\\ p_{+,i}(Y,\tau ),& \text{if }{\Delta }_i={\delta }_{x,i}.\end{array}$$With probability vectors defined as$$p_{\pm }(Y,\tau )=\frac{1}{2}{\delta }_t{\delta }_x^{-1}[\pm a(Y,\tau )+{\delta }_x^{-1}b(Y,\tau {)}^2].$$

The advantage of the ternary generalization is the decoupling of ${\delta }_x(X,t)$ from the SDE's diffusion coefficient $b(X,t)$. For example, in the ternary scheme one can set a constant ${\delta }_x$ and retain a valid discretization even if $b(X,t)$ varies as a function of space $X$ and/or time $t$. However, a general rule of thumb is to set ${\delta }_x(X,t)=\sqrt{{\delta }_t}b(X,t)$ to recover the binary case or close to for performance and robustness.

Advantages

The spatially discrete nature of the Duffield discretization is a marked departure from traditional discretizations such as Euler-Maruyama. This brings several advantages

• No requirement on Gaussian random variate generation. The binary or ternary random sampling is significantly simpler than Gaussian sampling which requires e.g. the Box-Muller transform or the Ziggurat algorithm. Gaussian samples are requried by majority of SDE discretisations (including Euler-Maruyama and Runge-Kutta).
• Inherent error mitigation due to the clamping of the drift and diffusion coefficients to only a discrete increment, in contrast to traditional methods that assume infinite precision. Errors in the computation drift and diffusion arise from e.g. numerical quantization.
• Robustness in the prescence of non-globally-Lipshitz drift coefficients, where methods such as Euler-Maruyama are known to peform poorly..
• Compatability with stochastic computing models of computation. For example, in the binary case the generation of the increment can be considered a vector of bipolar stochastic numbers. Stochastic computing can be used to generate such random variables with specified expectations using stochastic rather than floating point arithmetic which can be significantly more efficient. The Duffield discretisation offers the advantage over traditional stochastic computing of only requiring a single random output rather than long bitstreams that need to be accumulated, this can viewed as an example of dynamic stochastic computing

A significant disadvantage is the restriction of the diffusion matrix to be diagonal.