1. A discrete-time Markov chain X = (Xn )n>0 has state space I = {A, B, C}, one-step

transition matrix

P =  ╱

1/2

0

1/3

0

5/12(5/6)、

1/2 ．  ,

and initial distribution P(X0  = i) = ωi  for i ∈ I, where ω = (1/4, 1/3, 5/12).

a. Draw a transition state diagram for X .                                                         [1]

b. Identify the communicating classes. State whether each class is positive recur- rent, null recurrent, or transient, and state its period.                                  [2]

c.  Calculate the equilibrium probability distribution π for X .                         [2]

d. Deduce that the long-term proportion of time X spends in state A is 3/8. Why is the long-term proportion of time in state B intuitively obvious?     [1]

e. Briefly explaining your method, find an expression for Pn  of the form Pn  = λ1(n)U1 + λ2(n)U2 + λ3(n)U3            (n = 0, 1, 2, 3, . . . )

where you should explicitly determine λ 1 , λ2 , λ3  and U1 , U2 , U3 .                   [6]

f. Using your formula for Pn , show that P(X2  = A|X0  = B) = 1/3 and determine P(X2  = A).                                                                                                     [4]

g.  Justifying your steps, for k, m, n 2 0, find an explicit expression for P(Xk+m  = A; Xk+m+n  = C|Xk  = B).

Determine the limit as m, n → & and give a brief intuitive explanation for your answer.                                                                                                   [4]

2. A particle performs a random walk on the set of vertices V = {A, B, C, D, E, F} of the octahedron (that is, a 3-dimensional object with 8 faces) shown below.  In each time step, the particle moves to one of the neighbouring vertices, each chosen with equal probability independently of everything else previously.

Let Xn  be the position of the particle at time n, then X = (Xn  : n = 0, 1, 2, . . . )

forms a discrete time Markov chain.  Let Pi  and ←i  represent probability and ex- pectation, respectively, conditional on X0  = i ∈ V . The first hitting time of state i is defined by Ti  := inf{n > 0 : Xn  = i}.

a.  Justifying your steps, show that

PB (TA  < TD ) = 3

扌╱nt!  宁ou s左oul〉m)≠é usé o≠ symmétry$                                                  [6]

b. Find the expected time, ←B (TA ), for the particle to reach vertex A given it starts from vertex B .                                                                                      [6]

c. Deduce the average time, ←A (TA ), to return to state A starting from A.     [2]

d. Deduce the long term proportion of time spent in state A and write down the invariant probability measure π for X .                                                          [2]

e.  Starting in state A, what is the average number of visits to state D before first

returning back to state A?

f. Deduce that, with probability one,

total number of visits to state A by time n                1

total number of visits to either state B or C by time n      2

Briefly explain your reasoning.

[2]

as n → &.

[2]

3.  Single customers arrive at a queue at rate 1, and in addition, when the queue is empty, pairs of customers arrive at rate 2. All customers have exponential service times with rate 3, and there is a single server. This queueing system is modelled by a continuous-time Markov chain X = (X(t))t>0  with state space 主+  = {0, 1, 2, . . . } and Q matrix

、│

Q =  ．(．)   0      3    _4    1     0     0    . . . │(│)

．(．)   0      0      3    _4    1     0    . . . │(│)

．       . . .    . . .    . . .    . . .   . . .   . . .．

where X(t) is the number of customers at time t, including anyone currently being served.

Let π = (πn )ne主+   be the equilibrium distribution for the number of customers in the queue, that is, π satisfies πQ = 0, πn  2 0,     ne主+  πn  = 1. For s ∈ [0, 1], define

(s) :  = n>0 πn sn .

a. Write out the structure of the equilibrium equations πQ = 0.

b.  Show that

(s) =

πn  =  ╱  、 n

and find π 1 .

d. Deduce that X is positive recurrent and that the long-term proportion of time

e.  Calculate the long-term average length of the queue.                                   [4]

4. A mouse travels through the rooms A, B and C connected as shown:

The room occupied by the mouse at any given time is described by a continuous-time Markov chain as follows. The mouse waits in the current room for an exponential length of time with rate 3.  Then the mouse chooses a door in the current room uniformly at random and goes through it to the next room.  All choices are made independently of what happened before.

Let X(t) denote the room the mouse is in at time t 2 0.  Initially, the mouse is placed in room B.

a. Write down the Q-matrix of (X(t) : t 2 0).

b. What is the probability that the mouse is in room B at time t? 扌╱nt! usé t左é résolvént R(λ) = (λI _ Q)-1 à