

\documentclass[twocolumn]{article}
% \documentclass{article}

\setlength{\oddsidemargin}{-0.5in}
\setlength{\evensidemargin}{-0.5in}
\setlength{\topmargin}{0.0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{7.0in}
\setlength{\textheight}{9.5in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.05in}
\setlength{\columnseprule}{0.3pt}

\setlength\columnsep{25pt}

\usepackage{fancyvrb}
\usepackage{relsize}
\usepackage{hyperref}

\usepackage{listings}
\usepackage{amsmath}

\begin{document}

\lstset{xleftmargin=5mm,framexleftmargin=10mm,basicstyle=\footnotesize}


{\Large \bf GROUP QUIZ SUBMISSION INSTRUCTIONS:}

\begin{itemize}

\item Your work must be submitted by 12 noon, March 12.  Submission must
be done from within the classroom.

\item Submit your work on {\bf handin}, to the directory {\bf 132quiz8}.

\item Your {\bf .tar} file name must conform to the rules explained in our
Syllabus, Section 19.4.  

\item Your {\bf .tar} file must comprise three files, named {\bf
Problem1a.R}, {\bf FindEta.R} and {\bf Problem 2.R}, with contents
as specified below. 

\end{itemize}

My grading script will be 

\begin{lstlisting}
source("Problem1a.R")
whicheqn()
# set p (not shown)
source("FindEta.R")
findeta(p)
source("Problem2.R")
# set c, n, nreps (not shown)
cmp2ests(c,n,nreps)
\end{lstlisting}

You are welcome to search the Web, though my saying this should not be
construed to mean you necessarily would benefit from this.

\bigskip

{\bf 1.}  Consider an $n$-state Markov chain that is {\it irreducible},
meaning that it is possible to get from any state $i$ to any other state
$j$ in some number of steps.  Define the random variable $T_{ij}$ to be
the time needed to go from state $i$ to state $j$.  (Note that $T_{ii}$
is NOT 0, though it can be 1 if $p_{ii} > 0$.)

\begin{equation}
\label{etij}
E(T_{ij}) = \sum_{k} p_{ik} E(T_{ij} ~| W = k), ~~
1 \leq i,j \leq n
\end{equation}

where $W$ is the state traveled to immediately after leaving state $i$.
This then implies that

\begin{equation}
\label{etij1}
E(T_{ij}) 
= 1 + \sum_{k \neq j} p_{ik} E(T_{kj}), ~~
1 \leq i,j \leq n
\end{equation}

We'll focus on the case $j = n$, i.e.\ look at how long it takes to get
to state $n$.  Let $\eta_{i}$ denote $E(T_{in})$, and define  $\eta =
(\eta_1,\eta_2,...,\eta_{n-1})'$.  (Note that $\eta$ has only $n-1$
components!)  So,


\begin{equation}
\label{etij2}
\eta_{i}
= 1 + \sum_{k \neq j} p_{ik} \eta_k, ~~
1 \leq i,j \leq n
\end{equation}

In this problem you'll develop an R function to calculate $\eta$.

Here is a easy (though trivial) example of $\eta$.  Suppose the
transition matrix of the chain is

\begin{equation}
\label{triv}
\left (
\begin{array}{rrr}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
\end{array}
\right )
\end{equation}

Then one can see right away without any computation that

\begin{equation}
\eta = (2,1)'
\end{equation}

\begin{itemize}

\item [(a)] Give the number of our textbook equation that most justifies
(\ref{etij}), among material {\it prior} to Chapter 4.

Your answer will take the form of an R function {\bf whicheqn()} that
consists of a single {\bf print()} call, e.g.

\begin{lstlisting}
print("(2,168)")
\end{lstlisting}

\item [(b)] Using (\ref{etij1}), write an R function with call form

\begin{lstlisting}
findeta(p)
\end{lstlisting}

that inputs the Markov chain's transition matrix {\bf p} and returns
$\eta$.

Hints:  Remember, in (\ref{etij2}) the $p_{ij}$ are the knowns, and the
$\eta_i$ are the unknowns.  Start with a very simple example, say
(\ref{triv}).

\end{itemize}

{\bf 2.}  This problem concerns the raffle example in Section 13.1 of
our book.  We have two competing estimators, and you will write
simulation code to compare them in terms of bias and mean absolute error,

$$
b1 = E(\widehat{c}) -c, ~~~~
b2 = E(\check{c}) -c, ~~~~
$$

$$
e1 = E(|\widehat{c} - c|), ~~~~
e2 = E(|\check{c} - c|) 
$$

Your code will consist of a function with call form

\begin{lstlisting}
cmp2ests(c,n,nreps)
\end{lstlisting}

and will return the (approximate) vector {\bf c(b1,b2,e1,e2)}.  Here
{\bf c} and {\bf n} are as in the raffle example (but are general,
unrelated to the specific data in that example), and {\bf nreps} is our
usual number of ``notebook lines.''  Assume sampling with{\it out}
replacement, even though the theory behind $\check{c}$ is based on
with-replacement sampling.\footnote{Thus assume that $n < c$.}

\onecolumn                                                                      
                                                                                
\newpage                                                                        
                                                                                
{\bf Solutions:}                                                                
                                                                                
{\bf 1a.} (3.154)                                                               
                                                                                
{\bf 1b.}                                                                       
                                                                                
\begin{lstlisting}                                                              
findeta <- function(p) {                                                        
   n <- nrow(p)                                                                 
   q <- diag(n) - p                                                             
   q <- q[1:(n-1),1:(n-1)]                                                      
   ones <- rep(1,n-1)                                                           
   solve(q,ones)                                                                
}                                                                               
\end{lstlisting}                        

{\bf 2.}

\begin{lstlisting}
cmp2ests <- function(c,n,nreps) {
   out <- matrix(nrow=nreps,ncol=2)
   for (i in 1:nreps) {
      x <- sample(1:c,n,replace=FALSE)
      out[i,1] <- 2*mean(x) - 1
      out[i,2] <- max(x)
   }
   c(
      mean(out[,1] - c),
      mean(out[,2] - c),
      mean(abs(out[,1] - c)),
      mean(abs(out[,2] - c)))
}
\end{lstlisting}

\end{document}

> cmp2ests(c,n,nreps)
[1] -0.003373333 -0.613600000  1.744820000  0.613600000

