Abstract

We focus on the design and analysis of efficient Monte Carlo methods for computing the tail probability at level b of the maximum of a Gaussian random field and the associated conditional expectations of the field given excursions at levels larger than b. Nave Monte Carlo takes an exponential computational cost in b to estimate such tail probabilities and associated conditional expectations with prescribed relative accuracy. In contrast, our Monte Carlo procedures exhibit at the most polynomial complexity in b assuming only that the mean and covariance functions are Holder continuous. In presence of more regularity conditions, such as homogeneity and smoothness, the complexity results can be further improved to constant. Central to the design of Monte Carlo scheme and its efficiency analysis is a change of measure that is NOT of the traditional exponential tilting form. This change of measure admits different representations that link the analysis of Monte Carlo methods to the random fields geometry. This feature is appealing to both simulation design and theoretical development of random fields.