Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary

DOI10.1017/JPR.2019.9MaRDI QIDQ4968514zbMATH OpenOpenAlexFDO

Authors Jing Dong, Zhipeng Liu, Jose Blanchet

Publication date 15 July 2019

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

random walkMonte Carloqueueing theoryexact simulation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Queueing theory (aspects of probability theory) (60K25) Sums of independent random variables; random walks (60G50)

Abstract: We present the first algorithm that samples $ma{x}_{ngeq0}{S}_n-n^{alpha},$ where $S_n$ is a mean zero random walk, and $n^{alpha}$ with $alphain(1/2,1)$ defines a nonliner boundary. We show that our algorithm has finite expected running time. We also apply the algorithm to construct the first exact simulation method for the steady-state departure process of a $GI/GI/infty$ queue where the service time distribution has infinite mean.

Recommendations

• Simulating the maximum of a random walk
• Perfect sampling for infinite server and loss systems
• Efficient Simulation of Random Walks Exceeding a Nonlinear Boundary
• Perfect sampling of GI/GI/\(c\) queues
• Maximum on a random time interval of a random walk with infinite mean

Cites work

• scientific article; zbMATH DE number 1188967 (Why is no real title available?)
• Applied Probability and Queues
• Big queues.
• Exact Sampling of Stationary and Time-Reversed Queues
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Perfect sampling for infinite server and loss systems
• Perfect sampling of GI/GI/\(c\) queues
• Simulating the maximum of a random walk
• Steady-state simulation of reflected Brownian motion and related stochastic networks

Cited in

(2)

• Simulating an infinite mean waiting time
• Equidistant sampling for the maximum of a Brownian motion with drift on a finite horizon

This page was built for publication: Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary

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