---
author: "Your name here"
title: "Math 365 Exam 1"
output: pdf_document
---

Please answer each problem as clearly and completely as you can.  Do not discuss these problems with other students, or anyone else but me. You may use your textbook, lecture notes, class materials (including those posted on the website), and homework, but do not use other books, the internet, or any materials other than those directly associated with the course.  Please do feel free to ask me questions, either via email or coming by my office.  Show all work to demonstrate that you understand your answer. You may use R for any computations; submit either your R script or pdf knit from your R markdown.

Exam is due Monday February 29 at the beginning of class. Late submissions will be penalized by 10 points per day. You may submit by emailing me your R markdown pdf or as a combination of paper and R work.

## Problem 1 (10pt) 

Suppose a Markov chain with state space $S=\{1,2,3,4,5\}$ has the following transition matrix:

```{r}
P<-matrix(0,5,5)
P[1:2,]<-.2
P[3:4,3:4]<-.5
P[5,5]<-1
P
```

(a) Find the communication classes and label each as recurrent or transient.


(b) Find the probability that the chain eventually ends up in the communication class containing state 3, given that the chain starts in state 1.


## Problem 2 (25pt) 

Suppose an irreducible Markov chain with state space $S=\{A,B,C,D\}$ has the following transition matrix:

```{r}
P<-matrix(0,4,4)
rownames(P)<-c('A','B','C','D')
colnames(P)<-c('A','B','C','D')
P[1:2,3:4]<-.5
P[3:4,]<-.25
P
```

(a) Find the invariant probability vector $\bar{\mathbf{\pi}}$.

(b) Suppose the random walk begins at state A. What is the expected number of steps until the walk returns to state A?

(c) What is the probability of hitting state D before hitting state A if the chain starts at state B?

(d) Suppose the chain begins at state C. What is the expected number of steps until the walker reaches state A?

(e) Suppose the chain begins at state C. What is the expected number of visits to state D before the walker reaches state A?

## Problem 3 (15pt)  

A transition matrix $\mathbf{P}$ is called \emph{doubly stochastic} if the sum over each row equals 1 and the sum over each column also equals 1. If the chain associated with a doubly stochastic transition matrix $\mathbf{P}$ is irreducible and aperiodic and has state space $S=\{1, 2, \dots, M\}$, prove that the invariant probability distribution is given by $\pi(i)=\frac{1}{M}$ for $i=1, 2, \dots, M$.

## Problem 4 (30pt) 

Consider the queueing model in Example 3 of Section 2.1 (pages 44-45). 

#### You may assume $q=\frac{1}{2}$ to simplify the computations.

(a) For which values of $p$ is the chain positive recurrent, null recurrent, or transient?
(b) For the case in which the chain is positive recurrent, find the limiting probability distribution $\pi(x)$.
(c) For the transient case, find $\alpha(x)=\mathbb{P}${$X_n=0$ for some $n\ge0$ | $X_0=x$}. That is, for $z=0$, find the function $\alpha(x)$ satisfying (2.2)-(2.4) on page 49.


## Problem 5 (20pt)  

Consider a population of organisms with the following rule for asexual reproduction: each individual has a probability $q$ of surviving long enough to produce offspring. If an individual does produce offspring, it produces one or two offspring for the next generation with equal probability, after which it dies. Suppose the population starts with 3 individuals.

(a) For which values of $q$ is it guaranteed that the population will eventually die out? Hint: work like a regular branching process, with the values of $p_k$ determined from the given scenario.

(b) If $q=0.7$, what is the probability that the population survives forever?