Exponential tilting

Given a random variable $X$ with probability distribution $\backslash mathbb\{P\}$, density $f$, and moment generating function (MGF) , the exponentially tilted measure $\backslash mathbb\{P\}\_\backslash theta$ is defined as follows:

:$\backslash mathbb\{P\}\_\backslash theta(X\; \backslash in\; dx)\; =\; \backslash frac\{\backslash mathbb\{E\}[e^\{\backslash theta\; X\}\backslash mathbb\{I\}[X\; \backslash in\; dx]]\}\{M\_X(\backslash theta)\}=e^\{\backslash theta\; x\; -\; \backslash kappa(\backslash theta)\}\backslash mathbb\{P\}(X\backslash in\; dx),$

where $\backslash kappa(\backslash theta)$ is the cumulant generating function (CGF) defined as

:$\backslash kappa(\backslash theta)\; =\; \backslash log\backslash mathbb\{E\}[e^\{\backslash theta\; X\}]\; =\; \backslash log\; M\_X(\backslash theta).$

We call

:$\backslash mathbb\{P\}\_\backslash theta(X\; \backslash in\; dx)=f\_\backslash theta(x)$

the $\backslash theta$-tilted density of $X$. It satisfies $f\_\backslash theta(x)\; \backslash propto\; e^\{\backslash theta\; x\}f(x)$.

The exponential tilting of a random vector $X$ has an analogous definition:

:$\backslash mathbb\{P\}\_\{\backslash theta\}(X\backslash in\; dx)\; =\; e^\{\backslash theta^T\; x\; -\; \backslash kappa(\backslash theta)\}\backslash mathbb\{P\}(X\backslash in\; dx),$

where $\backslash kappa(\backslash theta)\; =\; \backslash log\; \backslash mathbb\{E\}[\backslash exp\backslash \{\backslash theta^T\; X\backslash \}]$.

The exponentially tilted measure in many cases has the same parametric form as that of $X$. 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, $N(\; \backslash mu,\; \backslash sigma\; ^2)$ the tilted density $f\_\backslash theta(x)$ is the $N(\; \backslash mu\; +\; \backslash theta\; \backslash sigma\; ^2,\; \backslash sigma\; ^2)$ 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 $f$. An example of this is the Pareto distribution with $f(x)\; =\; \backslash alpha\; /(1\; +\; x)\; ^\backslash alpha,\; x\; >\; 0$, where $f\_\backslash theta(x)$ is well defined for but is not a standard distribution. In such examples, the random variable generation may not always be straightforward.Asmussen, Soren & Glynn, Peter (2007). Stochastic Simulation. Springer. pp. 164–167. {{ISBN|978-0-387-30679-7}}

In statistical mechanics, the energy of a system in equilibrium with a heat bath has the Boltzmann distribution: $\backslash mathbb\{P\}(E\backslash in\; dE)\; \backslash propto\; e^\{-\backslash beta\; E\}\; dE$, where $\backslash beta$ is the inverse temperature. Exponential tilting then corresponds to changing the temperature: $\backslash mathbb\{P\}\_\backslash theta\; (E\backslash in\; dE)\; \backslash propto\; e^\{-(\backslash beta\; -\; \backslash theta)\; E\}dE$.

Similarly, the energy and particle number of a system in equilibrium with a heat and particle bath has the grand canonical distribution: $\backslash mathbb\{P\}((N,\; E)\backslash in\; (dN,\; dE)\; )\; \backslash propto\; e^\{\backslash beta\; \backslash mu\; N\; -\backslash beta\; E\}\; dNdE$, where $\backslash mu$ is the chemical potential. Exponential tilting then corresponds to changing both the temperature and the chemical potential.

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,

:$\backslash kappa\_\backslash theta(\backslash eta)\; =\; \backslash log(\backslash mathbb\{E\}\_\backslash theta[e^\{\backslash eta\; X\}])\; =\; \backslash kappa(\backslash theta\; +\; \backslash eta)\; -\; \backslash kappa(\backslash theta).$

We can see this by observing that

:$F\_\backslash theta(x)\; =\; \backslash int\backslash limits\_\{\backslash infty\}^x\backslash exp\backslash \{\backslash theta\; y\; -\; \backslash kappa(\backslash theta)\backslash \}f(y)dy.$

Thus,

:$$

\begin{align}

\kappa_{\theta}(\eta) &= \log \int e^{\eta x}dF_{\theta}(x) \\

&= \log \int e^{\eta x}e^{\theta x - \kappa(\theta)}dF(x) \\

&= \log\mathbb{E}[e^{(\eta+\theta)X-\kappa(\theta)}] \\

&= \log(e^{\kappa(\eta+\theta)-\kappa(\theta)}) \\

&= \kappa(\eta+\theta)-\kappa(\theta)

\end{align}

.

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,

:$\backslash ell\; =\; \backslash frac\{d\backslash mathbb\{P\}\}\{d\backslash mathbb\{P\}\_\backslash theta\}\; =\; \backslash frac\{f(x)\}\{f\_\{\backslash theta\}(x)\}\; =\; e^\{-\; \backslash theta\; x\; +\; \backslash kappa(\backslash theta)\}$.

• If $\backslash kappa(\backslash eta)=\backslash log\; \backslash mathrm\{E\}[\backslash exp(\backslash eta\; X)]$ is the CGF of $X$, then the CGF of the $\backslash theta$-tilted $X$ is

::$\backslash kappa\_\backslash theta(\backslash eta)\; =\; \backslash kappa(\backslash theta\; +\; \backslash eta)\; -\; \backslash kappa(\backslash theta).$

:This means that the $i$-th cumulant of the tilted $X$ is $\backslash kappa^\{(i)\}(\backslash theta)$. In particular, the expectation of the tilted distribution is

::$\backslash mathrm\{E\}\_\backslash theta[X]=\backslash tfrac\{d\}\{d\backslash eta\}\backslash kappa\_\backslash theta(\backslash eta)|\_\{\backslash eta=0\}\; =\; \backslash kappa\text{'}(\backslash theta)$.

:The variance of the tilted distribution is

::$\backslash mathrm\{Var\}\_\backslash theta[X]=\backslash tfrac\{d^2\}\{d\backslash eta^2\}\backslash kappa\_\backslash theta(\backslash eta)|\_\{\backslash eta=0\}\; =\; \backslash kappa\text{'}\text{'}(\backslash theta)$.

• Repeated tilting is additive. That is, tilting first by $\backslash theta\_1$ and then $\backslash theta\_2$ is the same as tilting once by $\backslash theta\_1+\backslash theta\_2$.

• If $X$ is the sum of independent, but not necessarily identical random variables $X\_1,\; X\_2,\; \backslash dots$, then the $\backslash theta$-tilted distribution of $X$ is the sum of $X\_1,\; X\_2,\; \backslash dots$ each $\backslash theta$-tilted individually.

• If $\backslash mu=\backslash mathrm\{E\}[X]$, then $\backslash kappa(\backslash theta)-\backslash theta\; \backslash mu$ is the Kullback–Leibler divergence

::$D\_\backslash text\{KL\}(P\; \backslash parallel\; P\_\backslash theta)=\backslash mathrm\{E\}\; \backslash left[\backslash log\backslash tfrac\{P\}\{P\_\backslash theta\}\backslash right]$

:between the tilted distribution $P\_\backslash theta$ and the original distribution $P$ of $X$.

• Similarly, since $\backslash mathrm\{E\}\_\{\backslash theta\}[X]=\backslash kappa\text{'}(\backslash theta)$, we have the Kullback-Leibler divergence as

::$D\_\backslash text\{KL\}(P\_\backslash theta\; \backslash parallel\; P)\; =\; \backslash mathrm\{E\}\_\backslash theta\; \backslash left[\backslash log\backslash tfrac\{P\_\backslash theta\}\{P\}\; \backslash right]\; =\; \backslash theta\; \backslash kappa\text{'}(\backslash theta)\; -\; \backslash kappa(\backslash theta)$.

The exponential tilting of $X$, 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. $X|X\backslash in\; A$. With an appropriate choice of $\backslash theta$, sampling from $\backslash mathbb\{P\}\_\backslash theta$ can meaningfully reduce the required amount of sampling or the variance of an estimator.

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

:$f\_\{\backslash theta\}(\backslash bar\{x\})\; =\; f(\backslash bar\{x\})\backslash exp\backslash \{n(\backslash theta\; \backslash bar\{x\}\; -\; \backslash kappa(\backslash theta))\backslash \}$.

Applying the Edgeworth expansion for $f\_\{\backslash theta\}(\backslash bar\{x\})$, we have

:$f\_\{\backslash theta\}(\backslash bar\{x\})\; =\; \backslash psi(z)(\backslash mathrm\{Var\}[\backslash bar\{X\}])^\{-1/2\}\backslash left\backslash \{1\; +\; \backslash frac\{\backslash rho\_3(\backslash theta)h\_3(z)\}\{6\}\; +\; \backslash frac\{\backslash rho\_4(\backslash theta)h\_4(z)\}\{24\}\backslash dots\backslash right\backslash \},$

where $\backslash psi(z)$ is the standard normal density of

:$z\; =\; \backslash frac\{\backslash bar\{x\}\; -\; \backslash kappa\_\{\backslash bar\{x\}\}\; \text{'}\; (\backslash theta)\}\{\backslash kappa\_\{\backslash bar\{x\}\}\; \text{'}\text{'}(\backslash theta)\}$,

:$\backslash rho\_n(\backslash theta)\; =\; \backslash kappa^\{(n)\}(\backslash theta)\backslash \{\backslash kappa\; \text{'}\text{'}(\backslash theta)^\{n/2\}\backslash \}$,

and $h\_n$ are the hermite polynomials.

When considering values of $\backslash bar\{x\}$ progressively farther from the center of the distribution, $|z|\backslash rightarrow\; \backslash infty$ and the $h\_n(z)$ terms become unbounded. However, for each value of $\backslash bar\{x\}$, we can choose $\backslash theta$ such that

::$\backslash kappa\; \text{'}(\backslash theta)\; =\; \backslash bar\{x\}.$

This value of $\backslash theta$ is referred to as the saddle-point, and the above expansion is always evaluated at the expectation of the tilted distribution. This choice of $\backslash theta$ leads to the final representation of the approximation given by

:$f(\backslash bar\{x\})\; \backslash approx\; \backslash left(\backslash frac\{n\}\{2\backslash pi\backslash kappa\; \text{'}\text{'}(\backslash theta)\}\backslash right)^\{1/2\}\backslash exp\backslash \{n(\backslash kappa(\backslash theta)\; -\; \backslash theta\backslash bar\{x\})\backslash \}.${{Cite book|title=Saddlepoint Approximations with Applications|url=https://archive.org/details/saddlepointappro00butl|url-access=limited|last=Butler|first=Ronald|publisher=Cambridge University Press|year=2007|isbn=9780521872508|pages=[https://archive.org/details/saddlepointappro00butl/page/n169 156]–157}}{{Cite book|title=Advances in GLIM and Statistical Modelling|last=Seeber|first=G.U.H.|publisher=Springer|year=1992|isbn=978-0-387-97873-4 |pages=195–200}}

Using the tilted distribution $\backslash mathbb\{P\}\_\{\backslash theta\}$ as the proposal, the rejection sampling algorithm prescribes sampling from $f\_\backslash theta(x)$ and accepting with probability

:$\backslash frac\{1\}\{c\}\; \backslash exp(-\backslash theta\; x\; +\; \backslash kappa(\backslash theta)),$

where

:$c\; =\; \backslash sup\backslash limits\_\{x\backslash in\; X\}\backslash frac\{d\backslash mathbb\{P\}\}\{d\backslash mathbb\{P\}\_\{\backslash theta\}\}(x).$

That is, a uniformly distributed random variable $p\; \backslash sim\; \backslash mbox\{Unif\}(0,1)$ is generated, and the sample from $f\_\backslash theta(x)$ is accepted if

:$p\; \backslash leq\; \backslash frac\{1\}\{c\}\; \backslash exp(-\backslash theta\; x\; +\; \backslash kappa(\backslash theta)).$

Applying the exponentially tilted distribution as the importance distribution yields the equation

:$\backslash mathbb\{E\}(h(X))\; =\; \backslash mathbb\{E\}\_\{\backslash theta\}[\backslash ell(X)h(X)]$,

where

:$\backslash ell(X)\; =\; \backslash frac\{d\backslash mathbb\{P\}\}\{d\backslash mathbb\{P\}\_\{\backslash theta\}\}$

is the likelihood function. So, one samples from $f\_\{\backslash theta\}$ to estimate the probability under the importance distribution $\backslash mathbb\{P\}(dX)$ and then multiplies it by the likelihood ratio. Moreover, we have the variance given by

:$\backslash mbox\{Var\}(X)\; =\; \backslash mathbb\{E\}[(\backslash ell(X)h(X)^2]$.

Assume independent and identically distributed $\backslash \{X\_i\backslash \}$ such that . In order to estimate $\backslash mathbb\{P\}(X\_1\; +\; \backslash cdots\; +\; X\_n\; >\; c)$, we can employ importance sampling by taking

:$h(X)\; =\; \backslash mathbb\{I\}(\backslash sum\_\{i\; =\; 1\}^n\; X\_i\; >\; c)$.

The constant $c$ can be rewritten as $na$ for some other constant $a$. Then,

:$\backslash mathbb\{P\}(\backslash sum\_\{i\; =\; 1\}^n\; X\_i\; >\; na)\; =\; \backslash mathbb\{E\}\_\{\backslash theta\_a\}\; \backslash left[\backslash exp\backslash \{-\backslash theta\_a\backslash sum\_\{i\; =\; 1\}^n\; X\_i\; +\; n\backslash kappa(\backslash theta\_a)\backslash \}\backslash mathbb\{I\}(\backslash sum\_\{i\; =\; 1\}^n\; X\_i\; >\; na)\; \backslash right]$,

where $\backslash theta\_a$ denotes the $\backslash theta$ defined by the saddle-point equation

:$\backslash kappa\; \text{'}(\backslash theta\_a)\; =\; a$.

Given the tilting of a normal R.V., it is intuitive that the exponential tilting of $X\_t$, a Brownian motion with drift $\backslash mu$ and variance $\backslash sigma^2$, is a Brownian motion with drift $\backslash mu\; +\; \backslash theta\backslash sigma^2$ and variance $\backslash sigma^2$. Thus, any Brownian motion with drift under $\backslash mathbb\{P\}$ can be thought of as a Brownian motion without drift under $\backslash mathbb\{P\}\_\{\backslash theta^*\}$. To observe this, consider the process $X\_t\; =\; B\_t\; +\; \backslash mu\_t$. $f(X\_t)\; =\; f\_\{\backslash theta^*\}(X\_t)\backslash frac\{d\backslash mathbb\{P\}\}\{d\backslash mathbb\{P\}\_\{\backslash theta^*\}\}\; =\; f(B\_t)\backslash exp\backslash \{\backslash mu\; B\_T\; -\; \backslash frac\{1\}\{2\}\backslash mu^2T\backslash \}$. The likelihood ratio term, $\backslash exp\backslash \{\backslash mu\; B\_\{T\}\; -\; \backslash frac\{1\}\{2\}\backslash mu^2\; T\backslash \}$, is a martingale and commonly denoted $M\_T$. Thus, a Brownian motion with drift process (as well as many other continuous processes adapted to the Brownian filtration) is a $\backslash mathbb\{P\}\_\{\backslash theta^*\}$-martingale.{{Cite book|last=Asmussen Soren & Glynn Peter|title=Stochastic Simulation|publisher=Springer|year=2007|isbn=978-0-387-30679-7|pages=407}}{{Cite book|title=Stochastic Calculus and Financial Applications|url=https://archive.org/details/stochasticcalcul00stee|url-access=limited|last=Steele|first=J. Michael|publisher=Springer|year=2001|isbn=978-1-4419-2862-7 |pages=[https://archive.org/details/stochasticcalcul00stee/page/n224 213]–229}}

The above leads to the alternate representation of the stochastic differential equation $dX(t)\; =\; \backslash mu(t)dt\; +\; \backslash sigma(t)\; dB(t)$: $dX\_\{\backslash theta\}(t)\; =\; \backslash mu\_\{\backslash theta\}(t)\; dt\; +\; \backslash sigma(t)\; dB(t)$, where $\backslash mu\_\{\backslash theta\}(t)$ = $\backslash mu(t)\; +\; \backslash theta\backslash sigma(t)$. Girsanov's Formula states the likelihood ratio $\backslash frac\{d\backslash mathbb\{P\}\}\{d\backslash mathbb\{P\}\_\{\backslash theta\}\}\; =\; \backslash exp\backslash \{-\backslash int\backslash limits\_0^T\backslash frac\{\backslash mu\_\{\backslash theta\}(t)\; -\; \backslash mu(t)\}\{\backslash sigma^2(t)\}dB(t)\; +\; \backslash int\backslash limits\_0^T(\backslash frac\{\backslash sigma^2(t)\}\{2\})dt\backslash \}$. Therefore, Girsanov's Formula can be used to implement importance sampling for certain SDEs.

Tilting can also be useful for simulating a process $X(t)$ via rejection sampling of the SDE $dX(t)\; =\; \backslash mu(X(t))dt+\; dB(t)$. We may focus on the SDE since we know that $X(t)$ can be written $\backslash int\backslash limits\_0^t\; dX(t)\; +\; X(0)$. As previously stated, a Brownian motion with drift can be tilted to a Brownian motion without drift. Therefore, we choose $\backslash mathbb\{P\}\_\{proposal\}=\backslash mathbb\{P\}\_\{\backslash theta^*\}$. The likelihood ratio $\backslash frac\{d\backslash mathbb\{P\}\_\{\backslash theta^*\}\}\{d\backslash mathbb\{P\}\}(dX(s):\; 0\; \backslash leq\; s\; \backslash leq\; t)\; =$

$\backslash prod\backslash limits\_\{\backslash tau\backslash geq\; t\}\backslash exp\backslash \{\backslash mu(X(\backslash tau))dX(\backslash tau)\; -\; \backslash frac\{\backslash mu(X(\backslash tau))^2\}\{2\}\backslash \}dt\; =\; \backslash exp\backslash \{\backslash int\backslash limits\_0^t\backslash mu(X(\backslash tau))dX(\backslash tau)\; -\; \backslash int\backslash limits\_0^t\backslash frac\{\backslash mu(X(s))^2\}\{2\}\backslash \}dt$. This likelihood ratio will be denoted $M(t)$. To ensure this is a true likelihood ratio, it must be shown that $\backslash mathbb\{E\}[M(t)]\; =\; 1$. Assuming this condition holds, it can be shown that $f\_\{X(t)\}(y)\; =\; f\_\{X(t)\}^\{\backslash theta^*\}(y)\backslash mathbb\{E\}\_\{\backslash theta\; ^*\}[M(t)|X(t)\; =\; y]$. So, rejection sampling prescribes that one samples from a standard Brownian motion and accept with probability $\backslash frac\{f\_\{X(t)\}(y)\}\{f\_\{X(t)\}^\{\backslash theta\; ^*\}(y)\}\backslash frac\{1\}\{c\}\; =\; \backslash frac\{1\}\{c\}\backslash mathbb\{E\}\_\{\backslash theta\; ^*\}[M(t)|X(t)\; =\; y]$.

Assume i.i.d. X's with light tailed distribution and $\backslash mathbb\{E\}[X]\; >\; 0$. In order to estimate where $\backslash tau(c)\; =\; \backslash inf\backslash \{t:\backslash sum\backslash limits\_\{i=1\}^t\; X\_i>\; c\backslash \}$, when $c$ is large and hence $\backslash psi(c)$ small, the algorithm uses exponential tilting to derive the importance distribution. The algorithm is used in many aspects, such as sequential tests,D. Siegmund (1985) Sequential Analysis. Springer-Verlag G/G/1 queue waiting times, and $\backslash psi$ is used as the probability of ultimate ruin in ruin theory. In this context, it is logical to ensure that . The criterion $\backslash theta\; >\; \backslash theta\_0$, where $\backslash theta\_0$ is s.t. $\backslash kappa\text{'}(\backslash theta\_0)\; =\; 0$ achieves this. Siegmund's algorithm uses $\backslash theta\; =\; \backslash theta^*$, if it exists, where $\backslash theta^*$ is defined in the following way:

$\backslash kappa(\backslash theta^*)\; =\; 0$.

It has been shown that $\backslash theta^*$ is the only tilting parameter producing bounded relative error ().{{Cite book|last=Asmussen Soren & Glynn Peter|first=Peter|title=Stochastic Simulation|publisher=Springer|year=2007|isbn=978-0-387-30679-7|pages=164–167}}

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 $X\_1,\; X\_2,...$be i.i.d. r.v.’s with distribution $G$; for simplicity we assume $X\backslash geq\; 0$. Define $\backslash mathfrak\{F\}\_n\; =\; \backslash sigma(X\_1,...,X\_n,U\_1,...,\; U\_n)$, where $U\_1,\; U\_2$, . . . are independent (0, 1) uniforms. A randomized stopping time for $X\_1,\; X\_2$, . . . is then a stopping time w.r.t. the filtration $\backslash \{\backslash mathfrak\{F\}\_n\backslash \}$, . . . Let further $\backslash mathfrak\{G\}$ be a class of distributions $G$ on $[0,\; \backslash infty)$ with and define $G\_\backslash theta$ by $\backslash frac\{dG\_\backslash theta\}\{dG(x)\}\; =\; e^\{\backslash theta\; x\; -\; k\_G\}$. We define a black-box algorithm for ECM for the given $\backslash theta$ and the given class $\backslash mathfrak\{G\}$of distributions as a pair of a randomized stopping time $\backslash tau$ and an $\backslash mathfrak\{F\}\_\backslash tau-$ measurable r.v. $Z$ such that $Z$ is distributed according to $G\_\backslash theta$ for any $G\; \backslash in\; \backslash mathfrak\{G\}$. Formally, we write this as

simulated values from $G$ and additional uniforms to produce an r.v. from $G\_\backslash theta$.Asmussen, Soren & Glynn, Peter (2007). Stochastic Simulation. Springer. pp. 416–420. {{ISBN|978-0-387-30679-7}}

• Importance sampling
• Rejection sampling
• Monte Carlo method
• Exponential family
• Esscher transform

{{Reflist|30em}}

Category:Sampling techniques