Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On large deviations and design of efficient importance sampling algorithms
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematical Statistics.ORCID iD: 0000-0001-8702-2293
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of four papers, presented in Chapters 2-5, on the topics large deviations and stochastic simulation, particularly importance sampling. The four papers make theoretical contributions to the development of a new approach for analyzing efficiency of importance sampling algorithms by means of large deviation theory, and to the design of efficient algorithms using the subsolution approach developed by Dupuis and Wang (2007).

In the first two papers of the thesis, the random output of an importance sampling algorithm is viewed as a sequence of weighted empirical measures and weighted empirical processes, respectively. The main theoretical results are a Laplace principle for the weighted empirical measures (Paper 1) and a moderate deviation result for the weighted empirical processes (Paper 2). The Laplace principle for weighted empirical measures is used to propose an alternative measure of efficiency based on the associated rate function.The moderate deviation result for weighted empirical processes is an extension of what can be seen as the empirical process version of Sanov's theorem. Together with a delta method for large deviations, established by Gao and Zhao (2011), we show moderate deviation results for importance sampling estimators of the risk measures Value-at-Risk and Expected Shortfall.

The final two papers of the thesis are concerned with the design of efficient importance sampling algorithms using subsolutions of partial differential equations of Hamilton-Jacobi type (the subsolution approach).

In Paper 3 we show a min-max representation of viscosity solutions of Hamilton-Jacobi equations. In particular, the representation suggests a general approach for constructing subsolutions to equations associated with terminal value problems and exit problems. Since the design of efficient importance sampling algorithms is connected to such subsolutions, the min-max representation facilitates the construction of efficient algorithms.

In Paper 4 we consider the problem of constructing efficient importance sampling algorithms for a certain type of Markovian intensity model for credit risk. The min-max representation of Paper 3 is used to construct subsolutions to the associated Hamilton-Jacobi equation and the corresponding importance sampling algorithms are investigated both theoretically and numerically.

The thesis begins with an informal discussion of stochastic simulation, followed by brief mathematical introductions to large deviations and importance sampling. 

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. , xii, 20 p.
Series
TRITA-MAT-A, 14:05
Keyword [en]
Large deviations, Monte Carlo methods, importance sampling
National Category
Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:kth:diva-144423ISBN: 978-91-7595-130-0 (print)OAI: oai:DiVA.org:kth-144423DiVA: diva2:713478
Public defence
2014-05-14, Sal F3, Lindstedtsvägen 26, KTH, Stockholm, 13:15 (English)
Opponent
Supervisors
Note

QC 20140424

Available from: 2014-04-24 Created: 2014-04-23 Last updated: 2014-04-24Bibliographically approved
List of papers
1. Large deviations for weighted empirical measures arising in importance sampling
Open this publication in new window or tab >>Large deviations for weighted empirical measures arising in importance sampling
2016 (English)In: Stochastic Processes and their Applications, ISSN 0304-4149, E-ISSN 1879-209X, Vol. 126, no 1Article in journal (Refereed) Published
Abstract [en]

Importance sampling is a popular method for efficient computation of various properties of a distribution such as probabilities, expectations, quantiles etc. The output of an importance sampling algorithm can be represented as a weighted empirical measure, where the weights are given by the likelihood ratio between the original distribution and the sampling distribution. In this paper the efficiency of an importance sampling algorithm is studied by means of large deviations for the weighted empirical measure. The main result, which is stated as a Laplace principle for the weighted empirical measure arising in importance sampling, can be viewed as a weighted version of Sanov's theorem. The main theorem is applied to quantify the performance of an importance sampling algorithm over a collection of subsets of a given target set as well as quantile estimates. The proof of the main theorem relies on the weak convergence approach to large deviations developed by Dupuis and Ellis.

Place, publisher, year, edition, pages
Elsevier, 2016
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-117805 (URN)10.1016/j.spa.2015.08.002 (DOI)000366535500006 ()2-s2.0-84948440031 (Scopus ID)
Note

QC 20160115

Available from: 2013-02-05 Created: 2013-02-05 Last updated: 2017-12-06Bibliographically approved
2. Moderate deviation principles for importance sampling estimators of risk measures
Open this publication in new window or tab >>Moderate deviation principles for importance sampling estimators of risk measures
2017 (English)In: Journal of Applied Probability, ISSN 0021-9002, E-ISSN 1475-6072Article in journal (Refereed) Accepted
Abstract [en]

Importance sampling has become an important tool for the computation of tail-based risk measures. Since such quantities are often determined mainly by rare events standard Monte Carlo can be inefficient and importance sampling provides a way to speed up computations. This paper considers moderate deviations for the weighted empirical process, the process analogue of the weighted empirical measure, arising in importance sampling. The moderate deviation principle is established as an extension of existing results. Using a delta method for large deviations established by Gao and Zhao (Ann. Statist., 2011) together with classical large deviation techniques, the moderate deviation principle for the weighted empirical process is extended to functionals of the weighted empirical process which correspond to risk measures. The main results are moderate deviation principles for importance sampling estimators of the quantile function of a distribution and Expected Shortfall.

Keyword
Large deviations, moderate deviations, empirical processes, importance sampling, risk measures
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-117808 (URN)
Note

QCR 20161219

Available from: 2013-02-05 Created: 2013-02-05 Last updated: 2017-12-06Bibliographically approved
3. Min-max representations of viscosity solutions of Hamilton-Jacobi equations and applications in rare-event simulation
Open this publication in new window or tab >>Min-max representations of viscosity solutions of Hamilton-Jacobi equations and applications in rare-event simulation
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper a duality relation between the Mañé potential and Mather's action functional is derived in the context of convex and state-dependent Hamiltonians. The duality relation is used to obtain min-max representations of viscosity solutions of first order Hamilton-Jacobi equations. These min-max representations naturally suggest classes of subsolutions of Hamilton-Jacobi equations that arise in the theory of large deviations. The subsolutions, in turn, are good candidates for designing efficient rare-event simulation algorithms.

Keyword
Hamilton-Jacobi equations, viscosity solutions, Monte Carlo methods
National Category
Probability Theory and Statistics Mathematical Analysis
Research subject
Mathematics
Identifiers
urn:nbn:se:kth:diva-144419 (URN)
Note

QS 2014

Available from: 2014-04-23 Created: 2014-04-23 Last updated: 2014-04-24Bibliographically approved
4. Importance sampling for a Markovian intensity model with applications to credit risk
Open this publication in new window or tab >>Importance sampling for a Markovian intensity model with applications to credit risk
(English)Manuscript (preprint) (Other academic)
Abstract [en]

This paper considers importance sampling for estimation of rare-event probabilities in a Markovian intensity model for credit risk. The main contribution is the design of efficient importance sampling algorithms using subsolutions of a certain Hamilton-Jacobi equation. For certain instances of the credit risk model the proposed algorithm is proved to be asymptotically optimal. The computational gain compared to standard Monte Carlo is illustrated by numerical experiments.

National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-144420 (URN)
Note

QC 20170125

Available from: 2014-04-23 Created: 2014-04-23 Last updated: 2017-01-25Bibliographically approved

Open Access in DiVA

Thesis(519 kB)450 downloads
File information
File name FULLTEXT01.pdfFile size 519 kBChecksum SHA-512
284a9c61ae181c7218bad349332683a7c2bf6b1d8efa44563171e4844f1047c6f2a4652c36f2af71c3b1edd7a9bfe1c30aec419da017e82a32aa717782af9718
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Nyquist, Pierre
By organisation
Mathematical Statistics
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 450 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 606 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf