$(2)$ Consider the Markov chain

$($a$)$ Does the Perron$-$Frobenius theorem apply?

$($b$)$ Is the graph strongly connected?

$($c$)$ Define a relation $$ on the set of vertices by saying $vw$ if

$($i$)v=w$ or

$($ii$)$ there is a path from $v$ to $w$ and a path from $w$ to $v.$

Convince yourself $($but do not turn in$)$ that this is an equivalence relation. Write down the equiva$-$

lence classes.

$(3)$ Let $S=\frac{Z}{5}Z-\{\frac{?}{\text{b}\text{a}\text{r}}(0)\}.$ On the board, I have written the element $\frac{?}{\text{b}\text{a}\text{r}}(1)inS.$ At every step, I consider the number

$a$ on the board. If $a$ is a square modulo $5,$ I erase a and replace it with one of the two square roots

$($chosen at random with equal probability$).$ If $a$ is not a square modulo $5,$ I erase a and write $\frac{?}{\text{b}\text{a}\text{r}}(2)*a.$

$($a$)$ Draw a weighted directed graph that models the game.

$($b$)$ Let $A$ be the transition matrix. Use the Perron$-$Frobenius theorem to find $\underset{k}{lim}{A}^k.$

$(4)$ Consider the Markov chain of snakes and ladders where the game ends if we jump to the $100$th square

or beyond. There are no ladders or snakes. In a computer program of your choice, construct the trasition

matrix of this game. Use it to answer the following questions.

$($a$)$ Starting at $0,$ what is the most likely position after $20$ moves.

$($b$)$ After $30$ moves, what is the probability that the game has ended?