\documentclass[11pt]{amsart}
\pagestyle{empty}

\addtolength{\hoffset}{-48pt}
\addtolength{\textwidth}{96pt}
\addtolength{\voffset}{-32pt}
\addtolength{\textheight}{45pt}

\usepackage{graphicx}

\newcommand{\RR}{{\mathbb R}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand\ben{\begin{enumerate}}
\newcommand\een{\end{enumerate}}
\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}
\newcommand\vg{\vspace{2ex}}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\ie}{{\it i.e.\ }}
\newcommand{\eg}{{\it e.g.\ }}
\newcommand{\mbf}[1]{{\mathbf #1}}
\newcommand{\bma}{\left[\begin{matrix}}
\newcommand{\ema}{\end{matrix}\right]}   % note alex likes \em as it is!

\begin{document}

Your name:
\vskip 12pt

Instructor (please circle): 
\hspace{1in}
Alex Barnett
\hskip .7in
Naomi Tanabe
\vskip 12pt

{\bf \large Math 22 Fall 2016, Homework 7, due Wed Nov 2}

{\em Please show your work. No credit is given for solutions without work or justification.}

\vskip .05in

\ben

% 7 pts
\item
Consider the matrix %$A = \bma 0& 6\\-1 & 5\ema$.
$A = \bma 1& 1\\1 & 0\ema$, which you should check maps the vector
$\mbf{x}^{(k)}:= \bma f_{k}\\f_{k-1}\ema$
to $\mbf{x}^{(k+1)}:=\bma f_{k+1}\\f_{k}\ema$,
where $\{f_k\}_{k=0}^\infty$ is the Fibonacci sequence 1,1,2,3,5,8,\dots.
\ben
\item Write the matrix in the form $A = P D P^{-1}$ (ie give all three matrices).
%for this factorization).
You (and us) will find it easiest if you express answers using the
{\em golden ratio} $\phi = (1+\sqrt{5})/2$; note $-\phi^{-1} = (1-\sqrt{5})/2$.

\vspace{3in}

\item Use this to write a formula for $\mbf{x}^{(k)}$, for 
the dynamical system with matrix $A$,
%$\mbf{x}^{(k+1)} = A \mbf{x}^{(k)}$,
for the initial vector $\mbf{x}^{(0)} = \bma 1\\0\ema$.
Reading off the first component gives an explicit formula
for the $k$th Fibonacci number! (Isn't it weird that $f_k$ must always be an
integer?)


\vspace{1.5in}

\item To what does $f_{k+1}/f_k$ converge, if anything, as $k\to\infty$,
and why? (explain using your formula).


\een

\newpage %%%%%%%%%%%%%%%%

% 7 pts
\item 
You play the following ``game.'' You start in the library. Every hour
you toss a coin. If in the library, heads you stay in the library,
tails you go party. If you're partying you still toss coins every hour
but continue to party!
\ben
\item Let the ordering be $\mbf{x} = \bma \mbox{probability of being
in the library}\\ \mbox{probability of partying} \ema$.
Write a stochastic matrix $A$ whose Markov chain models the game.

\vspace{1.5in}

\item Derive a formula for the matrix $A^k$.

\vspace{2in}

\item Is the matrix $A$ regular? (no explanation needed)

\vspace{.3in}

\item After $k$ hours (coin tosses),
what is your probability vector $\mbf{x}^{(k)}$ ?

\vspace{1in}

\item For any initial probability vector $\mbf{x}^{(0)}$, does
$\mbf{x}^{(k)}$ converge to a unique steady state as $k\to\infty$, and why?

\vspace{1.5in}

\item Does (e) together with (c) contradict the
convergence theorem for Markov chains? Explain.

\een



\newpage %%%%%%%%%%%%%%%%

% 6 pts
\item
The web consists of three pages. a lints to b. b links to c. c links to
a and b. Use the PageRank algorithm with $\alpha=1$.
\ben
\item Write the stochastic matrix then solve for the vector of
importances (order it abc and normalize so that the vector sums to one).

\vspace{3.5in}


\item In a rather selfish effort to increase its rank (importance score), page a
removes its link to b. [Hint: make sure you understand how the algorithm
deals with such a situation.]
What is the new vector of importances? Did the effort work?

\vspace{3.5in}


\item [BONUS] If the PageRank Markov chain iteration were used to
approximate solutions to (a) and (b), would they converge, and why?

\een

\een

\end{document}
