Simulating the maximum of a random walk

DOI10.1016/S0378-3758(99)00075-0MaRDI QIDQ1973290zbMATH OpenOpenAlexFDO

Authors Katherine Bennett Ensor, Peter W. Glynn

Publication date 16 December 2001

Published in Journal of Statistical Planning and Inference (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0378-3758(99)00075-0

zbMATH Keywords

random walksimulation

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22)

Review text

Let \(X= (x_n: n\geq 1)\) be a sequence of real-valued independent identically distributed random variables and \(S_0= 0\), \(S_n= X_1+\cdots+ X_n\), so \(S= (S_n:n\geq 0)\) is the associated random walk. The paper deals with the development of an exact sampling technique for generating the random variable \(M= \max(S_n:n\geq 0)\). For the practice an alternative is to simulate the Markov chain \(W\) and to average over the chain's trajectory in order to estimate the expectation of any given functional of \(M\). The main contribution of the paper is how to generate the random variable \(M\) in finite time or equivalently how to generate a stationary version of the Markov chain \(W\). It provides a ``coupling between \(M\) and a certain closely related exponential random variable and it allows to apply standard nonparametric methodology to the estimation of various functionals corresponding to \(M\).

Recommendations

• An iterative approximation procedure for the distribution of the maximum of a random walk
• Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary
• Search for the maximum of a random walk
• The maximum of a random walk whose mean path has a maximum
• Maximum on a random time interval of a random walk with infinite mean

Cites work

• Approximation Theorems of Mathematical Statistics
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• Exponential families and regression in the Monte Carlo study of queues and random walks
• scientific article; zbMATH DE number 4013703 (Why is no real title available?)
• scientific article; zbMATH DE number 3815002 (Why is no real title available?)
• scientific article; zbMATH DE number 3538576 (Why is no real title available?)
• Queueing Simulation in Heavy Traffic
• Sequential analysis. Tests and confidence intervals
• Stationarity detection in the initial transient problem
• Technical Note—Simulating the GI/G/1 Queue in Heavy Traffic
• The Asymptotic Efficiency of Simulation Estimators

Cited in

(17)

• -strong simulation of the convex minorants of stable processes and meanders
• Perfect sampling of GI/GI/\(c\) queues
• Perfect sampling of a single-server queue with periodic Poisson arrivals
• Entrance times of random walks: with applications to pension fund modeling
• Stochastic representations of Max-type functionals of a random walk
• The maximum of a random walk whose mean path has a maximum
• NEW ESTIMATORS FOR EFFICIENT GI/G/1 SIMULATION
• A dichotomy for sampling barrier-crossing events of random walks with regularly varying tails
• Exact sampling of the infinite horizon maximum of a random walk over a nonlinear boundary
• Double Happiness: Enhancing the Coupled Gains of L-lag Coupling via Control Variates
• Perfect Sampling of Hawkes Processes and Queues with Hawkes Arrivals
• Exact simulation of the extrema of stable processes
• Perfect Sampling of Generalized Jackson Networks
• Exact estimation for Markov chain equilibrium expectations
• Simulation-based computation of the workload correlation function in a Lévy-driven queue
• Monte Carlo Algorithms for Finding the Maximum of a Random Walk with Negative Drift
• Steady-state simulation of reflected Brownian motion and related stochastic networks

This page was built for publication: Simulating the maximum of a random walk

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