\documentclass[12pt]{article}
\usepackage{graphicx}% Include figure files
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}

\newcommand{\ba}[1]{\begin{array}{#1}}
\newcommand{\ea}{\end{array}}
\newcommand{\arr}[2]{\ba{#1} #2 \ea}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray*}}
\newcommand{\eea}{\end{eqnarray*}}
\newcommand {\no}  {\noindent}
\newcommand{\borel}{\mathcal{B}}
\newcommand{\field}{\mathcal{F}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\ra}{\rightarrow}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\naturals}{\mathbb{N}}

\begin{document}

\centerline {\bf Monte Carlo Methods - Spring 16 - Homework 4 } 

\bigskip

\no 1. (based on problems in Owen) For the nominal density we 
let $p(x)$ be the standard normal density.
We want to use importance sampling to compute the expected value of $f(x)$
with respect to $p(x)$ where $f(x)$ is defined below. 
We  take the sampling density $q(x)$ to be normal with 
variance $1$ and mean $\theta$. 
So 
\bea
q(x,\theta)=\frac{1}{\sqrt{2 \pi}} \exp(-\frac{1}{2}(x-\theta)^2)
\eea

\smallskip
\no (a) Let $f(x)=exp(kx)$. 
Find the optimal $\theta$ where optimal means that it minimizes the variance
of the importance sampling algorithm using $q(x,\theta)$  
Can you do any better with a sampling density that is not of the assumed form?

\smallskip
\no (b) Now let $f(x)=\exp(-(x-10)^2)$. 
Find the optimal $\theta$ for our one parameter family of 
sampling densities. Now consider all possible sampling densities. 
What is the optimal one? How does the variance of the importance sampling 
algorithm for this optimal $q$ compare with the variance of the 
importance sampling algorithm using $q(x,\theta)$ with the optimal 
choice of $\theta$? 

\bigskip

\no 2.  Problem 9.10 in chapter 9 of Owen's notes. 

\bigskip

\no 3. In class we looked at the following example. $Z$ has a standard
normal distribution. We want to compute $P(Z>4)$. We let 
\bea
p(x,\theta)= \frac{1}{\sqrt{2 \pi}} \exp(-\frac{1}{2}(x-\theta)^2)
\eea
so the nominal density $p(x)$ is $p(x,0)$. 

\no (a) Suppose we take $\theta=4$ for our sampling density. 
Using importance sampling, compute (approximately) the probability $P(Z>4)$. 
Find the variance of the estimator and use it to give a 
95\% confidence interval for your answer.

\no (b) Now suppose we want to reduce the variance even further. 
In class I discussed doing a pilot MC run with some reference value 
$\theta_r$ for the sampling $\theta$ and using this single run to 
estimate the variance for other values of $\theta$. Using a 
reference $\theta_r=4$, estimate the variance for other $\theta$ and 
find the optimal choice of $\theta$. 

\bigskip

\no 4. Consider the random walk exit example from section 6.4 in the notes.
In class (and the notes) I took the sampling density to be a random 
walk with steps having a normal density with variance $1$ and mean $\theta$
with $\theta=0$. Now consider sampling densities where the mean of 
the step distribution $\theta$ is a parameter. Find the optimal $\theta$.
It is possible to do this by brute force: for many different values of 
$\theta$ you can do a MC run to estimate the variance. 
But ideally you should be able to estimate the optimal $\theta$ with 
a single MC run.

\end{document}
\end

\no ?. bridge network using beta distributions

