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

\smallskip



\no 1. This problem looks at whether the digits of $\pi$ would make 
a good random number generator, albeit a very impractical one. 
The file pi.txt on the wepage contains the first 100,000 digits of 
$\pi$. Think of the digits as a stream of random numbers taking 
values $0,1,2,\cdots,9$. We want to test the hypothesis that 
the digits are uniformly distributed and independent. 

\smallskip
\no (a) Test the hypothesis that the digits are uniformly distributed with 
a $\chi^2$ test. 

\smallskip
\no (b) Adapt one of the tests we studied for random generators 
to test if the digits are independent. 

\no You can find many more digits on the web if 100,000 is not enough for you.

\medskip

\no 2. There are several examples of random number generators 
in the notes and references to many more. Pick one and test it. 

\medskip

\no 3. Suppose we want to sample the standard normal distribution 
using the density $g(x)=\frac{1}{2} \exp(-|x|)$.
Show that this can be done and find the acceptance fraction. 

\smallskip
\no If you want to compute something, you can generate a bunch of 
samples of the normal with your algorithm and then either plot a histogram 
to if it looks normal or do a Kolmogorov Smirnov test that the samples 
follow a standard normal distribution.

\medskip

\no 4. As remarked in class and in the notes there is an 
acceptance rejection algorithm for discrete random variables. 

\smallskip
\no (a) Suppose we want to sample a discrete random variable $X$
with \\
$P(X=k)=p_k$ for $k=1,2,\cdots, n$. 
For the easy to sample distribution we just use the uniform 
distribution on $1,2,\cdots,n$. 
What is the acceptance rate? What is the worst case for the acceptance rate?
Can you tweak the algorithm to get an acceptance rate that is 
at worst $1/2$?

\smallskip
\no (b) Now consider two discrete distributions where the RV takes on 
an infinite number of values - the geometric distribution and the Poison
distribution. We saw a trick in class that makes it easy to sample
from the geometric distribution (take an exponential RV and round down.)
So we could try to use the geometric distribution and acceptance-rejection
to sample from the Poisson distribution with parameter $\lambda$. 
We need to choose the parameter for the geometric. Suppose we just choose
the geometric parameter $p$ so that its mean equals the mean of the 
Poission. Show that acceptance-rejection sampling is
possible and say what you can about the 
acceptance rate. (I don't think you can compute the acceptance rate
analytically. You will probably have to resort to some numerics.)

\smallskip
\no (c) Suppose that we had a good way to sample from the Poisson distribution
and wanted to use acceptance-rejection to generate samples from the 
geometric. Explain why this will not work.

\medskip

\no 5. Let $(X,Y)$ have joint distribution 
$$ 
f(x,y) = \cases{
(y+1)\exp(1-(x+1)(y+1)),& if $ x,y \ge 0$ \cr
                   0,& otherwise \cr}
$$
So $X$ and $Y$ are non-negative random variables. 
We want to generate samples of $(X,Y)$. 

\smallskip
\no (a) Give an algorithm that uses the conditioning method 
(also sometimes called composition). 

\smallskip
\no (b) Give an acceptance-rejection algorithm that generates samples
of $(X,Y)$. 

\smallskip
\no (c) Implement both of your algorithms and check (somehow) that they 
``agree.'' 



\end{document}
\end
