STAT 380

Midterm Examination

Richard Lockhart 20 February 2002

=1=Instructions: This is an open book exam. You may use notes, books and a calculator. The exam is out of 25. Questions 1 and 3 are worth 5 marks each. Each of the 5 parts of question 2 is worth 3 marks. I will be marking for clarity of explanation as well as correctness. Without a clear explanation you should not expect to get more than half marks.

1.

A Markov Chain has state space $\{1,2,3,4\}$ and transition matrix

$$\left[\begin{array}{cccc} \frac{1}{3} & \frac{1}{3} & 0 & \fr... ...frac{1}{4} & 0 & \frac{1}{4} & \frac{1}{2} \end{array}\right]$$

Identify all the communicating classes and say whether or not each is transient. [5 marks]

Solution: Since 2 leads only to 2 one class is $\{2\}$. Similarly 3 leads only to 3 and must be in a class of its own, $\{3\}$. Finally 1 and 4 lead to each other so $\{1,4\}$ is the last class. The classes 2 and 3 are recurrent while $\{1,4\}$ is transient.

2.

Each day I get a random number of pieces of voice mail. I deal with, and delete, a random number of pieces of voice mail. When the mail box gets full any further messages received are lost. Here is a simplified model. Assume that my mail box can hold two messages. Each morning I get either 1 message or 0 messages. Each evening I delete either 1 message or 0 messages. The probability that I get 1 message is p regardless of what has happened in the past. The probability that I delete 1 message is $\pi$ if there is a message to delete. Let X_n be the number of messages on day n in the morning before any message arrives. Assume that X₀=0; day 0 is the starting day.

(a)

Write out the transition matrix of the resulting Markov Chain. [3 marks]

Solution: Clearly P₀₂=P₂₀=0. If you start the morning with no voice mail then you end the day with 1 voice mail if a piece of mail comes and you don't delete it. This makes $P_{01}=p(1-\pi)$. Similarly $P_{12}=p(1-\pi)$. Since the rows must sum to 1 we find $P_{00}=1-p(1-\pi)$. If I start the day with 1 voice mail I will end the day with 0 voice mails provided no voice mail arrives and I delete the one I already have; the probability of this is $(1-p)\pi = P_{10}$. This makes $P_{11} = 1-p(1-\pi)-(1-p)\pi= p\pi+(1-p)(1-\pi)$. Finally: if I start the day with 2 voice mails any arriving voice mail will be discarded so that I will end up at 1 voice mail at the end of the day if I delete a voice mail that day; thus $P_{21}=\pi$. Putting it together get

$${\bf P} = \left[\begin{array}{ccc} 1-p(1-\pi) & p(1-\pi) & 0 ... ...1-p)(1-\pi) & p(1-\pi) \\ 0 & \pi & 1-\pi \end{array}\right]$$

A common mistake will be to think that $P_{21} = (1-p)\pi$. (This is the mistake I made in doing the problem when I made it up; with the mistake in place part c is much easier!)

(b)

Suppose $p=\pi$ and compute the probability that the mailbox is empty in the morning on day 2 (before the arrival of any mail). [3 marks]

Solution: You need

$$\begin{eqnarray*}({\bf }P^2)_{00} & = & P_{00}P_{00}+P_{01}P_{10}+P_{02}P_{20} \... ... \{1-p(1-p)\}^2 + \{p(1-p)\}^2 + 0 \\ & = & 2p^4-4p^3+4p^2-2p+1 \end{eqnarray*}$$

I didn't need to see that last line.

(c)

Again supposing $p=\pi$, show that in the long run the fraction of days on which I lose an email is p/3. [3 marks]

Solution: I made a mistake here. When I created the exam I thought I was making ${\bf P}$ doubly stochastic in which case the stationary initial distribution would be

$$(\alpha_0,\alpha_1,\alpha_2)=(1/3,1/3,1/3)$$

Instead we solve

$$\begin{eqnarray*}\alpha_0 & = & \alpha_0\{1-p(1-p)\}+\alpha_1\{p(1-p)\} \\ \alp... ...{p(1-p)\} + \alpha_2(1-p) \\ 1 & = & \alpha_0+\alpha_1+\alpha_2 \end{eqnarray*}$$

The first equation gives $\alpha_0=\alpha_1$. The second gives $\alpha2= (1-p)\alpha_1$. Thus $(3-p)\alpha_1=1$ or

$$(\alpha_0,\alpha_1,\alpha_2) = \left(\frac{1}{3-p}, \frac{1}{3-p}, \frac{1-p}{3-p}\right)$$

The long run fraction of days I start with the mail box full is (1-p)/(3-p); I lose an email on the fraction p of those days when I get an voice mail so I lose

$$\frac{p(1-p)}{3-p}$$

(d)

Again supposing $p=\pi$, in the long run what fraction of my e-mail will be lost? [3 marks]

Solution: In the first n days I will get about np pieces of voice mail and I will lose about np(1-p)/(3-p) pieces of voice mail. The answer is the ratio which is (1-p)/(3-p). (This answer is not valid for p=0 which corresponds to never getting or deleting voice mail.

(e)

Let T be the number of days till I lose my first e-mail and let m_k be the expected value of T given that I start in state k (for k=0,1,2). Use first step analysis to derive a set of equations which would be solved to compute the m_k. DO NOT SOLVE THE EQUATIONS. [3 marks]

Solution: If you start the day in state 2 there is a chance pthat T=0 because a piece of mail arrives. If no mail arrives and you don't delete any (probability $(1-p)(1-\pi)$) then you have used one day and should still expect to require m₂ days more. If no mail arrives and you delete one piece (probability $\pi(1-p)$) then you have used a day and should expect to wait m₁ more days. Thus

$$m_2 = (1-p) + (1-p)(1-\pi)m_2 +(1-p)\pi m_1$$

If you start the day in state 0 or 1 the situation is easier. You will use your first day and then require m_j more days if you go to state jThus

$$\begin{eqnarray*}m_0 & = & 1+ p(1-\pi)m_1 + \{1-p(1-\pi)\}m_0 \\ m_1 & = & 1+ p... ... \pi(1-p)m_0 \\ m_2 & = & (1-p) + (1-p)(1-\pi)m_2 +(1-p)\pi m_1 \end{eqnarray*}$$

3.

Imagine that buses arrive at a particular stop according to a Poisson process with rate 2 per hour. I start waiting at the stop at 1:00. Given that the second bus arrives between 2:00 and 3:00 what is the probability that the first bus arrived before 2:00? You may leave your answer as a formula--do not bother plugging the numbers into the calculator. [5 marks]

Solution: You are given the information $N(0,2] \ge 2$ and $N(0,1] \le 1$which is the union of two events:

$$A_0 = \{N(0,1]=0\} \cap\{ N(1,2] \ge 2\}$$

and

$$A_1 = \{N(0,1]=1\} \cap\{ N(1,2] \ge 1\}$$

You want
$$\begin{align*}P(N(0,1]\ge 1\vert A_0\cup A_1) & = \frac{P(N(0,1]\ge 1; N(0,1] ... ...a})}{ 1-e^{-\lambda} - 2\lambda e^{-\lambda} +\lambda e^{-\lambda}} \end{align*}$$
Plug in 2 for $\lambda$.