%% LyX 1.4.4 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\newenvironment{proof}[1][Proof]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{definition}[1][Definition]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{example}[1][Example]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{remark}[1][Remark]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newcommand{\qed}{\nobreak \ifvmode \relax \else
      \ifdim\lastskip<1.5em \hskip-\lastskip
      \hskip1.5em plus0em minus0.5em \fi \nobreak
      \vrule height0.75em width0.5em depth0.25em\fi}

\usepackage{babel}
\makeatother
\begin{document}

\title{Markov Chains and Applications}


\author{Alexander Volfovsky}

\maketitle
\begin{abstract}
In this paper I provide a quick overview of Stochastic processes and
then quickly delve into a discussion of Markov Chains. There is some
assumed knowledge of basic calculus, probability, and matrix theory.
I build up Markov Chain theory towards a limit theorem. I prove the
Fundamental Theorem of Markov Chains relating the stationary distribution
to the limiting distribution. I then employ this limiting theorem
in a Markov Chain Monte Carlo example.%
\footnote{I would like to thank Prof. Lawler for all of his incites into stochastic
processes during his course on random walks. Also, I would like to
thank Sam Raskin for inspirational conversations when the paper seemed
to be taking unfortunate turns for the worse. The book that is used
in order to find statements of some of the theorems is the reference
guide by Larry Wasserman, \textit{All of Statistics: A Concise Course
in Statistical Inference}. Published by Springer Books in 2004.%
}

\tableofcontents{}\newpage{}
\end{abstract}

\section{Introduction}

In a deterministic world, it is good to know that sometimes randomness
can still occur. A stochastic process is the exact opposite of a deterministic
one, and is a random process that can have multiple outcomes as time
progresses. This means that if we know an initial condition for the
process and the function by which it is defined, we can speak of likely
outcomes of the process. One of the most commonly discussed stochastic
processes is the Markov chain. Section \ref{sec:Markov-Chains} defines
Markov chains and goes through their main properties as well as some
interesting examples of the actions that can be performed with Markov
chains. The conclusion of this section is the proof of a fundamental
central limit theorem for Markov chains. We conclude the dicussion
in this paper by drawing on an important aspect of Markov chains:
the Markov chain Monte Carlo (MCMC) methods of integration. While
we provide an overview of several commonly used algorithms that fall
under the title of MCMC, Section \ref{sec:MCMC} employs importance
sampling in order to demonstrate the power of MCMC.


\section{Markov Chains\label{sec:Markov-Chains}}

Markov chains are stochastic processes that have the Markov Property,
named after Russian mathematician Andrey Markov. 

\begin{definition}[Definition of Markov Property]Informally it is
the condition that given a state, the past and future states are independent
of it. Formally we can define it as follows:\[
\mathbb{P}\left(X_{n}=x|X_{0},\dots,X_{n-1}\right)=\mathbb{P}\left(X_{n}=x|X_{n-1}\right)\,\forall n\forall x.\]
\end{definition}

We now present some important theorems and lemmas regarding Markov
Chains. 


\subsection{Theorems and lemmas}

First some notation: $P$ always represents a transition matrix, while
$p_{ij}$ represents an element of it. $X_{j}$ is always a random
variable.

\begin{definition}State $i$ is recurrent if \[
\mathbb{P}\left(X_{n}=i\,\mbox{for some}\, n\geq1|X_{0}=i\right)=1.\]
 Otherwise it is transient.\end{definition}

\begin{definition}A chain is irreducible if every state can be reached
from any other one. That is $p_{ij}\left(1\right)>0\,\forall i,j$
\end{definition}\newpage{}

We state without proof the following results:

A state is recurrent if and only if $\sum_{n}p_{ii}\left(n\right)=\infty$
and it is transient if and only if $\sum_{n}p_{ii}\left(n\right)<\infty.$%
\footnote{I hope that at this point the reader realizes a fundamental truth
about transient states (as it becomes relevant soon). We have that
given a nonzero probability $p$ of returning to transient state $i$
after starting from it, the distribution of the number of times that
we return to that state is geometric. This requires only a little
justification in one's mind. %
}

We delve right in with a lemma that connects the notions of reccurence
and irreducibility.

\label{lem:irred}\begin{lemma}In an irreducible chain, all the states
are either transient or recurrent.\end{lemma}

\begin{proof}We take the shortest path from state $i$ to state $j$
(let it have $n$ steps), and the shortest path from $j$ to $i$
(let it have $m$ steps). Thus we have $p_{ij}\left(n\right)=a>0$
and $p_{ji}\left(m\right)=b>0$ and so we have\begin{eqnarray*}
p_{ii}\left(l+n+m\right) & \geq & p_{ij}\left(n\right)p_{jj}\left(l\right)p_{ji}\left(m\right)\\
 & = & abp_{jj}\left(l\right)\\
p_{jj}\left(l+n+m\right) & \geq & p_{ji}\left(m\right)p_{ii}\left(l\right)p_{ij}\left(n\right)\\
 & = & abp_{ii}\left(l\right).\end{eqnarray*}
So it is obvious that either $\sum_{n}p_{ii}\left(n\right)$ and $\sum_{n}p_{jj}\left(n\right)$
are both finite or are both infinite. Thus from the above results
we note that all the states of an irreducible chain are either transient
or recurrent, as desired.\end{proof}

\label{lem:rec}\begin{lemma}Facts about reccurrence.

\begin{enumerate}
\item If state $i$ is recurrent and $i\leftrightarrow j$, then $j$ is
reccurent.
\item If state $i$ is transient and $i\leftrightarrow j$, then $j$ is
transient.
\item The states of a finite, irreducible Markov chain are all recurrent.
\end{enumerate}
\end{lemma}\begin{proof}

\begin{enumerate}
\item We employ the definition of reccurrence. Thus $\exists n,m\geq0$
st $p_{ij}\left(n\right)>0$ and $p_{ji}\left(m\right)>0.$ Thus we
have\begin{eqnarray*}
\sum_{l=1}^{\infty}p_{jj}\left(l\right) & \geq & \sum_{l=n+m+1}^{\infty}p_{jj}\left(l\right)\\
 & \geq & \sum_{k=1}^{\infty}p_{ji}\left(m\right)p_{ii}\left(k\right)p_{ij}\left(n\right)\\
 & = & p_{ji}\left(m\right)\left(\sum_{k=1}^{\infty}p_{ii}\left(k\right)\right)p_{ij}\left(n\right)\\
 & = & \infty\end{eqnarray*}
where the last part follows from the recurrence of $i$. 
\item We apply similar logic as above. Since $i\leftrightarrow j\,\exists n>0$
st $p_{ij}\left(n\right)>0$ so for $m>n$ we have $p_{ii}\left(m\right)\geq p_{ij}\left(n\right)p_{ji}\left(m-n\right)$
and thus we have:\begin{eqnarray*}
\sum_{k=1}^{\infty}p_{ii}\left(k\right) & \geq & \sum_{k=n+1}^{\infty}p_{ii}\left(k\right)\\
 & \geq & p_{ij}\left(n\right)\left(\sum_{k=n+1}^{\infty}p_{ji}\left(k-n\right)\right)\\
 & = & p_{ij}\left(n\right)\left(\sum_{l=1}^{\infty}p_{ji}\left(l\right)\right)\end{eqnarray*}
which implies that $\sum_{l=1}^{\infty}p_{ji}\left(l\right)\leq\frac{1}{p_{ij}\left(n\right)}\left(\sum_{l=1}^{\infty}p_{ji}\left(l\right)\right)<\infty$
as desired.
\item We know from Lemma \ref{lem:irred} that since the chain is irreducible,
all the states are either recurrent or transient. First assume that
all states are transient. Now, fix a state $i$ and consider the number
of times that we pass state $j$ after starting at $i$. Since we
only have finitely many states, the expectation for the number of
times that we pass state $j$ for some state $j$ would be infinite.
So this implies that the expected number of returns to state $j$
after starting at state $j$ would also be infinite. But that contradicts
the geometric distribution of the number of returns, which has the
expectation be at one over the probability of returning.
\end{enumerate}
\end{proof}

\begin{definition}Mean recurrence time for a recurrent state $i$
is $m_{i}=\sum_{n}nf_{ii}\left(n\right)$ where $f_{ii}\left(n\right)$
is the probability of getting from $i$ to $i$ in exactly $n$ steps.
A state is null recurrent if $m_{i}=\infty$ and non-null otherwise.\end{definition}

We should note that we used exactly this value in the proof of (3)
in lemma \ref{lem:rec} so the above result can easily be extended
to the fact that a finite state Markov chain has all its recurrent
states be non-null.

\begin{definition}The period of state $i$, $d\left(i\right)=d$
if $p_{ii}\left(n\right)=0$ for $d\nmid n$ and $d=\gcd\left\{ n|p_{ii}\left(n\right)>0\right\} .$
Thus a state is periodic if $d\left(i\right)>1$ and aperiodic otherwise.
\end{definition}

\begin{definition}For $\pi_{i}=\lim_{n\rightarrow\infty}p_{ij}\left(n\times d\left(i\right)\right)$,
if greater than zero then non-null recurrent otherwise, null recurrent.\end{definition}

\begin{lemma}If $i\leftrightarrow j$ then $d\left(i\right)=d\left(j\right)$\end{lemma}

\begin{proof}We consider $m,n$ st $p_{ij}\left(n\right)>0$ and
$p_{ji}\left(m\right)>0$ thus we can note that from the Kolmogorov
Chapman equations we have %
\footnote{The proof of the Kolmogorov Chapman Equations is provided in the Appendix%
}\[
p_{ii}\left(m+n\right)=\sum_{k=1}^{N}p_{ik}\left(n\right)p_{ki}\left(m\right)\geq p_{ij}\left(n\right)p_{ji}\left(m\right).\]
Now by definition $p_{ii}\left(n+m\right)>0$ and $d\left(i\right)|\left(n+m\right)$.
Now we can consider $p_{ii}\left(m+l+n\right)$ and apply the same
reasoning as above to arrive at: \begin{eqnarray*}
p_{ii}\left(m+l+n\right) & = & \sum_{k=1}^{N}p_{ir}\left(n\right)\sum_{t=1}^{N}p_{rk}\left(l\right)p_{ki}\left(m\right)\\
 & \geq & p_{ij}\left(n\right)p_{jj}\left(l\right)p_{ji}\left(m\right)\end{eqnarray*}
So if we have that $p_{jj}\left(l\right)>0$ then $d\left(j\right)|l$
implying as desired that $p_{ii}\left(m+l+n\right)>0$ and so $d\left(i\right)|\left(n+m+l\right)$
but combining this with $d\left(i\right)|\left(m+n\right)$ we get
that $d\left(i\right)|l$ and so since $d\left(j\right)=\gcd\left\{ l|p_{jj}\left(l\right)>0\right\} $
we get that $d\left(j\right)\geq d\left(i\right).$ We can apply the
same logic going from $j$ to $i$ and so we arrive at the conclusion
that $d\left(i\right)=d\left(j\right)$ as desired.\end{proof}

\begin{definition}A chain is ergodic if all of its states are non-null
recurent and aperiodic.\end{definition}

\begin{definition}Let $\pi$ be a probability mass function, then
we say that $\pi$ is a stationary probability distribution if $\pi=\pi P$
(that is, if $\pi$is an eighenvector of the transition probability
matrix $P$)\end{definition}

\begin{definition}A limiting distribution exists if $P^{n}\rightarrow\left[\begin{array}{c}
\pi\\
\vdots\\
\pi\end{array}\right]$ for some $\pi$\end{definition}

\begin{theorem}[Fundamental theorem for Markov Chains]An irreducible,
ergodic Markov chain has a unique stationary distribution $\pi$.
The limiting distribution exists and is equal to $\pi.$ \end{theorem}

\begin{proof}Since the chain is ergodic, it is non-null recurrent
which implies from above that $\pi_{j}=\lim_{n\rightarrow\infty}p_{ij}\left(n\right)>0\,\forall i$
and $\sum\pi_{j}=1.$ Now we consident for any $M$ $\sum_{i=0}^{M}p_{ij}\left(n\right)\leq\sum_{i=0}^{\infty}p_{ij}\left(n\right)=1$.
Now, letting $n\rightarrow\infty$ we get that $\sum_{i=0}^{M}\pi_{i}\leq1\,\forall M$
which implies from above that the same is true for the inifinte case
$\sum_{i=0}^{\infty}\pi_{i}\leq1.$ Now we consider the probability
of moving from $i$ to $j$ in $n+1$ steps so $p_{ij}\left(n+1\right)=\sum_{k=0}^{\infty}p_{ik}\left(n\right)p_{kj}\geq\sum_{k=0}^{M}p_{ik}\left(n\right)p_{kj}\,\forall M.$
Now we again can let $n\rightarrow\infty$ which implies that $\pi_{i}\geq\sum_{k=0}^{M}\pi_{k}p_{kj}\,\forall M$
which implies that $\pi_{i}\geq\sum_{k=0}^{\infty}\pi_{k}p_{kj}$.
Now we assume the inequality is strict for some $i$ which leads to
the following contradiction: \begin{eqnarray*}
\sum_{i=0}^{\infty}\pi_{i} & \geq & \sum_{i=0}^{\infty}\sum_{k=0}^{\infty}\pi_{k}p_{ki}\\
 & = & \sum_{k=0}^{\infty}\pi_{k}\sum_{i=0}^{\infty}p_{ki}\\
 & = & \sum_{k=0}^{\infty}\pi_{k}.\end{eqnarray*}
Thus we come to the conclusion that $\pi_{i}=\sum_{k=0}^{\infty}\pi_{k}p_{ki}\,\forall i$.
Now we can consider $\tilde{\pi}_{i}=\pi_{i}/\sum_{k=0}^{\infty}\pi_{k}$
to be a stationary distribution. So we have shown existence. Now to
show uniqueness we consider the following: \[
\tilde{\pi}_{i}=\mathbb{P}\left(X_{n}=i\right)=\sum_{j=0}^{\infty}\mathbb{P}\left(X_{n}=i|X_{0}=j\right)\mathbb{P}\left(X_{0}=j\right)=\sum_{j=0}^{\infty}p_{ji}\left(n\right)\tilde{\pi}_{j}.\]
So we have that $\tilde{\pi}_{i}\geq\sum_{j=0}^{M}p_{ji}\left(n\right)\tilde{\pi}_{j}$and
taking $M,n\rightarrow\infty$ we get that $\tilde{\pi}_{i}\geq\sum_{j=0}^{\infty}\tilde{\pi}_{j}\pi_{i}=\pi_{i}$
but we know that from the transition matrix that $p_{ji}\left(n\right)\leq1$
and so $\tilde{\pi}_{i}\leq\sum_{j=0}^{M}p_{ji}\left(n\right)\tilde{\pi}_{j}+\sum_{j=M+1}^{\infty}\tilde{\pi}_{j}\,\forall M$
and so taking $n\rightarrow\infty$we get $\tilde{\pi}_{i}\leq\sum_{j=0}^{M}\pi_{i}\tilde{\pi}_{j}+\sum_{j=M+1}^{\infty}\tilde{\pi}_{j}\,\forall M.$
Now we know that $\tilde{\pi}$is a stationary distribution so it
sums up to $1$, and so we let $M\rightarrow\infty$ and we get $\tilde{\pi}_{i}\leq\sum_{j=0}^{\infty}\pi_{i}\tilde{\pi}_{j}=\pi_{i}$
which implies that the stationary distribution is unique. 

The above process thus shows the existence of a limiting distribution
and so we now know that an ergodic chain converges to its stationary
distribution.

\end{proof}

This proof allows us to take any bounded function $g$ and say with
probability $1$ that \[
\lim_{N\rightarrow\infty}\frac{1}{N}\sum_{n=1}^{N}g\left(X_{n}\right)\rightarrow E_{\pi}\left(g\right)\equiv\sum_{j}g\left(j\right)\pi_{j}\]
 which is a very strong result that we use constantly in Markov chain
Monte Carlo. 

We conclude this section of lemmas and theorems with a useful definition
and a small lemma.

\begin{definition}$\pi$ satisfies detailed balance if $\pi_{i}p_{ij}=p_{ji}\pi_{j}$\end{definition}

\begin{lemma}If $\pi$ satisfies detailed balance then it is a stationary
distribution.\end{lemma}

\begin{proof}We consider the $j^{th}$ element of $\pi P$ which
is $\sum_{i}\pi_{i}p_{ij}=\sum_{i}\pi_{j}p_{ji}=\pi_{j}\sum_{i}p_{ji}=\pi_{j}$
as desired.\end{proof}


\subsection{Applications}

In this section I provide a few basic examples of Markov chains to
illustrate the points made above. All the examples come from Chapter
23 of Larry Wasserman's book (provided there as exercises rather than
as solved examples).

\begin{example}Consider a two-state Markov chain with state $\chi=\left\{ 1,2\right\} $
and transition matrix\[
P=\left[\begin{array}{cc}
1-a & a\\
b & 1-b\end{array}\right]\]
where $0<a,b<1$. Prove that \[
\lim_{n\rightarrow\infty}P^{n}=\left[\begin{array}{cc}
\frac{b}{a+b} & \frac{a}{a+b}\\
\frac{b}{a+b} & \frac{a}{a+b}\end{array}\right].\]
\end{example}

\begin{example}[Solution]To verify this we need to first show that
the chain is irreducible and ergodic. Irreducible is easy since all
states communicate with nonzero probabilities. To show that it is
ergodic we need to show that all states are reccurent, non-null and
aperiodic. Since $p_{ii}\left(1\right)>0$ we have that this chain
is aperiodic. Now at time $n$ we must be at some location so $\sum_{j\in S}p_{ij}\left(n\right)=1$
for any $i$. Since this is true for every $n$ we can take the limit
as $n\rightarrow\infty$ to get $\lim_{n\rightarrow\infty}\sum_{j\in S}p_{ij}\left(n\right)=1$
but in our case $S$ is finite so we can move the limit under the
sum. Now, if every state in our MC is transient or null reccurent
we would have that $\lim_{n\rightarrow\infty}p_{ij}\left(n\right)=0$
thus contradicting the above statement, so at least one state must
be positive reccurent. Now, since we are in a finite state MC we have
that all states are positive reccurent (due to question (7) below)
since all the states communicate. Thus it is clear that our state
is irreducible and ergodic and so it has a unique stationary distribution.
Now we can solve:\begin{eqnarray*}
\left[\begin{array}{cc}
\pi_{1} & \pi_{2}\end{array}\right]\left[\begin{array}{cc}
1-a & a\\
b & 1-b\end{array}\right] & = & \left[\begin{array}{cc}
\pi_{1}\left(1-a\right)+\pi_{2}b & \pi_{1}a+\pi_{2}\left(1-b\right)\end{array}\right]\end{eqnarray*}
and now we can solve this system of equations with the added restriction
$\pi_{1}+\pi_{2}=1.$ So we get \[
\left[\begin{array}{cc}
\pi_{1} & \pi_{2}\end{array}\right]=\left[\begin{array}{cc}
\frac{b}{a+b} & \frac{a}{a+b}\end{array}\right]\]
as desired. And now we can easily note that the limiting distribution
is $\lim_{n}P^{n}=\left[\begin{array}{c}
\pi\\
\pi\end{array}\right]$ as desired.\end{example}

\begin{example}Let\[
P=\left[\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right]\]
Show that $\pi=\left(0.5,0.5\right)$is a stationary distribution.
Does this chain converge?\end{example}

\begin{example}[Solution]All we are asked to show is that $\pi=\left[\begin{array}{cc}
0.5 & 0.5\end{array}\right]$ is a stationary distribution so:\begin{eqnarray*}
\left[\begin{array}{cc}
0.5 & 0.5\end{array}\right]\left[\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right] & = & \left[\begin{array}{cc}
0+0.5 & 0.5+0\end{array}\right]\\
 & = & \left[\begin{array}{cc}
0.5 & 0.5\end{array}\right]\end{eqnarray*}
as desired. However, the chain does not converge as it is clear that
if we start with $\pi$ we will have an equal probability of being
in either state. This means that the period of each of the states
is 2 and so the chain does not converge.\end{example}


\section{Markov Chain Monte Carlo\label{sec:MCMC}}

Markov chain Monte Carlo integration is a method for integrating function
that might not have a closed form using estimation. 

We demonstrate a very basic example of MCMC processes through Importance
Sampling. Importance sampling is used in statistics as a variance
reduction method. While the standard method that we describe below
does not necessarily optimize the variance, we will state the condition
for minimal variance. Importance sampling allows us to estimate the
distribution of a random variable using a different random variable.
The idea behind the process is that during the simulation, due to
weighing of the random variable from which we have the observations,
we get a better, less biased idea of the parameter we are estimating.
Thus the choice of the weight is very important. We will not go through
the derivation of the {}``best'' (in terms of minimizing the variance)
weight, but just state the result here. 

In an importance sampling problem we are trying to estimate the distribution
of $I$ using $\hat{I}=\frac{1}{N}\sum\frac{h\left(X_{i}\right)f\left(X_{i}\right)}{g\left(X_{i}\right)}.$The
optimal choise of $g$ in this case is $g\left(x\right)=\frac{\left|h\left(x\right)\right|f\left(x\right)}{\int\left|h\left(s\right)\right|f\left(s\right)ds}$. 

The problem is from Larry Wasserman's All of Statistics: A Concise
Course in Statistical Inference.


\subsection{Statement}

(From Larry Wasserman's All of Statistics, 24.7.2)

Let $f_{X,Y}\left(x,y\right)$be a bivariate density and let $\left(X_{1},Y_{1}\right),\dots,\left(X_{N},Y_{N}\right)\sim f_{X,Y}.$

\begin{enumerate}
\item Let $w\left(x\right)$ be an arbitrary probability density function.
Let \[
\hat{f}_{X}\left(x\right)=\frac{1}{N}\sum_{i=1}^{N}\frac{f_{X,Y}\left(x,Y_{i}\right)w\left(x\right)}{f_{X,Y}\left(X_{i},Y_{i}\right)}.\]
Show that, for each $x$, $\hat{f}_{X}\left(x\right)\overset{p}{\rightarrow}f_{X}\left(x\right).$
Find an expression for the variance.
\item Let $Y\sim N\left(0,1\right)$ and $X|Y=y\sim N\left(y,1+y^{2}\right).$
Use the method in $(1)$ to estimate $f_{X}\left(x\right).$
\end{enumerate}

\subsection{Solution}

\begin{enumerate}
\item We consider each part of the sum to be its own random variable, and
we note that they are all identically and independently distributed.
Due to this we can consider just one of them for the following:\begin{eqnarray*}
E\left[\frac{f_{X,Y}\left(x,Y_{i}\right)w\left(x\right)}{f_{X,Y}\left(X_{i},Y_{i}\right)}\right] & = & \int\frac{f_{X,Y}\left(x,y\right)w\left(z\right)}{f_{X,Y}\left(z,y\right)}f_{X,Y}\left(z,y\right)dzdy\\
 & = & \int f_{X,Y}\left(x,y\right)w\left(z\right)dzdy\\
 & = & \int f_{X,Y}\left(x,y\right)dy\\
 & = & f_{X}\left(x\right)\end{eqnarray*}
and so we can apply the law of large numbers to note that \begin{eqnarray*}
\frac{1}{N}\sum_{i=1}^{N}\frac{f_{X,Y}\left(x,Y_{i}\right)w\left(x\right)}{f_{X,Y}\left(X_{i},Y_{i}\right)} & \overset{p}{\rightarrow} & E\left[\frac{f_{X,Y}\left(x,Y_{i}\right)w\left(x\right)}{f_{X,Y}\left(X_{i},Y_{i}\right)}\right]\end{eqnarray*}
which is the same as $\hat{f}_{X}\left(x\right)\overset{p}{\rightarrow}f_{X}\left(x\right),$
as desired.


The variance calculation is fairly simple and we do not dwell on it,
providing simply the easily verifiable answer:\begin{eqnarray*}
\mbox{var}\hat{f}_{X}\left(x\right) & = & \frac{1}{N}\left[\int\frac{f_{X,Y}^{2}\left(x,y\right)w^{2}\left(z\right)}{f_{X,Y}\left(z,y\right)}dzdy-f_{X}^{2}\left(x\right)\right].\end{eqnarray*}


\item We note that the marginal density of $X$ is hard to evaluate:\begin{eqnarray*}
f_{X}\left(x\right) & = & \int f_{X|Y}\left(x\right)f_{Y}\left(y\right)dy\\
 & = & \int\frac{1}{\sqrt{2\pi\left(1+y^{2}\right)}}e^{-\frac{\left(x-y\right)^{2}}{2\left(1+y^{2}\right)}}\frac{1}{\sqrt{2\pi}}e^{-\frac{y^{2}}{2}}dy.\end{eqnarray*}
Thus it makes sense to employ importance sampling as in $(1)$ in
order to estimate $f_{X}\left(x\right).$ So we take the distribution
of $w\left(x\right)$ to be the Standard Normal as it seems like a
reasonable one in this case. So we have:\begin{eqnarray*}
\hat{f}_{X}\left(x\right) & = & \frac{1}{N}\sum_{i=1}^{N}\frac{f_{X,Y}\left(x,Y_{i}\right)w\left(x\right)}{f_{X,Y}\left(X_{i},Y_{i}\right)}\\
 & = & \frac{1}{N}\sum_{i=1}^{N}\frac{f_{X|Y}\left(x|Y_{i}\right)w\left(X_{i}\right)}{f_{X|Y}\left(X|Y_{i}\right)}\\
 & = & \frac{1}{N}\sum_{i=1}^{N}\frac{1}{\sqrt{2\pi}}\exp\left\{ -\frac{1}{2\left(1+y^{2}\right)}\left[\left(x-Y_{i}\right)^{2}-\left(X_{i}-Y_{i}\right)^{2}+\left(x\left(1+y^{2}\right)\right)^{2}\right]\right\} \end{eqnarray*}
using the above knowledge.
\end{enumerate}

\subsection{Further Discussion}

We see above a very basic application of Markov chain Monte Carlo
methods which allows us to use a biased sampling distribution in order
to estimate a random variable of interest. The above discussed method
is a very basic and introductory one. We actually have multiple possible
algorithms that we can apply in order to arrive at the best possible
estimate, however they are a topic for another paper and will only
be briefly mentioned here. 

The most commonly used algorithms for MCMC are the Metropolis Hastings
algorithms which use a conditional proposal distribution in order
to construct a Markov chain with a stationary distribution $f.$ It
supposes that $X_{0}$ was chosen arbitrarily and then proceeds to
use the proposal distribution in order to generate candidates that
are either added to the chain or are overlooked based on a specified
probability distribution.%
\footnote{For basic Metropolis-Hastings, we have the probability be $r\left(x,y\right)=\min\left\{ \frac{f\left(y\right)}{f\left(x\right)}\frac{q\left(x|y\right)}{q\left(y|x\right)},1\right\} $where
$q$ is the proposal distribution. In the case that we have, we can
easily choose a $q$ such that $q\left(x|y\right)=q\left(y|x\right)$
so obviously one part of the multiplication cancels out. %
} There are several different incarnations of this algorithm, with
different suggested proposal distributions: the random-walk M-H algorithm
is the one that was described above (as if we do not accept or reject
the generated value, all we are doing is simulating a random walk
on the real line). In independence M-H we change the proposal distribution
to a fixed distribution which we believe to be an approximation of
$f.$

Another method that gets a lot of use is the Gibbs sampling algorithm
which is simply an emblishment of the M-H algorithm. What this method
does is take a multi-dimensional problem and turns it into several
one-dimensional problems that can be easily estimated using the above
method. So instead of simply getting $X_{i+1}$, Gibbs sampling allows
for the estimation of $\left(X_{i+1}^{\left(1\right)},\dots,X_{i+1}^{\left(n\right)}\right)$for
an $n$-dimensional model.

This process works due to detailed balance of Markov Chains, which
was briefly mentioned in the previos section. For further information
consult Wasserman's book.\newpage{}


\section{Appendix}

\begin{theorem}Chapman Kolmogorov Equations. The n-step probabilities
satisfy\[
p_{ij}\left(n+m\right)=\sum_{k}p_{ik}\left(m\right)p_{kj}\left(n\right).\]
 (We thus get $P_{m+n}=P_{m}P_{n}$ which is standard matrix multiplication)\end{theorem}

\begin{proof}We employ the law of conditional probability and the
law of total probability to arrive at the following:\begin{eqnarray*}
p_{ij}\left(m+n\right) & = & P\left(X_{m+n}=j|X_{0}=i\right)\\
 & = & \sum_{k}P\left(X_{m+n}=j,X_{m}=k|X_{0}=i\right)\\
 & = & \sum_{k}P\left(X_{m+n}=j|X_{m}=k,X_{0}=i\right)P\left(X_{m}=k|X_{0}=i\right)\\
 & = & \sum_{k}P\left(X_{m+n}=j|X_{m}=k\right)P\left(X_{m}=k|X_{0}=i\right)\\
 & = & \sum_{k}p_{ik}\left(m\right)p_{kj}\left(n\right)\end{eqnarray*}
by definition, as desired.\end{proof}
\end{document}
