% This is a LaTex file.
% Homework for the course "Stochastic Calculus",
% Fall semester, 2004, Jonathan Goodman.
\documentclass[12pt]{article}
% The page format, somewhat wider and taller page than in art12.sty.
\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in \evensidemargin 0in \textwidth 6.5in
\begin{document}
% The title and header.
\noindent
{\scriptsize Stochastic Calculus, Fall 2004
(http://www.math.nyu.edu/faculty/goodman/teaching/StochCalc2004/)} \hfill
\begin{center}
\large
Assignment 3.
\normalsize
\end{center}
\noindent
Given September 16, due September 23. Last revised, September 16.\\
\vspace{.3in}
\noindent
{\bf Objective:} Markov chains, II and lattices.
\vspace{.5cm}
% The questions
\begin{description}
\item[1.] We have a three state Markov chain wih transition matrix
$$
P = \left( \begin{array}{ccc} \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\
\frac{1}{2} & \frac{1}{2} & 0 \\
\frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\
\end{array} \right) \;\; .
$$
(Some of the transition probabilities are
$P(1 \rightarrow 1) = \frac{1}{2}$, $P(3 \rightarrow 1) = \frac{1}{3}$,
and $P(1 \rightarrow 2) = \frac{1}{4}$. Let $\tau = \min(t \mid X_t = 3)$.)
Even though this $\tau$ is not bounded (it could be arbitrarily large),
we will see that $P(\tau > t) \leq C a^t$ for some $a<1$ so that the
probability of large $\tau$ is very small. This is enough to prevent the
stopping time paradox (take my word for it). Suppose that at time $t=1$,
all states are equally likely.
\begin{description}
\item[a.] Consider the quantities $u_t(j) = P(X_t = j \mbox{ and } \tau > t)$.
Find a matrix evolution equation for a two component vector made from
the $u_t(j)$ and a submatrix, $\widetilde{P}$, of $P$.
\item[b.] Solve this equation using the the eigenvectors and
eigenvalues of $\widetilde{P}$ to find a
formula for $m_t = P(\tau = t)$.
\item[c.] Use the answer of part b to find $E[\tau]$. It might be helpful
to use the formula
$$
\sum_{t=1}^{\infty}tP(\tau=t) = \sum_{t=1}^{\infty}P(\tau \geq t) \; .
$$
Verify the formula if you want to use it.
\item[d.] Consider the quantities $f_t(j) = P(\tau \geq t \mid X_1 = j)$.
Find a matrix recurrence for them.
\item[e.] Use the method of question 1 to solve this and find the $f_t$.
\end{description}
\item[2.] Let $P$ be the transition matrix for an $n$ state Markov chain. Let
$v(k)$ be a function of the state $k \in \cal S$. For this problem, suppose
that paths in the Markov chain start at time $t=0$ rather than $t=1$, so that
$X = (X_0, X_1, \ldots)$. For any complex number, $z$, with
$\left|z\right|<1$, consider the sum
\begin{equation}
E\left[ \sum_{t=0}^{\infty} z^t v(X_t) \mid {\cal F}_0 \right] \; .
\end{equation}
Of course, this is a function of $X_0 = k$, which we call $f(k)$.
Find a linear matrix equation for the quantities $f$ that involves
$P$, $z$, and $v$. Hint: the sum
$$
E\left[ \sum_{t=1}^{\infty} z^t v(X_t) \mid {\cal F}_1 \right] \; .
$$
may be related to (1) if we take out the common factor, $z$.
\item[3.] (Change of measure) Let $P$ be the probability measure corresponding
to ordinary random walk with step probabilities $a=b=c=1/3$. Let $Q$
be the measure for the random walk where the up, stay, and down probabilities
from site $x$ depend on $x$ as
$$
\bigl(c(x),b(x),a(x)\bigr) = \frac{1}{3} e^{-\beta(x)}
\left( e^{-\alpha(x)}, 1, e^{\alpha(x)}\right) \; .
$$
We may choose $\alpha(x)$ arbitrarily and then choose $\beta(x)$ so that
$a(x) + b(x) + c(x) = 1$. Taking $\alpha \neq 0$ introduces drift into
the random walk. The state space for walks of length $T$ is the set of
paths $x = x(0), \cdots, x(T)$ through the lattice. Assume that the
probability distribution for $x(0)$ is the same for $P$ and $Q$. Find
a formula for $Q(x)/P(x)$. The answer is a discrete version of Girsanov's
formula.
\item[4.] In the urn process, suppose balls are either {\em stale} or
{\em fresh}. Assume that the process starts with all $n$ stale balls and
that all replacement balls are fresh. Let $\tau$ be the first time
all balls are fresh. Let $X(t)$ be the number of stale balls at time
$t$. Show that $X(t)$ is a Markov chain and write the transition
probabilities. Use the backward or forward equation aproach to calculate
the quantities $a(x) = E_x(\tau)$. This is a two term recurrence relation
($a(x+1) = \mbox{something}\cdot a(x)$) that is easy to solve. Show that
at time $\tau$, the colors of the balls are iid red with probability $p$.
Use this ti explain the binomial formula for the invariant distribution
of colors.
\end{description}
\end{document}