\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
Michael Musty
\vskip 12pt

{\bf \large Math 22 Summer 2017, Homework 7, due Fri Aug 11}

{\em There is limited space, but please show the key intermediate steps
  to achieve full credit.}

\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,1,\dots$, 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).
  Please use the
  {\em golden ratio} $\phi = (1+\sqrt{5})/2$ for working and answers;
  note $-\phi^{-1} = (1-\sqrt{5})/2$.
  Please also choose the 2nd row of $P$ to be $[1 \;\; 1]$.

\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 wild 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,'' which involves a decisions made on the hour.
  If you are exercising this hour, then for sure the next hour you will
  start studying. If you are studying, then at the end of the hour you
  toss a fair coin: heads you continue studying, tails you switch to exercise.
  (This basic model doesn't include eating or sleeping. Details!)
\ben
\item Let the ordering be $\mbf{x} = \bma \mbox{probability of exercising
}\\ \mbox{probability of studying} \ema$.
Write a stochastic matrix $A$ whose Markov chain models the game.

\vspace{1.5in}

\item Is the matrix $A$ {\em regular}? Explain.

\vspace{.7in}

\item
  Say your initial vector is
  $\mbf{x}^{(0)} = \left[\begin{array}{c}1\\0\end{array}\right]$.
%  Say, initially you are exercising.
  To what, if anything, does your probability of studying tend
  in the long-time limit $k\to\infty$? Explain.

  
\vspace{2.6in}
  
\item
  Prove the claim from class 
  that any stochastic matrix $A$ must have an eigenvalue 1.
  [Hint: find a simple eigenvector of $A^T$.]

    

\een



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

% 6 pts
\item
The web consists of three pages. a links 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 importance score, page a
removes its link to b. (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
  (with $\alpha=1$) was used to
approximate solutions to (a) and (b), would they converge, and why?

\een

\een

\end{document}
