The transform likelihood ratio method for rare event simulation with heavy tails

We present a novel method, called the transform likelihood ratio (TLR) method, for estimation of rare event probabilities with heavy-tailed distributions. Via a simple transformation ( change of variables) technique the TLR method reduces the original rare event probability estimation with heavy tail distributions to an equivalent one with light tail distributions. Once this transformation has been established we estimate the rare event probability via importance sampling, using the classical exponential change of measure or the standard likelihood ratio change of measure. In the latter case the importance sampling distribution is chosen from the same parametric family as the transformed distribution. We estimate the optimal parameter vector of the importance sampling distribution using the cross-entropy method. We prove the polynomial complexity of the TLR method for certain heavy-tailed models and demonstrate numerically its high efficiency for various heavy-tailed models previously thought to be intractable. We also show that the TLR method can be viewed as a universal tool in the sense that not only it provides a unified view for heavy-tailed simulation but also can be efficiently used in simulation with light-tailed distributions. We present extensive simulation results which support the efficiency of the TLR method.

Improved algorithms for rare event simulation with heavy tails

The estimation of P(S-n > u) by simulation, where S, is the sum of independent. identically distributed random varibles Y-1,..., Y-n, is of importance in many applications. We propose two simulation estimators based upon the identity P(S-n > u) = nP(S, > u, M-n = Y-n), where M-n = max(Y-1,..., Y-n). One estimator uses importance sampling (for Y-n only), and the other uses conditional Monte Carlo conditioning upon Y1,..., Yn-1. Properties of the relative error of the estimators are derived and a numerical study given in terms of the M/G/1 queue in which n is replaced by an independent geometric random variable N. The conclusion is that the new estimators compare extremely favorably with previous ones. In particular, the conditional Monte Carlo estimator is the first heavy-tailed example of an estimator with bounded relative error. Further improvements are obtained in the random-N case, by incorporating control variates and stratification techniques into the new estimation procedures.

Efficient simulation of a Tandem Jackson Network

The two-node tandem Jackson network serves as a convenient reference model for the analysis and testing of different methodologies and techniques in rare event simulation. In this paper we consider a new approach to efficiently estimate the probability that the content of the second buffer exceeds some high level L before it becomes empty, starting from a given state. The approach is based on a Markov additive process representation of the buffer processes, leading to an exponential change of measure to be used in an importance sampling procedure. Unlike changes of measures proposed and studied in recent literature, the one derived here is a function of the content of the first buffer. We prove that when the first buffer is finite, this method yields asymptotically efficient simulation for any set of arrival and service rates. In fact, the relative error is bounded independent of the level L; a new result which is not established for any other known method. When the first buffer is infinite, we propose a natural extension of the exponential change of measure for the finite buffer case. In this case, the relative error is shown to be bounded (independent of L) only when the second server is the bottleneck; a result which is known to hold for some other methods derived through large deviations analysis. When the first server is the bottleneck, experimental results using our method seem to suggest that the relative error is bounded linearly in L.

A tutorial on the cross-entropy method

The cross-entropy (CE) method is a new generic approach to combinatorial and multi-extremal optimization and rare event simulation. The purpose of this tutorial is to give a gentle introduction to the CE method. We present the CE methodology, the basic algorithm and its modifications, and discuss applications in combinatorial optimization and machine learning. combinatorial optimization

Mutations in exon 3 of the beta-catenin gene are rare in melanoma cell lines

Mutations in exon 3 of the CTNNB1 gene encoding beta-catenin have been reported in colorectal cancer cell lines and tumours. Although one study reported mutations or deletions affecting beta-catenin in 20% of melanoma cell lines, subsequent reports detected a much lower frequency of aberrations in uncultured melanomas. To determine whether this difference in mutation frequency reflected an in vitro culturing artefact, exon 3 of CTNNB1 was screened in a panel of 62 melanoma cell lines. In addition, reverse transcription-polymerase chain reaction (RT-PCR) was performed to detect intragenic deletions affecting exon 3. One out of 62 (1.6%) cell lines was found to carry a mutation, indicating that aberration of the Wnt-l/wingless pathway through activation of beta-catenin is a rare event, even in melanoma cell lines. (C) 2002 Lippincott Williams Wilkins.

Heavy tails, importance sampling and cross-entropy

We consider the problem of estimating P(Yi + (...) + Y-n > x) by importance sampling when the Yi are i.i.d. and heavy-tailed. The idea is to exploit the cross-entropy method as a toot for choosing good parameters in the importance sampling distribution; in doing so, we use the asymptotic description that given P(Y-1 + (...) + Y-n > x), n - 1 of the Yi have distribution F and one the conditional distribution of Y given Y > x. We show in some specific parametric examples (Pareto and Weibull) how this leads to precise answers which, as demonstrated numerically, are close to being variance minimal within the parametric class under consideration. Related problems for M/G/l and GI/G/l queues are also discussed.

Successful defibrillation of a dental patient in cardiac arrest

Cardiac arrest is a very rare event in a dental patient. However, practitioners have a duty of care to their patients if ever such an event occurs. The cardiac arrest discussed in this case report occurred in an elderly person with an implanted pacemaker whilst undergoing restorative dental treatment. Cardiac arrest was diagnosed and cardiopulmonary resuscitation instituted immediately, followed within three minutes by successful defibrillation using the School's semi-automatic defibrillator.

Carpogenic germination of Sclerotinia minor and potential distribution in Australia

This study confirms that Australian isolates of Sclerotinia minor can produce fertile apothecia and further demonstrates that ascospores collected from these apothecia are pathogenic to sunflower (Helianthus annuus). Sunflower is a known host of the related fungus Sclerotinia sclerotiorum and is grown in some regions where S. minor is known to occur. Head rot symptoms were produced following inoculation with S. minor ascospores. Predictive modeling using CLIMEX software suggested that conditions suitable for carpogenic germination of S. minor probably occur in Australia particularly in southern regions. Carpogenic germination is probably a rare event in northern regions and, if it does occur, probably does not coincide with anthesis in sunflower crops, therefore allowing disease escape.

Dapsone-induced agranulocytosis. The role of xenobiotic-metabolizing enzymes demonstrated by a case report [Dapson-induzierte agranulozytose. Die rolle fremdstoffmetabolisierender enzyme am beispiel einer kasuistik]

A 34-year-old female patient with a three year history of generalized granuloma annulare was treated systemically with dapsone (DADPS). Six weeks after the onset of treatment, the patient developed an extensive tonsillitis of the base of the tongue with fever and malaise. Routine laboratory work showed a leukocytopenia with agranulocytosis. Further investigation revealed a marked decrease of the enzyme activity of N-acetyltransferase 2, which plays an important role in dapsone metabolism. Treatment included the cessation of dapsone, antibiotic coverage, and G-CSF leading to the rapid improvement of symptoms and normalization of leukocyte counts. Dapsone-induced angina agranulocytotica is a rare event and is interpreted as an idiosyncratic reaction. Depending on genetic polymorphisms of various enzymes, dapsone can be metabolized to immunologically or toxicologically relevant intermediates. Because of the risk of severe hematologic reactions, dapsone should only be employed for solid indications and with appropriate monitoring.

Estimating buffer overflows in three stages using cross-entropy

In this paper we propose a fast adaptive Importance Sampling method for the efficient simulation of buffer overflow probabilities in queueing networks. The method comprises three stages. First we estimate the minimum Cross-Entropy tilting parameter for a small buffer level; next, we use this as a starting value for the estimation of the optimal tilting parameter for the actual (large) buffer level; finally, the tilting parameter just found is used to estimate the overflow probability of interest. We recognize three distinct properties of the method which together explain why the method works well; we conjecture that they hold for quite general queueing networks. Numerical results support this conjecture and demonstrate the high efficiency of the proposed algorithm.

Accelerating seismic energy release and evolution of event time and size statistics: Results from two heterogeneous cellular automaton models

The evolution of event time and size statistics in two heterogeneous cellular automaton models of earthquake behavior are studied and compared to the evolution of these quantities during observed periods of accelerating seismic energy release Drier to large earthquakes. The two automata have different nearest neighbor laws, one of which produces self-organized critical (SOC) behavior (PSD model) and the other which produces quasi-periodic large events (crack model). In the PSD model periods of accelerating energy release before large events are rare. In the crack model, many large events are preceded by periods of accelerating energy release. When compared to randomized event catalogs, accelerating energy release before large events occurs more often than random in the crack model but less often than random in the PSD model; it is easier to tell the crack and PSD model results apart from each other than to tell either model apart from a random catalog. The evolution of event sizes during the accelerating energy release sequences in all models is compared to that of observed sequences. The accelerating energy release sequences in the crack model consist of an increase in the rate of events of all sizes, consistent with observations from a small number of natural cases, however inconsistent with a larger number of cases in which there is an increase in the rate of only moderate-sized events. On average, no increase in the rate of events of any size is seen before large events in the PSD model.

Satellite observation and climate system model simulation of the St. Lawrence Island polynya

The St. Lawrence Island polynya (SLIP) is a commonly occurring winter phenomenon in the Bering Sea, in which dense saline water produced during new ice formation is thought to flow northward through the Bering Strait to help maintain the Arctic Ocean halocline. Winter darkness and inclement weather conditions have made continuous in situ and remote observation of this polynya difficult. However, imagery acquired from the European Space Agency ERS-1 Synthetic Aperture Radar (SAR) has allowed observation of the St. Lawrence Island polynya using both the imagery and derived ice displacement products. With the development of ARCSyM, a high resolution regional model of the Arctic atmosphere/sea ice system, simulation of the SLIP in a climate model is now possible. Intercomparisons between remotely sensed products and simulations can lead to additional insight into the SLIP formation process. Low resolution SAR, SSM/I and AVHRR infrared imagery for the St. Lawrence Island region are compared with the results of a model simulation for the period of 24-27 February 1992. The imagery illustrates a polynya event (polynya opening). With the northerly winds strong and consistent over several days, the coupled model captures the SLIP event with moderate accuracy. However, the introduction of a stability dependent atmosphere-ice drag coefficient, which allows feedbacks between atmospheric stability, open water, and air-ice drag, produces a more accurate simulation of the SLIP in comparison to satellite imagery. Model experiments show that the polynya event is forced primarily by changes in atmospheric circulation followed by persistent favorable conditions: ocean surface currents are found to have a small but positive impact on the simulation which is enhanced when wind forcing is weak or variable.

On the importance function in splitting simulation

The splitting method is a simulation technique for the estimation of very small probabilities. In this technique, the sample paths are split into multiple copies, at various stages in the simulation. Of vital importance to the efficiency of the method is the Importance Function (IF). This function governs the placement of the thresholds or surfaces at which the paths are split. We derive a characterisation of the optimal IF and show that for multi-dimensional models the natural choice for the IF is usually not optimal. We also show how nearly optimal splitting surfaces can be derived or simulated using reverse time analysis. Our numerical experiments illustrate that by using the optimal IF, one can obtain a significant improvement in simulation efficiency.