Introduction
Reflected Brownian Motion (RBM) is a fundamental stochastic process used extensively in operations research to model systems constrained by boundaries, such as queueing networks and storage systems. While standard Brownian motion is straightforward to simulate, RBM introduces significant complexity because the process is "pushed" back whenever it reaches the boundary of its domain—typically the non-negative orthant $\mathbb{R}^d_+$.
Historically, simulating RBM has relied on numerical approximations like the Euler-Maruyama method. However, these methods suffer from discretization bias: because reflections occur continuously, a discrete-time simulator might miss boundary contacts between steps, leading to systematic errors. This paper presents the first algorithm for the exact simulation of multidimensional RBM at a fixed time $T$, eliminating discretization bias entirely.
The Simulation Challenge
The difficulty in simulating RBM stems from two primary factors:
- Discretization Bias: In discrete time, the path's interaction with the boundary is only checked at specific intervals. If the process "touches" the boundary and returns within a single time step, the simulator fails to account for that reflection.
- Dimensionality and Correlation: In one dimension, RBM can be simulated using the running maximum of a standard Brownian motion. In higher dimensions, however, reflections are governed by a "reflection matrix" $R$, creating correlations that make standard exact simulation techniques (like those based on Girsanov’s theorem) inapplicable.
Methodology: A Novel Two-Stage Framework
The authors propose a framework that combines path approximation with a sophisticated acceptance-rejection logic.
1. $\epsilon$-Strong Simulation
The first stage employs Tolerance-Enforced Simulation (TES). Instead of sampling discrete points, the algorithm generates a piecewise linear approximation of the driving Brownian motion. This approximation is guaranteed to stay within a deterministic distance $\epsilon$ of the true path in the uniform norm. By tracking the maximum and minimum of the path over dyadic intervals, the algorithm maintains a "tube" of uncertainty around the true trajectory.
2. Refine until Accept/Reject
The core innovation is the "Refine until Accept/Reject" strategy. Traditional acceptance-rejection sampling requires calculating an exact likelihood ratio. The authors demonstrate that for exact simulation, one only needs a binary decision: whether to accept or reject a proposed sample.
The algorithm proceeds as follows:
- Propose a sample $Z$.
- Calculate upper and lower bounds for the likelihood ratio based on the current $\epsilon$-approximation.
- If the acceptance threshold $V$ is clearly below the lower bound, the sample is accepted.
- If $V$ is clearly above the upper bound, the sample is rejected.
- If $V$ falls within the "uncertainty zone" created by $\epsilon$, the algorithm refines the simulation (reducing $\epsilon$) and repeats the check.
Key Insights
The success of this approach relies on two critical mathematical properties:
- Lipschitz Continuity of the Skorokhod Map: The mapping from a "free" Brownian motion to a reflected one (the Skorokhod map) is Lipschitz continuous. This allows the algorithm to bound the error of the reflected process based on the known error $\epsilon$ of the driving process.
- Local Linearity: The algorithm identifies "safe zones"—small intervals around the target time $T$ where the process has not hit the boundary. In these zones, RBM behaves like standard Brownian motion, making conditional density calculations tractable.
Results and Theoretical Impact
The paper's primary contribution is Theorem 1, which formally proves that it is possible to simulate the state of a $d$-dimensional RBM at a deterministic time $T$ without any bias. The authors provide a concrete algorithmic framework (Algorithm 3) that bridges the gap between abstract probability theory and computational implementation.
Limitations and Future Outlook
While the paper is a landmark in proving the possibility of exact RBM simulation, the current algorithm faces a significant practical hurdle: computational complexity. The authors identify that the expected running time is currently infinite. This occurs because the cost of refining the $\epsilon$-strong simulation grows quadratically ($1/\epsilon^2$), while the probability of the acceptance variable $V$ falling near the decision boundary does not decrease fast enough.
Consequently, the algorithm remains of "theoretical interest" for now. Future research into more efficient refinement strategies or specialized handling of the process near reflecting boundaries may eventually make this method practical for large-scale engineering applications.
Summary updated