\documentclass[twoside]{article}
\newcommand{\assgnnum}{2}
\newcommand{\duedate}{Thursday, 23 April, 2009}
\newcommand{\SCPDduedate}{Friday, 24 April, 2009}


\usepackage{amsmath}
%\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{bbm}
\usepackage{fancyhdr,lastpage}
\usepackage{paralist}

\oddsidemargin 0in \evensidemargin 0in
\topmargin -0.5in \headheight 0.25in \headsep 0.25in
\textwidth 6.5in \textheight 9in
\parskip 6pt \parindent 0in \footskip 20pt

% set the header up
\fancyhead{} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Put your name in place of the following
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\fancyhead[LE,RO]{CME308: Assignment \assgnnum}
\fancyhead[RE,LO]{Due: \duedate (for regular students) \\Due: \SCPDduedate (for SCPD)}
\renewcommand\headrulewidth{0.4pt}
\setlength\headheight{15pt}
\fancyfoot{}
\fancyfoot[RE,LO]{Prof. Peter Glynn (glynn@stanford.edu)\\ Stanford University}
\fancyfoot[LE,RO]{Page \thepage \: of\: \pageref{LastPage}}

\newcommand{\p}{\ensuremath{\mathbf{P}}}
\renewcommand{\Pr}[1]{\ensuremath{\p \left \{ #1 \right \}}}
\newcommand{\nti}{\ensuremath{n \to \infty}}
\newcommand{\I}{\ensuremath{\operatorname{I}}}
\newcommand{\One}[1]{\ensuremath{\mathbbm{1}_{\left \{ #1 \right \}}}}
\newcommand{\E}{\ensuremath{\mathbf{E}}}
\newcommand{\Ex}[2][]{\ensuremath{\E_{#1} \left[ #2 \right]}}
\newcommand{\var}[1]{\ensuremath{\operatorname{Var}\left( #1\right)}}
\newcommand{\cov}[2]{\ensuremath{\operatorname{Cov}\left( #1, #2\right)}}
\newcommand{\F}{\ensuremath{\mathcal{F}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\NormRV}[2]{\ensuremath{\operatorname{N}\left(#1, #2\right)}}
\newcommand{\BetaRV}[2]{\ensuremath{\operatorname{Beta}\left(#1, #2\right)}}

\newcommand{\eqD}{\ensuremath{\overset{\mathcal{D}}{=}}}

\setlength{\parindent}{0in}

\newcounter{pbctr}
\setcounter{pbctr}{0}
\newenvironment{problem}[1][10]{\refstepcounter{pbctr}\begin{trivlist}
\item {\bf Problem \arabic{pbctr} (#1 pts):\:}}
{\end{trivlist}}

\begin{document}

\pagestyle{fancy}
%\vspace*{15pt} 

{\bf Due Date: } This assignment is due on \duedate (for regular students) and on \SCPDduedate (for SCPD only, please indicate that you are SCPD),
by 5pm in the box outside Durand 112. See the course website for the policy on incentives for \LaTeX{} solutions.

% Problem 1
\begin{problem} Define/explain the following terms or concepts.
\begin{itemize}
	\item Strong Law of Large Numbers
	\item Central Limit Theorem
	\item Confidence Interval
	\item Acceptance-Rejection RV generation
\end{itemize}
\end{problem}
% Problem 2
\begin{problem}
Consider a single-server queue in which customers are served according
to a last in / first out non-preemptive discipline.  When a given
customer completes service, the server begins processing the most
recently arrived customer.  Customers arrive at times 1,3,5,7,11 and
15.  With corresponding service requirements 4,3,1,8 and 2.  How many
customers are in the system at $t = 13.7$?
\end{problem}
% Problem 3
\begin{problem}
\begin{enumerate}
\item A mean zero unit variance random variable $X$ has a
\emph{Laplace} distribution if its p.d.f. is
\[ f(x) = \frac{1}{2} e^{-|x|}. \]
Give an algorithm to generate such random variables.
\item Using the result above, give an algorithm to generate
$\NormRV{\mu}{\sigma^2}$ random variables.
\end{enumerate}
\end{problem}
% Problem 4
\begin{problem}
\begin{enumerate}
\item Suppose that we wish to compute $\alpha = \E{g(W)}$, where
$g$ is a non-negative function and $W$ is a rv having density
$f_W$. If $X$ is a rv having positive density $f_X$, prove that
$\alpha$ can be re-expressed as 
\[\alpha = \E{g(X)\frac{f_W(X)}{f_X(X)}}\]

\item Prove that the variance of the Monte Carlo procedure
associated with the above is minimized by choosing $X$ to have
density 
\[f^*_X(x) = g(x)f_W(x)/\alpha\, .\]

\item Why is the above choice of $f^*_X(\cdot)$ impractical in
general?

\item Suppose that we wish to compute $\alpha = \Pr{N(0,1) >
3.75}$. Compute $\alpha$ first by (crude) Monte Carlo sampling based on
iid sampling of $\One{N(2,1) > 5.75}$, and then compute $\alpha$ via the
approach suggested in 3. with density

\[f_X(x) = \frac{1}{ \sqrt{2\pi}}\exp\left(-(x-5.75)^2/2\right)\]
(i.e. sampling $X$ according to a $N(5.75,1)$ distribution). Produce a
$90\%$ confidence interval based on 10000 and 100000 samples for each
approach. 

\noindent{\bf Remark.} The Monte Carlo approach described
above is called ``importance sampling''.

\end{enumerate}
\end{problem}

\end{document}