**Title: Accuracy and Efficiency of Barrier-Hitting and Extreme Event Simulation**

**Advisor**: Dr. Ton Dieker

**Committee Members:**

Dr. Robert Foley

Dr. David Goldberg

Dr. Karl Sigman

Dr. Enlu Zhou

**Date and time: Friday, December 9th, 2:00 PM.**

**Location**: ISyE Groseclose Building, 226A

Abstract:

In this thesis we consider the broad field of simulation of barrier-hitting and extreme events events of stochastic processes. Our focus is on the analysis of the efficiency and accuracy of these simulation methods; especially, we are interested in providing theoretical mathematical guarantees for efficiency and accuracy. Loosely speaking, efficiency of a simulation algorithm is related to the time the algorithm requires to produce an output sample; and accuracy relates to how close is the distribution of the output of the algorithm, compared to the "true" or "target" distribution of the event intended to sample. A third topic that permeates all aspects of this thesis is the simulation of reflected processes, which is usually done by simulating the extremes of a "free" or "unreflected" process. We now give a brief description of the parts of this thesis.

In Chapter 1 we give a general overview of Chapters 2 and 3 of this thesis. We argue that the overarching theme connecting them is the study of efficiency and accuracy of methods for the simulation of barrier-hitting events, extreme events, or events of reflected processes.

In Chapter 2 we consider heavy-tailed random walks with negative drift, and study the simulation of paths of the random walk up to the first time it crosses a fixed positive barrier. We consider the framework of exact sampling algorithms that use the change of measure technique; in particular, with this technique the simulated barrier-hitting paths are unbiased or completely accurate. As a consequence, our work in Chapter 2 is mostly concerned with the study of efficiency of these methods. For that, we propose a framework to evaluate how efficient is a change of measure for the simulation of barrier-hitting paths with the change of measure technique. We apply this framework to evaluate the efficiency of the change of measure of Blanchet and Glynn (2008) when the random walk step sizes have regularly varying right tails, say with tail index alpha>1, and lighter left tails. We study this particular change of measure because it has been a successful measure for the sampling of rare events for heavy-tailed random walks with Importance Sampling.

Our main contributions of Chapter 2 are the following. First, for a requirement characterizing how much more likely the change of measure is to sample a barrier-hitting path, the Blanchet-Glynn change of measure is efficient only when the tail index alpha is in the interval (1, 3/2); in particular this is the regime of heaviest tails. Second, for a requirement quantifying the expected number of steps needed to sample a barrier-hit with the Blanchet-Glynn change of measure, we show that the expected number of steps is infinite for alpha in (1, 3/2). In particular, the latter result corrects a non-central result of Blanchet and Glynn (2008). We also discuss that the value alpha=3/2 has arisen as a threshold for efficiency criteria in other related algorithms for random walks with regularly varying right tails, which raises the question of how precisely are these works connected. We remark that the work in Chapter 2 was originally motivated by the design of an algorithm for exact sampling of stationary reflected processes.

In Chapter 3 of this thesis we derive weak limits related to the discretization errors of sampling barrier-hitting and extreme events of Brownian motion by using the Euler discretization simulation method. In detail, we consider the Euler discretization approximation of Brownian motion to sample barrier-hitting events, i.e. hitting for the first time a deterministic "barrier" function; and to sample extreme events, i.e. attaining a minimum on a given compact time interval or unbounded closed time interval. For each case we study the discretization error between the actual time the event occurs versus the time the event occurs for the discretized path, and also the discretization error on the position of the Brownian motion at these times.

The main contributions of Chapter 3 are the following. We show that if the step-size of the time mesh is 1/n then in each of the three aforementioned events the discretization error for the times converges at rate O(1/n) and the error for the position of the Brownian motion converges at rate O(1/sqrt n). We show limits in distribution for the discretization errors normalized by their convergence rate, and give closed-form analytic expressions for the limiting random variables. Additionally, we use these limits to study the asymptotic behavior of Gaussian random walks in the following situations: (1.) the overshoot of a Gaussian walk above a barrier that goes to infinity; (2.) the minimum of a Gaussian walk compared to the minimum of the Brownian motion obtained when interpolating the Gaussian walk with Brownian bridges, both up to the same time horizon that goes to infinity; and (3.) the global minimum of a Gaussian walk compared to the global minimum of the Brownian motion obtained when interpolating the Gaussian walk with Brownian bridges, when both have the same positive drift decreasing to zero. In deriving these limits in distribution we provide a unified framework to understand the relation between several papers where the constant -z(1/2)/sqrt(2 pi) has appeared, where z is the Riemann zeta function. In particular, we show that this constant is the mean of some of the limiting distributions we encounter.