The maximum of perturbed random walk limit theorems and applications

A perturbed random walk is a stochastic process obtained by taking an ordinary random walk (S_n: n ≥ 0) and adding to it a stationary sequence (ξ_n: n ≥ 0). Similarly to the unperturbed process, a perturbed random walk arises in analysis of certain models describing production and telecommunication systems, as well as insurance risk. In the production problem, for instance, introducing such process enables us to compute the Order-To-Delivery time for the production facility in the presence of uncertainties generated by both the downstream demand and the upstream supply. We focus throughout this thesis on getting approximations of the distribution of the maximum of a perturbed random walk, M_∞, which describes the performance of such systems.; We first propose a representation of the distribution of M _∞. We obtain a closed-form exact solution of this distribution in the particular case where (−X_j: j ≥ 1) is an i.i.d sequence of exponential random variables. The X _j's being the increments of the random walk. Secondly, we look into “heavy-traffic” diffusion approximations for M _∞, when the utilization of the system is quite high. The all time maximum, M_∞ is then approximated by a functional of reflected Brownian motion when the drift of the underlying (unperturbed) random walk (S_n: n ≥ 0) is close to zero. When the perturbation has a light tail, the result is the sum of two components (one due to the random walk and another one generated by the perturbation). In the heavy tail case, the distribution of M_∞ has a more complex formulation but is essentially governed by the perturbation. We provide in this case a way of computing numerically this approximation.; Finally, we obtain tail asymptotics for the all-time maximum of a perturbed random walk. These results are relevant when one is interested in keeping the system's performance (P (M_∞ > x)) close to zero. We develop Cramér-Lundberg type approximations for M_∞. Specifically, we establish that when the perturbations (ξ_n: n ≥ 0) have an appropriately light (right) tail, then P (M _∞ > x) has an exponential decay rate given by the conventional Cramér-Lundberg exponential decay rate for the tail of the maximum of (S_n: n ≥ 0). We also provide upper and lower bounds for P (M_∞ > x) that are, in some sense, within a constant factor of the true tail probability. Finally, we develop exact asymptotics for P (M _∞ > x) when the perturbations have a heavy tail.