Monte Carlo distribution shifting technique
Exponential Tilting (ET), Exponential Twisting, or Exponential Change of Measure (ECM) is a distribution shifting technique used in many parts of mathematics.
The different exponential tiltings of a random variable formula_1 is known as the natural exponential family of formula_1.
Exponential Tilting is used in Monte Carlo Estimation for rare-event simulation, and rejection and importance sampling in particular.
In mathematical finance Exponential Tilting is also known as Esscher tilting (or the Esscher transform), and often combined with indirect Edgeworth approximation and is used in such contexts as insurance futures pricing.
The earliest formalization of Exponential Tilting is often attributed to Esscher with its use in importance sampling being attributed to David Siegmund.
Overview.
Given a random variable formula_1 with probability distribution formula_4, density formula_5, and moment generating function (MGF) formula_6, the exponentially tilted measure formula_7 is defined as follows:
formula_8
where formula_9 is the cumulant generating function (CGF) defined as 
formula_10 
We call 
formula_11 
the formula_12-tilted density of formula_1. It satisfies formula_14.
The exponential tilting of a random vector formula_1 has an analogous definition:
formula_16
where formula_17.
Example.
The exponentially tilted measure in many cases has the same parametric form as that of formula_1. One-dimensional examples include the normal distribution, the exponential distribution, the binomial distribution and the Poisson distribution. 
For example, in the case of the normal distribution, formula_19 the tilted density formula_20 is the formula_21 density. The table below provides more examples of tilted densities.
For some distributions, however, the exponentially tilted distribution does not belong to the same parametric family as formula_5. An example of this is the Pareto distribution with formula_23, where formula_20 is well defined for formula_25 but is not a standard distribution. In such examples, the random variable generation may not always be straightforward.
In statistical mechanics, the energy of a system in equilibrium with a heat bath has the Boltzmann distribution: formula_26, where formula_27 is the inverse temperature. Exponential tilting then corresponds to changing the temperature: formula_28.
Similarly, the energy and particle number of a system in equilibrium with a heat and particle bath has the grand canonical distribution: formula_29, where formula_30 is the chemical potential. Exponential tilting then corresponds to changing both the temperature and the chemical potential.
Advantages.
In many cases, the tilted distribution belongs to the same parametric family as the original. This is particularly true when the original density belongs to the exponential family of distribution. This simplifies random variable generation during Monte-Carlo simulations. Exponential tilting may still be useful if this is not the case, though normalization must be possible and additional sampling algorithms may be needed.
In addition, there exists a simple relationship between the original and tilted CGF, 
formula_31 
We can see this by observing that 
formula_32 
Thus, 
formula_33.
Clearly, this relationship allows for easy calculation of the CGF of the tilted distribution and thus the distributions moments. Moreover, it results in a simple form of the likelihood ratio. Specifically, 
formula_34.
formula_39 
This means that the formula_40-th cumulant of the tilted formula_1 is formula_42. In particular, the expectation of the tilted distribution is 
formula_43.
The variance of the tilted distribution is 
formula_44.
formula_56 
between the tilted distribution formula_57 and the original distribution formula_58 of formula_1.
formula_61.
Applications.
Rare-event simulation.
The exponential tilting of formula_1, assuming it exists, supplies a family of distributions that can be used as proposal distributions for acceptance-rejection sampling or importance distributions for importance sampling. One common application is sampling from a distribution conditional on a sub-region of the domain, i.e. formula_63. With an appropriate choice of formula_12, sampling from formula_7 can meaningfully reduce the required amount of sampling or the variance of an estimator.
Saddlepoint approximation.
The saddlepoint approximation method is a density approximation methodology often used for the distribution of sums and averages of independent, identically distributed random variables that employs Edgeworth series, but which generally performs better at extreme values. From the definition of the natural exponential family, it follows that 
formula_66. 
Applying the Edgeworth expansion for formula_67, we have
formula_68
where formula_69 is the standard normal density of 
formula_70, 
formula_71, 
and formula_72 are the hermite polynomials.
When considering values of formula_73 progressively farther from the center of the distribution, formula_74 and the formula_75 terms become unbounded. However, for each value of formula_73, we can choose formula_12 such that 
formula_78
This value of formula_12 is referred to as the saddle-point, and the above expansion is always evaluated at the expectation of the tilted distribution. This choice of formula_12 leads to the final representation of the approximation given by
formula_81
Rejection sampling.
Using the tilted distribution formula_82 as the proposal, the rejection sampling algorithm prescribes sampling from formula_20 and accepting with probability 
formula_84 
where 
formula_85
That is, a uniformly distributed random variable formula_86 is generated, and the sample from formula_20 is accepted if
formula_88 
Importance sampling.
Applying the exponentially tilted distribution as the importance distribution yields the equation 
formula_89, 
where 
formula_90
is the likelihood function. So, one samples from formula_91 to estimate the probability under the importance distribution formula_92 and then multiplies it by the likelihood ratio. Moreover, we have the variance given by
formula_93.
Example.
Assume independent and identically distributed formula_94 such that formula_95. In order to estimate formula_96, we can employ importance sampling by taking 
formula_97. 
The constant formula_98 can be rewritten as formula_99 for some other constant formula_100. Then, 
formula_101, 
where formula_102 denotes the formula_12 defined by the saddle-point equation 
formula_104.
Stochastic processes.
Given the tilting of a normal R.V., it is intuitive that the exponential tilting of formula_105, a Brownian motion with drift formula_30 and variance formula_107, is a Brownian motion with drift formula_108 and variance formula_107. Thus, any Brownian motion with drift under formula_4 can be thought of as a Brownian motion without drift under formula_111. To observe this, consider the process formula_112. formula_113. The likelihood ratio term, formula_114, is a martingale and commonly denoted formula_115. Thus, a Brownian motion with drift process (as well as many other continuous processes adapted to the Brownian filtration) is a formula_111-martingale.
Stochastic Differential Equations.
The above leads to the alternate representation of the stochastic differential equation formula_117: formula_118, where formula_119 = formula_120. Girsanov's Formula states the likelihood ratio formula_121. Therefore, Girsanov's Formula can be used to implement importance sampling for certain SDEs.
Tilting can also be useful for simulating a process formula_122 via rejection sampling of the SDE formula_123. We may focus on the SDE since we know that formula_122 can be written formula_125. As previously stated, a Brownian motion with drift can be tilted to a Brownian motion without drift. Therefore, we choose formula_126. The likelihood ratio formula_127 
formula_128. This likelihood ratio will be denoted formula_129. To ensure this is a true likelihood ratio, it must be shown that formula_130. Assuming this condition holds, it can be shown that formula_131. So, rejection sampling prescribes that one samples from a standard Brownian motion and accept with probability formula_132.
Choice of tilting parameter.
Siegmund's algorithm.
Assume i.i.d. X's with light tailed distribution and formula_133. In order to estimate formula_134 where formula_135, when formula_98 is large and hence formula_137 small, the algorithm uses exponential tilting to derive the importance distribution. The algorithm is used in many aspects, such as sequential tests, G/G/1 queue waiting times, and formula_138 is used as the probability of ultimate ruin in ruin theory. In this context, it is logical to ensure that formula_139. The criterion formula_140, where formula_141 is s.t. formula_142 achieves this. Siegmund's algorithm uses formula_143, if it exists, where formula_144 is defined in the following way: 
formula_145. 
It has been shown that formula_144 is the only tilting parameter producing bounded relative error (formula_147).
Black-Box algorithms.
We can only see the input and output of a black box, without knowing its structure. The algorithm is to use only minimal information on its structure. When we generate random numbers, the output may not be 
within the same common parametric class, such as normal or exponential distributions. An automated way may be used to perform ECM. Let formula_148be i.i.d. r.v.’s with distribution formula_149; for simplicity we assume formula_150. Define formula_151, where formula_152, . . . are independent (0, 1) uniforms. A randomized stopping time for formula_153, . . . is then a stopping time w.r.t. the filtration formula_154, . . . Let further formula_155 be a class of distributions formula_149 on formula_157 with formula_158 and define formula_159 by formula_160. We define a black-box algorithm for ECM for the given formula_12 and the given class formula_162of distributions as a pair of a randomized stopping time formula_163 and an formula_164 measurable r.v. formula_165 such that formula_165 is distributed according to formula_167 for any formula_168. Formally, we write this as formula_169 for all formula_170. In other words, the rules of the game are that the algorithm may use
simulated values from formula_171 and additional uniforms to produce an r.v. from formula_167.
References.
 ;templatestyles src="Reflist/styles.css" / ;