Exact simulation algorithms with applications in queueing theory and extreme value analysis

This dissertation focuses on the development and analysis of exact simulation algorithms with applications in queueing theory and extreme value analysis. We first introduce the first algorithm that samples max_𝑛≥0 {𝑆_𝑛 − 𝑛^α} where 𝑆_𝑛 is a mean zero random walk, and 𝑛^α with α ∈ (1/2,1) defines a nonlinear boundary. We apply this algorithm to construct the first exact simulation method for the steady-state departure process of a 𝐺𝐼/𝐺𝐼/∞ queue where the service time distribution has infinite mean. Next, we consider the random field 𝑀 (𝑡) = sup_(𝑛≥1) 􏰄{ − log 𝑨_𝑛 + 𝑋_𝑛 (𝑡)􏰅}, 𝑡 ∈ 𝑇 , for a set 𝑇 ⊂ ℝ^𝓂, where (𝑋_𝑛) is an iid sequence of centered Gaussian random fields on 𝑇 and 𝑂 < 𝑨₁ < 𝑨₂ < . . . are the arrivals of a general renewal process on (0, ∞), independent of 𝑋_𝑛. In particular, a large class of max-stable random fields with Gumbel marginals have such a representation. Assume that the number of function evaluations needed to sample 𝑋_𝑛 at 𝑑 locations 𝑡₁, . . . , 𝑡_𝑑 ∈ 𝑇 is 𝑐(𝑑). We provide an algorithm which samples 𝑀(𝑡_{1}), . . . ,𝑀(𝑡_𝑑) with complexity 𝑂 (𝑐(𝑑)^{1+𝘰 (1)) as measured in the 𝐿_𝑝 norm sense for any 𝑝 ≥ 1.

Moreover, if 𝑋_𝑛 has an a.s. converging series representation, then 𝑀 can be a.s. approximated with error δ uniformly over 𝑇 and with complexity 𝑂 (1/(δl og (1/\δ((^{1/α}, where α relates to the Hölder continuity exponent of the process 𝑋_𝑛 (so, if 𝑋_𝑛 is Brownian motion, α =1/2). In the final part, we introduce a class of unbiased Monte Carlo estimators for multivariate densities of max-stable fields generated by Gaussian processes. Our estimators take advantage of recent results on the exact simulation of max-stable fields combined with identities studied in the Malliavin calculus literature and ideas developed in the multilevel Monte Carlo literature. Our approach allows estimating multivariate densities of max-stable fields with precision 𝜀 at a computational cost of order 𝑂 (𝜀 ⁻² log log log 1/𝜀).