\chapter{Methodology}
\label{ch:method}


\section{Importance Sampling: The Importance Sampling Estimator}


To estimate $\theta =E[h(X)]$, where X has a probability density function of f(x).  Let $g(\ldots)$ be another pdf with the property that $g(x) \neq 0$ whenever $f(x)\neq 0$.  That is $g$ has the same support as $f$.  Then

\begin{eqnarray}
\theta & = & E[h(x)] = \int h(x)f(x)dx \nonumber
\\
& = & \int h(x) \frac{f(x)}{g(x)}g(x)dx
\end{eqnarray}

Since $g$ is a pdf, then the expectation with respect to $g(\ldots)$ is
\begin{equation}
\theta = E\left[ \frac{h(X)f(X)}{g(X)}\right]
\end{equation}

Using Monte Carlo simulation method generates $n$ samples of $X$ from the density, $f(\ldots)$, and set $\hat{\theta}_n = \sum{h(X)/n}$.  An alternative method is to generate $n$ vales of $X$ from the density, $g(\dot)$, and set
\begin{equation}
\hat{\theta}_{n,is} = \sum_{j=1}^n \frac{h(X_j)f(X_j)}{ng(X_j)}
\end{equation}

then $\hat{\theta}_{n,is}$ is the importance sampling estimator of $\theta$.

\section{Determine the form of the tilted density}

For a scalar $t>0$, define the tilted density as:
\begin{equation}
f_t(x) = \frac{e^{tx}f(x)}{M(t)}, \hspace{.25cm} \textrm{where} \hspace{.25cm} f(x)= \lambda\,e^{\lambda\,x}
\end{equation}

Then 
\begin{eqnarray}
M'(x) & = & \int^{\infty}_0 e^{tx}f(x)dx	\nonumber
\\
& = & \lambda \int^{\infty}_0 e^{tx} e^{\lambda/,x}dx \nonumber
\\
& = & e^{-x(\lambda - t)}dx \nonumber
\\
& = & -\left(\frac{\lambda}{\lambda-t}\right)(0-1) \nonumber
\\
& = & \left(\frac{\lambda}{\lambda-t}\right)
\end{eqnarray}


Therefore, 
\begin{eqnarray}
f_t(x)  & =&  \frac{e^{tx}f(x)}{\left(\frac{\lambda}{\lambda-t}\right)} \nonumber
\\
& =& (\lambda-t) e^{-(\lambda-t)x}
\end{eqnarray}

$f_t(x)$, the tilted density, has a exponential distribution with mean = $\frac{1}{(\lambda-t)}$, or using the recipical form, the intensity of $(\lambda-t)$.

\section{From the tilted density, how to obtain samples}

Will obtain samples by using the inverse transform method.  Generate unform random variables from [0,1] and $X_i$'s from $\frac{1}{(\lambda-t)}\, \log(U)$.

\section{State the optimal amount of tilt $t$ to estimate $\theta$, for a given $a$.}

From the mean of $f_t(x)$ can obtain the $t^{*}$, the optimal amount of tilt.   The mean of $f_t(x)$ is $\frac{1}{(\lambda-t)}$, which is equal to $a$.  Therefore, 
\begin{equation}
t^{*} = \lambda - \left(\frac{1}{a}\right)
\end{equation}

\section{State the expression for $\tilde{\theta_n}$ Monte Carlo estimator that uses these samples.}

By sampling $X_i$'s be from the optimally tilted density, say $f_t^{*}(x)$, the $X_i$'s will have an exponential distribution with mean $\frac{1}{(\lambda-t^{*})}$.

From there, will substitute $t^{*}$.  This will make the $X_i$'s have exponential distribution with mean $a$.    Using the method described above, will generate the $X_i$'s to have a density of $a\log(U)$.

Therefore the expression for , 
\begin{eqnarray}
\tilde{\theta_n} & =&  \frac{\lambda}{n(\lambda-t^{*})} \sum^n_{i=1}I_{[a,\infty)}(x_i)e^{-t^{*}x_i} \nonumber
\\
& =&  \frac{a\,\lambda}{n} \sum^n_{i=1}I_{[a,\infty)}(x_i)e^{-\left(\lambda-\frac{1}{a}\right)x_i}
\end{eqnarray}


\section{Compare the $\tilde{\theta_n}$ with $\hat{\theta_n}$, the classical Monte Carlo estimator that uses samples from $f(x)$ directly.}

From $\hat{\theta_n}$, the classical Monte Carlo estimator, the $X_i$'s have an exponential distribution with mean $\frac{1}{\lambda}$
\begin{equation}
\hat{\theta_n} =  \frac{1}{n} \sum^n_{i=1}I_{[a,\infty)}(x_i)
\end{equation}

