\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 1} 

\smallskip



\no 1. This is based on an example in the review article by Kroese.
Consider the small network shown in the figure. 

\begin{figure}[tbh]
\includegraphics{network.eps}
\end{figure}

The random variables $T_i$ are the times it takes to traverse that bond. 
The times $T_i$ are uniformly distributed but with different ranges:\\
$T_1$ uniform on $[0,1]$\\
$T_2$ uniform on $[0,2]$\\
$T_3$ uniform on $[0,3]$\\
$T_4$ uniform on $[0,1]$\\
$T_5$ uniform on $[0,2]$\\
We want to find the quickest path from A to B. Let $X$ be the total time
it takes to traverse this quickest path. We want to compute the mean 
$\mu=E[X]$. 

\no (a) Using $N=10,000$ samples, use direct Monte Carlo to estimate $\mu$.
Using your data estimate $\sigma^2$ and find a $95\%$ confidence interval
for your estimate. 
As a check on your simulation, the exact answer is know to be 
$\frac{1339}{1440} \approx 0.92986$.

\no (b) Repeat what you did in (a) 100 times and see how many times your
confidence interval contains the exact value of $\mu$. 

\bigskip

\no 2. (corrected 2/9) 
In class and in the notes I claimed that if you apply the delta method
to find the variance of the estimator $\hat{\theta}=\overline{Y}/\overline{X}$
for $\theta=E[Y]/E[X]$, then the variance of $\hat{\theta}$ is approximately 
\bea
var(\hat{\theta}) \approx 
\frac{1}{n} \frac{\sum_{i=1}^n (Y_i- \hat{\theta} X_i)^2}{n \overline{X}^2}
\eea
where $\overline{X}$ and $\overline{Y}$ are the sample means for $X$ and $Y$ 
and $\hat{\theta}=\overline{Y}/\overline{X}$. 
For the general estimator $\hat{\theta}=f(\hat{\mu}_1, \cdots,\hat{\mu}_d)$
we found from the delta method that the variance is 
$(\hat{\nabla} f, \hat{\Sigma} \hat{\nabla} f)/n$. 
Use this general result to derive the equation above, i.e., show 
\bea
(\hat{\nabla} f, \hat{\Sigma} \hat{\nabla} f)
= \frac{\sum_{i=1}^n (Y_i- \hat{\theta} X_i)^2}{n \overline{X}^2}
\eea

\bigskip

\no 3. Let $X_1,\cdots,X_n$ be our sample. Define
\bea
\overline{X} = \frac{1}{n} \sum_{i=1}^n X_i, \quad
s^2 = \frac{1}{n-1} \sum_{i=1}^n (X_i-\overline{X})^2
\eea
The kurtosis of $X$ is 
\bea
\kappa = \frac{E[(X-\mu)^4]}{\sigma^4}
\eea
For a normal RV the kurtosis is $3$. So $\kappa-3$ is sometimes called
the excess kurtosis. Unfortunately sometimes the excess kurtosis is
just called the kurtosis. In particular Owen does this. 

\no (a) Find the variance of $s^2$ in terms of $\sigma^2$, $\kappa$ and 
$n$. I think the answer is 
\bea
\frac{1}{n}(\kappa \sigma^4 - \frac{n-3}{n-1} \sigma^4)
\eea
This is just a computation and rather tedious. 
You may want to skip this part and just do (b).

\no (b) Define
\bea
\hat{\sigma^2} &=& \frac{1}{n} \sum_{i=1}^n (X_i-\overline{X})^2
\eea
This is just $s^2$ with the $1/(n-1)$ replaced by $1/n$. 
Expanding out the square we can also write this as 
\bea
\hat{\sigma^2} &=& \frac{1}{n} \sum_{i=1}^n X_i^2 - \overline{X}^2
\eea
Now let $Y=X^2$. The variance of $X$ is $E[Y]-E[X]^2$
which is $f(E[X],E[Y])$ where $f(x,y)=y-x^2$. The estimator 
$\hat{\sigma^2}$ is $\overline{Y}-\overline{X}^2=f(\overline{X},\overline{Y})$.
So we can use the delta method to find the variance of $\hat{\sigma^2}$.
Carry out this computation and compare with the result in part (a). 

\end{document}
\end

