Abstract
This paper develops the first class of algorithms that enable unbiased estimation of steady-state expectations for multidimensional reflected Brownian motion. In order to explain our ideas, we first consider the case of compound Poisson (possibly Markov modulated) input. In this case, we analyze the complexity of our procedure as the dimension of the network increases and show that, under certain assumptions, the algorithm has polynomial-expected termination time. Our methodology includes procedures that are of interest beyond steady-state simulation and reflected processes. For instance, we use wavelets to construct a piecewise linear function that can be guaranteed to be within $\varepsilon$ distance (deterministic) in the uniform norm to Brownian motion in any compact time interval.
Introduction
Reflected Brownian Motion (RBM) serves as a fundamental model for complex stochastic networks operating under heavy traffic conditions, such as data centers, manufacturing systems, and communication networks. Despite its theoretical importance, obtaining accurate steady-state expectations for multidimensional RBMs has historically been a significant challenge. Traditional simulation methods suffer from two primary sources of error: initialization bias, arising from the unknown stationary distribution of the starting state, and discretization bias, caused by the continuous nature of Brownian motion being approximated by discrete time steps.
This work introduces a novel class of algorithms designed to provide unbiased estimation of steady-state expectations. By integrating "Coupling From The Past" (CFTP) with a wavelet-based path representation, the authors overcome the limitations of previous simulation techniques, offering a scalable solution for multidimensional systems.
Methodology
1. The Fluid Case: Compound Poisson Input
The authors first address networks with jump-based (compound Poisson) inputs. To achieve unbiased sampling, they employ Dominated Coupling From The Past (DCFTP). This technique involves constructing a "dominating" process—an upper bound that is simpler to simulate backward in time. When this dominating process hits zero, it implies that all possible trajectories starting from any initial state have converged (coalesced) into a single value by time zero. This value represents a perfect sample from the steady-state distribution, effectively eliminating initialization bias.
2. Multidimensional Reflected Brownian Motion
Simulating RBM is more complex because the process rarely hits an exact zero state in higher dimensions. The authors solve this through a multi-layered approach:
- Wavelet Path Representation: Utilizing the Levy-Ciesielski construction, Brownian paths are represented using wavelets. This allows for the creation of a piecewise linear approximation that is guaranteed to remain within a deterministic distance $\varepsilon$ of the true Brownian path across any compact time interval.
- Tolerance-Enforced Coupling: Instead of requiring exact coalescence at zero, the algorithm monitors when the system enters a defined $\varepsilon$-neighborhood.
- Debiasing via Randomization: To transition from an $\varepsilon$-accurate estimate to a truly unbiased expectation, the authors apply a randomization trick. By sampling at a specific random time, they "correct" the approximation error inherent in the discretization.
Key Insights and Theoretical Results
Polynomial Complexity
A critical contribution of this research is the proof that the algorithm's complexity grows polynomially with the network dimension ($d$). This is a significant departure from many multidimensional simulation problems that suffer from the "curse of dimensionality," suggesting that this methodology is viable for relatively large-scale stochastic networks.
Monotonicity and the Skorokhod Problem
The algorithm relies on the monotonicity of the Skorokhod problem, which governs the reflection of the Brownian path. Because the system preserves order—a trajectory starting from a higher state remains above one starting from a lower state—the use of a dominating process becomes a mathematically sound strategy for ensuring convergence.
Deterministic Error Bounds
The use of wavelets provides a robust framework for error control. Unlike standard discretization methods where error is probabilistic, the wavelet approach guarantees that the simulated path stays within a fixed distance $\varepsilon$ of the true path everywhere in the interval.
Experimental Validation
The authors validated their theoretical framework using two primary benchmarks:
- 10-Station Tandem Network: In a fluid network where jobs pass through ten sequential stations, the simulation yielded a mean for the final station of $3.3200 \pm 0.1040$, closely aligning with the theoretical value of $3.3333$ derived from Laplace transforms.
- 2D Symmetric RBM: For a two-dimensional reflected process with a known analytical mean of $5/12 \approx 0.4167$, the algorithm produced an estimate of $0.4164 \pm 0.0137$ at a precision of $\varepsilon = 0.01$.
Conclusion and Future Work
This paper represents a theoretical breakthrough as the first to provide unbiased estimators for multidimensional RBM steady-state expectations. While the RBM simulation is computationally more intensive than the fluid model due to the time required to find the coalescence point, it establishes a rigorous foundation for future optimizations. Future research may focus on improving the practical efficiency of these algorithms for industrial-scale applications, potentially by balancing bias control with variance reduction to decrease computational overhead.
Summary updated