CS计算机代考程序代写 chain MAST30001 Stochastic Modelling

MAST30001 Stochastic Modelling

Tutorial Sheet 8

1. A CTMC (Xt)t≥0 with state space S = {1, 2, 3, 4} has non-zero transition rates
q1,2 = 4, q2,1 = 1 = q2,4 and q2,3 = 3. Suppose that P(X0 = 1) = 1 (i.e. the chain
starts in state 1), and let T1 = inf{t > 0 : Xt 6= X0} be the first jump time of
(Xt)t≥0, and T2 = inf{t > T1 : Xt 6= XT1} denote the time of the second jump.

(a) Draw the transition diagram for the CTMC (Xt)t≥0

1 2

3

4

4

1

3

1

(b) Describe the communicating classes of (Xt)t≥0
3 and 4 are absorbing states (so their own communicating classes), while 1 and
2 communicate with each other

(c) Find h1,3, the probability of ever reaching state 3.
This is the same as for the jump chain, which has transition diagram

1 2

3

4

1

1/5

3/5

1/5

1

1

The hitting probability of state 3 is
3/5

3/5+1/5
= 3/4.

(d) What is the distribution of T1?
exponential(4)

(e) What is the distribution of XT1?
XT1 = 2 with probability 1

(f) Find E[T2].
This is the expectation of the sum of the first two jump times which are re-
spectively exponential(4) and exponential(3 + 1 + 1) random variables, so the
expectation is 1

4
+ 1

3+1+1
= 9/20.

(g) What is the distribution of XT2?
P(XT2 = 1) =

1
5

= P(XT2 = 4), while P(XT2 = 3) = 3/5
(h) Find m1,{3,4}, which is the expected time until (Xt)t≥0 reaches state 3 or 4.

Let A = {3, 4} then

m1,A =
1

4
+m2,A

m2,A =
1

5
+

1

5
m1,A + 0

Solving gives m1,A = 9/16.

(i) Find the limiting proportion of time spent in each state.
This is random. The limiting proportion of time spent in state 3 is 1 with
probability h1,3, and zero with probability 1 − h1,3. The limiting proportion
of time spent in state 4 is 1 with probability h1,4 = 1 − h1,3 and zero with
probability h1,3. The limiting proportion of time spent in states 1 and 2 are
zero respectively.

2. Let λ, µ > 0, and consider a CTMC with state space S = Z+ whose non-zero
transition rates are qi,i+1 = λ and qi+1,i = (i+ 1)µ for each i ∈ Z+.

(a) Explain intuitively why this CTMC is positive recurrent.
Let i0 = min{i : iµ > λ}. Then at each state i ≥ i0 we wait for less than
a exponential(λ + µ) amount of time before jumping, and we jump down with
probability

iµ+ λ

i0µ

i0µ+ λ
=: κ > 1/2.

Therefore for all states i ≥ i0 (i.e. all but finitely many of the states) we have
a bias (that is bounded below) to the left. Thus, mi,i0 <∞ for each i ≥ i0. On the other hand mi,i0 <∞ for each i < i0 since this is the same as the expected hitting time of i0 starting from i for a finite-state Markov chain with state space {0, 1, . . . , i0}. This shows that mi,i0 is finite for every i, and thus the expected return time to i0 is finite. This means that the expected return time to every state is finite, so the chain is positive recurrent. (b) Find the stationary distribution. This is a birth and death chain so it satisfies the detailed balance equations. Thus, for each i ∈ N, πiiµ = πi−1λ. Solving gives πi = ( λ µ )i 1 i! π0. Summing over i ∈ Z+ gives 1 = π0 ∞∑ i=0 ( λ µ )i 1 i! = π0e λ/µ, so π0 = e −λ/µ and πi = e −λ/µ ( λ µ )i 1 i! . So the stationary distribution is Poisson with parameter λ/µ. (c) Find the limiting distribution, starting from initial distribution a. This is an irreducible positive recurrent Markov chain, so the limiting distribu- tion is π regardless of the starting distribution (d) Find the limiting proportion of time spent in each state. As above, this is π 3. (CTMCs as limits of DTMCs) Let P be a stochastic matrix with i, j-th entry pi,j, and such that pi,i = 0 for all i. For (λi)i∈S and for each integer m > supi∈S λi, define
a DTMC (Y (m)n )n∈Z+ by

P(Y (m)n+1 = i|Y
(m)

n = i) =

(
1−

λi
m

)
,

and for i 6= j
P(Y (m)n+1 = j|Y

(m)

n = i) =
λi
m
pij.

Define a continuous time process (not a CTMC though) by

X
(m)

t = Y
(m)

bmtc,

where bac is the greatest integer not bigger than a.

(a) What does a typical trajectory of X (m) look like? At what times does it jump?
The chain only has jumps at times k/m for k an integer. Given the chain is
in state i, it stays there for a geometric λi/m (> 0) number of 1/m time units
and then jumps according to the one step transition matrix P . The number
of these time units are the number of integer time units between jumps in the
Y (m) chain.

(b) Given X
(m)

0 = i, what is the distribution of the random time

T (m)(i) = min{t ≥ 0 : X (m)t 6= i}

As mentioned in the previous problem, the Y (m) chain stays at state i for a
geometric (λi/m) number of time units before jumping. Then considering the
time change to get from Y (m) to X (m), the variable mT (m)(i) is geometric λi/m
(> 0); that is for k = 1, 2, . . .

P(T (m)(i) = k/m) =
λi
m

(
1−

λi
m

)k−1
.

(c) As m→∞, to what distribution does that of the previous item converge?
A standard calculation (do it!) shows that if Zp is geometric p, then pZp con-
verges in distribution to an exponential distribution with mean 1 as p → 0.
Since mT (m)(i) is geometric λi/m, T

(m)(i) converges to an exponential variable
with rate λi.

(d) It turns out that X (m) converges (in a certain sense) as m→∞ to a continuous
time Markov chain. What are its transition rates?
Since the holding times converge to exponential variables as m goes to infinity,
the description of the limiting chain is as follows. Given X0 = i the chain waits
an exponential with rate λi time and then jumps to state j with probability pi,j
(the state jumped to is independent of the time of the jump). Then the chain
stays in state j and exponential λj amount of time and jumps to state k with
probability pj,k, and so on. Thus the transition rates are λipi,j for j 6= i.