\documentclass[twoside]{article}
\newcommand{\assgnnum}{4}
\newcommand{\duedate}{Thursday, 21 May, 2009}

\usepackage{amsmath}
%\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{bbm}
\usepackage{fancyhdr,lastpage}
\usepackage{paralist}
\usepackage{graphicx}
\usepackage[pdftex,colorlinks=true, urlcolor = blue]{hyperref}

\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{} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% UPDATE THIS SECTION FOR YOUR HOMEWORK SUBMISSION %
\fancyhead[LE,RO]{CME308: Assignment \assgnnum} % Put your name here
\fancyhead[RE,LO]{Due: \duedate} %Put the date here, or whatever else you want...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand\headrulewidth{0.4pt}
\setlength\headheight{15pt}

\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]{\refstepcounter{pbctr}\begin{trivlist}
\item {\bf Problem \arabic{pbctr}: {\sc #1}\:}}
{\end{trivlist}}

\begin{document}

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

{\bf Due Date: } This assignment is due on \duedate(with the natural 1 day extension for SCPD students), by 5pm in the box outside Durand 112.  The \LaTeX{} incentive policy is in effect.

%Problem 1
\begin{problem}{} The Smiths receive the paper every morning and place it on a pile
after reading it.  Each afternoon, with probability $1/3$, someone
takes all the papers in the pile and puts them in the recycling bin.
Also, if ever there are at least five papers in the pile, MR. Smith
(with probability 1) takes all the papers to the bin.
\begin{enumerate}
\item This problem can be modeled with a 5 state Markov Chain, where
the states are $\{0,1,2,3,4\}$ corresponding to the number of papers
in the pile in the evening.  What is the corresponding transition
matrix?
\item After a long time, what would be the expected number of papers
in the pile?
\item Assume the pile starts with 0 papers.  What is the expected time
until the pile will again have 0 papers?
\end{enumerate}
\end{problem}

%Problem 2
\begin{problem}{}
Let $G = (V, E)$ be a finite undirected and connected graph. Let $X =
(X_n: n\geq 0)$ be a Markov chain that moves from vertex to vertex by
choosing uniformly among the available edges. Compute the stationary
distribution of this Markov chain (known as ``random walk on the graph
$G$'')
\end{problem}

%Problem 3
\begin{problem}{}
{(Lawler, Problem 1.8)} Consider a simple random walk on the graph
shown in Figure \ref{fig:graph}.  (Recall that a simple random walks
on a graph is the Markov chain which at each time moves to an adjacent
vertex, each adjacent vertex having the same probability.)

\begin{figure}[b]
\centering
\scalebox{0.75}{
\includegraphics{hw4fig.pdf}}
\caption{Graph for Problem 3}
\label{fig:graph}
\end{figure}

\begin{enumerate}
\item In the long run, about how much time is spent in vertex A?
\item Suppose a walker starts in vertex A.  What is the expected
number of steps until the walker returns to A?
\item Suppose a walker starts in vertex C.  What is the expected
number of visits to B before the walker reaches A?
\item Suppose a walkers starts in vertex B.  What is the probability
that the walker reaches A before the walker reaches C?
\item Again, assume the walker starts in C.  What is the expected
number of steps until the walker reaches A?
\end{enumerate}
\end{problem}

%Problem 4
\begin{problem}{}(Bremaud, Problem 3.3.5) A knight moves randomly on a chessboard,
making each admissible move with equal probability, and starting from
a corner.  What is the average time he takes to return to the corner
he started from?
\end{problem}

%Problem 5
\begin{problem}{Choice Theory: Markov Chain Models of Brand Switching}

Suppose for a given product, a consumer has a choice between $m$ competing products, labeled $1,2,\ldots,m$.  Suppose successive purchases by a consumer are modeled as an ergodic Markov chain $\{X_n\}$ with transition matrix $P = \{p_{ij},1\leq i,j,\leq m\}$. 

The diagonal entries of $P$ are measures of consumer loyalty to a brand since $p_{jj}$ measures the tendency of a consumer to repurchase brand $j$ when his last purchase was brand $j$.

Companies are interested in market share.  The market share of a brand $j$ is the percentage of purchases made which are of brand $j$.  Assuming a homogeneous population, the market share of brand $j$ can be evaluated as
\[\lim_{N\rightarrow\infty} N^{-1}\sum_{n=0}^N \One{X_n=j},\]
which we know is just $\pi(j)$, where $\pi$ is the stationary distribution for the chain.
\begin{enumerate}
	\item Consider a simple case.  Suppose $\forall j$, $p_{jj}=1/2$ and $\forall i\ne j$, $p_{ij} = (2(m-1))^{-1}$.  Check that this matrix is doubly stochastic and find its stationary distribution.
	\item Now assume that for $i\ne j$,
	\[p_{ij} = \frac{1-p_{ii}}{m-1},\]
	so that a consumer not choosing his old brand chooses uniformly among the others.  With this simple specification of choice probabilityies, can we see the dependence of market share on consumer loyalty?  Verify
	\[\pi(j) = \frac{(1-p_{jj})^{-1}}{\sum_{k=1}^m (1-p_{kk})^{-1}},\]
	so that $\pi(j)\uparrow 1$ as $p_{jj}\uparrow 1$. (Wolf, 1989)
\end{enumerate}
\end{problem}

%Problem 6
\begin{problem}{Non-Parametric Maximum Likelihood Estimation of Transition Probabilities}

Imagine we have a Markov chain $\{X_n\}$ on the finite state space $\mathbb{S}$  with the number of states $m$ known and the transition $P = (p_{i,j},1\leq i,j\leq m)$ matrix unknown.  We observe the chain during the times $0,1,\ldots,n$ and wish to estimate $P$.

If $x_0,\ldots,x_n$ is the realization of the Markov chain to time $n$, then the likelihood function $L_n(P)$ is given by
\begin{align*} L_n(P) = \p(X_0 & = x_0,\ldots,X_n = x_n)\\
& = \p(X_0 = x_0)p_{x_0,x_1}\cdots p_{x_{n-1},x_n}.\end{align*}
Setting $a_{x_0} = \p(X_0 = x_0)$, the log-likelihood function $\mathcal{L}_n(P) = \log L_n(P)$ is then given by
\begin{align*}\mathcal{L}_n(P) & = \log(a_{x_0}p_{x_0,x_1}\cdots p_{x_{n-1},x_n})\\
& = \log\left(a_{x_0}\prod_{(i,j)\in \mathbb{S}\times\mathbb{S}} p_{i,j}^{N_{i,j}}\right)\\
& = \log a_{x_0} + \sum_{(i,j)\in \mathbb{S}\times\mathbb{S}} N_{i,j} \log p_{i,j},\end{align*}
where 
\[N_{i,j} = \sum_{k=0}^{n-1}\One{X_k = i,X_{k+1}= j}.\]
Define
\[N_i = \sum_{k\in\mathbb{S}} N_{ik}.\]
Show that the maximum likelihood estimator of $P$ is given by
\[\hat{p}_{i,j} = \frac{N_{i,j}}{N_i}.\]
\end{problem}

%Problem 7
\begin{problem}{}
The page-rank algorithm computes the equilibrium distribution of a finite state Markov chain having a transition matrix of the form
\[P = \alpha\Lambda + (1-\alpha)Q,\quad 0<\alpha<1,\]
where $\Lambda$ is a rank-one stochastic matrix having identical positive rows and $Q$ is an arbitrary stochastic matrix.
\begin{enumerate}
	\item Compute the equilibrium distribution $\pi(\alpha)$ of $P$ (in terms of something involving the inverse of a matrix).
	\item How would you compute the sensitivity $\pi'(\alpha)$?
\end{enumerate}
\end{problem}

%Problem 8
\begin{problem}{}
Please visit the following two surveys and fill them out.  At the end of each  survey, a random code will be given to you.  Put those codes as your answer to this problem.  These codes will show us that you did in fact complete the surveys but will not in any way reveal your responses.

\href{http://www.surveymonkey.com/s.aspx?sm=69yOSdoIbs4WIQAXn0sGuA_3d_3d}{Tzu-Wei's Evaluation}

\href{http://www.surveymonkey.com/s.aspx?sm=8Yllz42D0amLcczvPKdPGA_3d_3d}{Alex's Evaluation}
\end{problem}


\end{document}