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

\bigskip

\no 1. Let $X$ be the four points $\{(0,0),(1,0),(0,1),(1,1)\}$. 
We define a probability density on it by 
\bea
f(0,0)=f(1,0)=1/3, \quad f(0,1)=f(1,1)=1/6
\eea
With the above ordering of the four points, 
we can think of this as a row vector $(1/3,1/3,1/6,1/6)$. 
A transition kernel for this state space can be thought 
of as a $4$ by $4$ matrix. 

\no (a) Consider the two stage Gibbs samplers. There are two of them since we 
can first update the second component and then the first component or 
we can first update the first component and then the second component. 
Find the transition matrices for these two algorithms. You should find that 
they are different, but the above row vector is the stationary distribution
for both of them. 

\no (b) Find the transition matrix for the randomized Gibbs sampler.  

\no (c) Find the transition matrix for the ``wrong'' two-stage 
Gibbs sampler discussed in class and the notes. Is the above row vector
the stationary distribution for it?

\medskip

\no 2. Consider the randomized Gibbs sampler for a distribution 
$f(x_1,x_2,\cdots,x_d)$ which is absolutely continuous with respect to 
$d$-dimensional Lebesgue measure. 
State precisely and prove a theorem that says that if the support of 
$f$ is ``thickly'' connected, then the Markov chain is irreducible. 
Hint: mimic what we did to prove irreducibility of the Metropolis-Hastings
algorithm.

\medskip

\no 3. Proposition 3 in chapter 8 of the notes says that for the 
independence sampler if $\pi(x) \le C g(x)$ where $g(x)$ is the proposal 
distribution, then the chain converges geometrically fast in the 
total variation norm. In class we proved this theorem for the case that 
the distribution is continuous with the additional assumption that 
the initial distribution was continuous. Do one (or both!) of the 
following. 

\no (a) Prove that if we start the chain in a single state, then 
the chain still converges geometrically fast in the total variation norm. 

\no (b) Prove the theorem when $\pi(x)$ is a discrete distribution, i.e., 
the state space is discrete. 

\newpage

\no 4. Consider the last example in section 8.4 on the Gibbs sampler. 
Suppose that the $p_i(x)$ are all the same and are Poisson with parameter
$\lambda$. So 
\bea
p_i(x)=e^{-\lambda} \frac{\lambda^x}{x!},\quad for \quad x=0,1,2,\cdots
\eea
Implement the Gibbs sampler discussed in class and use it to compute the 
expected value of $X_1$ when $d=2$ and $m=10$. Note: this can be computed
analytically to check your simulation result.  

\end{document}
\end





\no 5. Want to generate samples of standard normal with a Metropolis-Hasting
algorith. Given $X_n=x$, the proposal distribution is the uniform distribution
on $[x-a,x+a]$ where $a$ is a parameter. 
\bea
q(x,y)=  \cases{
\frac{1}{2a}  & if $|x-y| \le a,$ \cr
0, &if 
$|x-y| > a,$
}
\eea

\no (a) Take $a=1.0$ and take the initial value to be $X_0=0$. 
Plot the trace when we run for ??? time steps. 

\no (b) Take $a=0.001$ and take the initial value to be $X_0=0$. 
Plot the trace when we run for ??? time steps. 

\no (c) Take $a=1.0$ and take the initial value to be $X_0=100$. 
Plot the trace when we run for ??? time steps. 


