State-independent importance sampling for random walks with regularly varying increments
We develop importance sampling based efficient simulation techniques for three commonly encountered rare event probabilities associated with random walks having i.i.d. regularly varying increments; namely, 1) the large deviation probabilities, 2) the level crossing probabilities, and 3) the level cr...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2015-03-01
|
| Series: | Stochastic Systems |
| Subjects: | |
| Online Access: | http://www.i-journals.org/ssy/viewarticle.php?id=114&layout=abstract |
| _version_ | 1818243547291189248 |
|---|---|
| author | Karthyek R. A. Murthy Sandeep Juneja Jose Blanchet |
| author_facet | Karthyek R. A. Murthy Sandeep Juneja Jose Blanchet |
| author_sort | Karthyek R. A. Murthy |
| collection | DOAJ |
| description | We develop importance sampling based efficient simulation techniques for three commonly encountered rare event probabilities associated with random walks having i.i.d. regularly varying increments; namely, 1) the large deviation probabilities, 2) the level crossing probabilities, and 3) the level crossing probabilities within a regenerative cycle. Exponential twisting based state-independent methods, which are effective in efficiently estimating these probabilities for light-tailed increments are not applicable when the increments are heavy-tailed. To address the latter case, more complex and elegant state-dependent efficient simulation algorithms have been developed in the literature over the last few years. We propose that by suitably decomposing these rare event probabilities into a dominant and further residual components, simpler state-independent importance sampling algorithms can be devised for each component resulting in composite unbiased estimators with desirable efficiency properties. When the increments have infinite variance, there is an added complexity in estimating the level crossing probabilities as even the well known zero-variance measures have an infinite expected termination time. We adapt our algorithms so that this expectation is finite while the estimators remain strongly efficient. Numerically, the proposed estimators perform at least as well, and sometimes substantially better than the existing state-dependent estimators in the literature. |
| first_indexed | 2024-12-12T14:02:52Z |
| format | Article |
| id | doaj.art-36c3298ea7f64df8b9223f94cc66e1ff |
| institution | Directory Open Access Journal |
| issn | 1946-5238 1946-5238 |
| language | English |
| last_indexed | 2024-12-12T14:02:52Z |
| publishDate | 2015-03-01 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | Article |
| series | Stochastic Systems |
| spelling | doaj.art-36c3298ea7f64df8b9223f94cc66e1ff2022-12-22T00:22:17ZengInstitute for Operations Research and the Management Sciences (INFORMS)Stochastic Systems1946-52381946-52382015-03-014232137410.1214/13-SSY114State-independent importance sampling for random walks with regularly varying incrementsKarthyek R. A. Murthy0Sandeep Juneja1Jose Blanchet2Tata Institute of Fundamental ResearchTata Institute of Fundamental ResearchColumbia UniversityWe develop importance sampling based efficient simulation techniques for three commonly encountered rare event probabilities associated with random walks having i.i.d. regularly varying increments; namely, 1) the large deviation probabilities, 2) the level crossing probabilities, and 3) the level crossing probabilities within a regenerative cycle. Exponential twisting based state-independent methods, which are effective in efficiently estimating these probabilities for light-tailed increments are not applicable when the increments are heavy-tailed. To address the latter case, more complex and elegant state-dependent efficient simulation algorithms have been developed in the literature over the last few years. We propose that by suitably decomposing these rare event probabilities into a dominant and further residual components, simpler state-independent importance sampling algorithms can be devised for each component resulting in composite unbiased estimators with desirable efficiency properties. When the increments have infinite variance, there is an added complexity in estimating the level crossing probabilities as even the well known zero-variance measures have an infinite expected termination time. We adapt our algorithms so that this expectation is finite while the estimators remain strongly efficient. Numerically, the proposed estimators perform at least as well, and sometimes substantially better than the existing state-dependent estimators in the literature.http://www.i-journals.org/ssy/viewarticle.php?id=114&layout=abstractState-independent importance samplingrare-event simulationheavy-tailsrandom walkssingle-server queueinsurance ruin |
| spellingShingle | Karthyek R. A. Murthy Sandeep Juneja Jose Blanchet State-independent importance sampling for random walks with regularly varying increments Stochastic Systems State-independent importance sampling rare-event simulation heavy-tails random walks single-server queue insurance ruin |
| title | State-independent importance sampling for random walks with regularly varying increments |
| title_full | State-independent importance sampling for random walks with regularly varying increments |
| title_fullStr | State-independent importance sampling for random walks with regularly varying increments |
| title_full_unstemmed | State-independent importance sampling for random walks with regularly varying increments |
| title_short | State-independent importance sampling for random walks with regularly varying increments |
| title_sort | state independent importance sampling for random walks with regularly varying increments |
| topic | State-independent importance sampling rare-event simulation heavy-tails random walks single-server queue insurance ruin |
| url | http://www.i-journals.org/ssy/viewarticle.php?id=114&layout=abstract |
| work_keys_str_mv | AT karthyekramurthy stateindependentimportancesamplingforrandomwalkswithregularlyvaryingincrements AT sandeepjuneja stateindependentimportancesamplingforrandomwalkswithregularlyvaryingincrements AT joseblanchet stateindependentimportancesamplingforrandomwalkswithregularlyvaryingincrements |