2020 Theses Doctoral

# 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/π).

## Subjects

## Files

- Liu_columbia_0054D_15782.pdf application/pdf 1.34 MB Download File

## More About This Work

- Academic Units
- Industrial Engineering and Operations Research
- Thesis Advisors
- Blanchet, Jose H.
- Degree
- Ph.D., Columbia University
- Published Here
- August 10, 2022