Simulating the maximum of a random walk (Q1973290)

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\).