Efficient steady-state simulation of high-dimensional stochastic networks

DOI10.1287/STSY.2021.0077zbMATH Open1496.60111arXiv2001.08384OpenAlexW3172749241MaRDI QIDQ5084487FDOQ5084487

Xinyun Chen, Nian Si, Peter W. Glynn, Jose Blanchet

Publication date: 24 June 2022

Published in: Stochastic Systems (Search for Journal in Brave)

Abstract: We propose and study an asymptotically optimal Monte Carlo estimator for steady-state expectations of a d-dimensional reflected Brownian motion. Our estimator is asymptotically optimal in the sense that it requires $ildeO(d)$ (up to logarithmic factors in $d$) i.i.d. Gaussian random variables in order to output an estimate with a controlled error. Our construction is based on the analysis of a suitable multi-level Monte Carlo strategy which, we believe, can be applied widely. This is the first algorithm with linear complexity (under suitable regularity conditions) for steady-state estimation of RBM as the dimension increases.

Full work available at URL: https://arxiv.org/abs/2001.08384

Recommendations

• Steady-state simulation of reflected Brownian motion and related stochastic networks
• Steady-state analysis of RBM in a rectangle: Numerical methods and a queueing application
• Reflected Brownian motion in an orthant: Numerical methods for steady- state analysis
• A numerical scheme for invariant distributions of constrained diffusions
• Exact simulation of multidimensional reflected Brownian motion

zbMATH Keywords

multilevel Monte Carloqueueing networksreflected Brownian motionsteady-state simulation

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Stochastic network models in operations research (90B15)

Cites Work

• Title not available (Why is that?)
• Multilevel Monte Carlo Path Simulation
• Reflected Brownian motion on an orthant
• Title not available (Why is that?)
• Brownian models of open queueing networks with homogeneous customer populations^∗
• Title not available (Why is that?)
• Reflected Brownian motion in an orthant: Numerical methods for steady- state analysis
• The finite element method for computing the stationary distribution of an SRBM in a hypercube with applications to finite buffer queueing networks
• Multilevel Monte Carlo Methods
• Unbiased estimation with square root convergence for SDE models
• Multi-level Monte Carlo methods for the approximation of invariant measures of stochastic differential equations
• Directional Derivatives of Oblique Reflection Maps
• Exact estimation for Markov chain equilibrium expectations
• Asymptotic irrelevance of initial conditions for Skorohod reflection mapping on the nonnegative orthant
• Steady-state simulation of reflected Brownian motion and related stochastic networks
• Parameter and dimension dependence of convergence rates to stationarity for reflecting Brownian motions
• Rates of Convergence to Stationarity for Reflected Brownian Motion
• Sensitivity Analysis for the Stationary Distribution of Reflected Brownian Motion in a Convex Polyhedral Cone

Cited In (10)

• Efficient simulation of hierarchical stochastic activity network models
• Utilizing network structure to accelerate Markov chain Monte Carlo algorithms
• S̲tochastic S̲imulation A̲lgorithm For Effective Spreading Dynamics On T̲ime-Evolving A̲daptive N̲etworX̲ (SSATAN-X)
• QRF
• Dimension-free local convergence and perturbations for reflected Brownian motions
• Generalizing Gillespie's direct method to enable network-free simulations
• On the effective dimension and multilevel Monte Carlo
• Steady-state simulation of reflected Brownian motion and related stochastic networks
• Fast simulation of highly reliable networks with varying random external load
• Long-time behavior of finite and infinite dimensional reflected Brownian motions

This page was built for publication: Efficient steady-state simulation of high-dimensional stochastic networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5084487)