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

DOI10.1017/JPR.2019.9zbMATH Open1415.60043arXiv1609.06402OpenAlexW2963476791MaRDI QIDQ4968514FDOQ4968514

Authors: Jing Dong, Zhipeng Liu, Jose Blanchet 

Publication date: 15 July 2019

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

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.

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

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

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)

Cites Work

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

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)