Tail asymptotics for the maximum of perturbed random walk

Consider a random walk S=(Sn:n.0) that is .perturbed. by a stationary sequence (.n:n.0) to produce the process (Sn+.n:n.0). This paper is concerned with computing the distribution of the all-time maximum M.=max.{Sk+.k:k.0} of perturbed random walk with a negative drift. Such a maximum arises in several different applications settings, including production systems, communications networks and insurance risk. Our main results describe asymptotics for .(M.>x) as x... The tail asymptotics depend greatly on whether the .n.s are light-tailed or heavy-tailed. In the light-tailed setting, the tail asymptotic is closely related to the Cramér.Lundberg asymptotic for standard random walk.