Department of Mathematics

MTL 106 (Introduction to Probability Theory and Stochastic Processes)

Tutorial Sheet No. 8
1. The one step transition probability matrix of DTMC {Xn , n = 0, 1, . . .} with state space {1, 2, 3} is
 
0.1 0.5 0.4
P =  0.6 0.2 0.2 
0.3 0.4 0.3
and the initial distribution is π0 = (0.7, 0.2, 0.1). Find
(a) P (X2 = 3)
(b) P (X3 = 2, X2 = 3, X1 = 3, X0 = 2)
(c) P {X30 = 3|X27 = 1}.
2. For a Markov chain {Xn , n = 0, 1, . . .} with state space E = {0, 1, 2, 3, 4} and transition probability matrix
P given below,
 1 classify the states
 of the chain. Also  determine the closed
 communicating classes.
1 1 1 1

6
2 0 0 2 0 0 3 0 3 3
 1 1 0 0 0   1 1 0 1 0 

2
 12 21   3 3 3 
1  2 1 
(a) P =  4 2 0 0 4 . (b) P =   01 01 3 01 13 .

5-
 0 0 0 1 0   0 4 4 
4 4
1 1 1
0 0 2 4 4 0 0 31 0 23

2
3. Assume {Yn , n = 0, 1, . . .} is a sequence of IID RVs taking values on N ∪ {0}, with probability distribution
20
P (Yn = i) = ai (i = 0, 1, . . .). Let Xn+1 = (Xn − 1)+ + Yn . Prove that {Xn , n = 0, 1, . . .} is a Markov chain
and write down its transition probability matrix.
4. Consider an inventory model. Let Yn be a quantity for the daily need, Xn be inventory quantity at nth day
er
and (s, S) is inventory storage. That means, when the inventory Xn is not more than s, it should be stocked
to the inventory S; when the inventory Xn is more than s, it should be stocked. Assume {Yn , n = 0, 1, . . .} is
t

a sequence of IID RVs with probability distribution P (Yn = i) = ai (i = 0, 1, . . .). Fix 0 < s < S < ∞. Let
es

(
Xn − Yn+1 , if s < Xn ≤ S;
Xn+1 =
S − Yn+1 , if Xn ≤ s.
m

Prove that {Xn , n = 0, 1, . . .} is a Markov chain and write down its transition probability matrix.
Se

5. Suppose that a machine can be in two states {0, 1} where 0 implies working and 1 implies out of order on
a day. The probability that a machine is working on a particular day depends on the state of the machine
during two previous days. Specifically assume that P {Xn+1 = 0|Xn−1 = j, Xn = k} = qjk j, k = 0, 1 where
II

Xn denotes the state of the machine on nth day.

(a) Show that {Xn , n = 1, 2, . . .} is not a DTMC.
(b) Define a new state space for the problem by taking the pairs (j, k) where j and k are 0 or 1. It is said
that machine is in state (j, k) on day n if the machine is in state j on day (n − 1) and in state k on nth
day. Show that in this case the state space of the system is a DTMC.
(c) It is given that the machine was working on Monday and Tuesday. Find the probability that it will be
working on Thursday?
6. Consider the chain with transition matrix
 
1/6 1/3 1/2 0
 1/2 1/2 0 0 
P=
 1/6 1/3 1/2 0  .


0 1/6 1/3 1/2

Identify the closed class.

1
 7. Consider a Markov Chain with state space S = {0, 1, 2, 3, 4} and transition probability matrix
 
1 0 0 0 0
 0 0.25 0.75 0 0 
 
P=  0 0.5 0.5 0 0  .
 0.25 0.25 0 0.25 0.25 
0 0 0 0.5 0.5

(a) Classify the states of the chain.

(b) Determine the stationary distribution for states 1 and 2.
(c) For the transient states, calculate µij , the expected number of visits to transient state j, given that the
process started in a transient state i.
(d) Find P {X5 = 2 | X3 = 1}.

8. Show that if a Markov Chain is irreducible and Pii > 0 for some state i then the chain is aperiodic.
9. Consider the Markov chain {Xn , n = 0, 1, 2}with S = {0, 1, 2} and transition probability matrix given as:

2 6
 1 1 1 
4 2 4
1 2
P= 0 .

5-
3 3
1 1
2 0 2

2
(a) Classify the chain as irreducible, aperiodic and find the stationary distribution.
20 

(b) Consider a DTMC with transition probability matrix  0.4 0

0.4 0.6 0


0.6 . Find the stationary distri-

0 0.4 0.6
bution for this Markov chain.
er
(c) Assume X0 = 1 and let R be the first time that the chain returns to state 1, i.e., R = min{m ≥ 1 : Xn = 1}.
Find E[R|X0 = 1].
t
es

10. A mathematics professor has 2 umbrellas. He keeps one of them at home and the other in the office. Every
morning, when he leaves home, he checks the weather and takes an umbrella with him if it rains. In case
m

both the umbrellas are in the office, he gets wet. The same procedure is repeated in the afternoon when
he leaves the office to go home. The professor lives in a tropical region, therefore, the chance of rain in the
Se

afternoon is higher than in the morning; it is 1/5 in the afternoon and 1/20 in the morning. Whether it rains
or not is independent of whether it rained the last time he checked. On day 0, there is an umbrella at home,
and 1 in the office. Note that, there are two trips each day. What is the expected number of days that will
pass before the professor gets wet? What is the probability that the first time he gets wet it is on his way
II

home from the office?

11. Consider a DTMC on non-negative integers where the chain, moves from i, to i + 1 with probability p, to
state 0 with probability 1 − p, and then return to i with probability 0 < p < 1. Show that this DTMC is
irreducible and recurrent and has a unique stationary distribution, also, find the stationary distribution.
12. A random walker walks on the integers. At each step, he moves one step right with probability 31 , two steps
left with probability 13 , and stays on his place with probability 13 . What is the probability that the walker
will return to his original location after three steps?
13. Show that the birth and death chain is recurrent if and only if
∞
X
γk = ∞
k=0

2
 where, γ0 = 1 and
q1 · · · qk
γk = , k = 1, 2, . . .
p1 · · · pk
qi = pi i−1 , i = 1, 2, . . .
pi = pi i+1 , i = 1, 2, . . . .

14. Show that an irreducible birth and death chain on S = {0, 1, . . .} is recurrent if and only if
∞
X q1 · · · qk
=∞
p1 · · · pk
k=0

where
qi = pi i−1 and pi = pi i+1 , i = 1, 2, . . .

15. Consider the birth and death chain on {0, 1, . . .} with

k+2 k

6
pk = and qk = ,k ≥ 0
2(k + 1) 2(k + 1)

2
determine whether the chain is recurrent or transient.

5-
Fij
16. Prove that µij = 1−Fij , i, j ∈ S.

2
(n)20
17. Prove that if i is a recurrent state and suppose pij > 0 for some n, then state j is recurrent and Fij = Fji = 1.

18. Define
(n)
ejk = P {Xn = k, Xm ̸= j, 0 < m < n|X0 = j}
er
denotes the probability that the chain starting from state j, the chain leads to state k at the nth step without
(n) (n)
hitting j in the middle. Prove that, if pjk > 0, then there exists m ≤ n such that ejk > 0.
t
es

19. Let {Xn , n = 0, 1, . . .} be a DTMC. Prove that the distribution of Xn is independent of n if and only if the
initial distribution π is a stationary distribution.
m

20. Consider a DTMC model arising in an insurance problem. To compute insurance or pension premiums for
professional diseases such as silicosis, it is needed to compute the average degree of disability at pre-assigned
Se

time periods. Suppose that, m degrees of disability S1 , S2 , . . . , Sm are retained. Assume that an insurance
policy holder can go from degree Si to degree Sj with a probability pij . This strong assumption leads to
the construction of the DTMC model in which P = [pij ] is the one step transition probability matrix related
to the degree of disability. Using real observations recorded in India, the following transition matrix P is
II

considered :  
0.90 0.10 0 0 0
 0 0.95 0.05 0 0 
 
P=  0 0 0.90 0.05 0.05 

 0 0 0 0.90 0.10 
0 0 0.05 0.05 0.90

(a) Classify the states of the chain as transient, positive recurrent or null recurrent along with period.
(b) Find the limiting distribution for the degree of disability.

21. Consider a DTMC with state space S = {0, 1, . . .} and define transition probabilities as pjj+2 = vj and
pj0 = 1 − vj , for j ∈ S. Find the transition probability matrix of Markov chain and classify the states of this
chain.

3
22. Consider an irreduciblePDTMC with state space S = {0, 1, . . . , m}. Assume that, P = [pij ] is a double
m Pm
stochastic matrix, i.e., k=1 pki = k=1 pik = 1 for each i = 1, 2, . . . , m. Prove that the stationary distri-
bution of this Markov chain is the uniform distribution on {1, 2, . . . , m}.
23. Consider the simple random walk on a circle. Assume that K odd number of points labeled as 0, 1, . . . , K − 1
are arranged on a circle clockwise. From i, the walker moves to i + 1 (with K identified with 0) with
probability p (0 < p < 1) and to i − 1 (with −1 identified with K − 1) with probability 1 − p. Find the
steady-state distribution for this random walk, if it exist.
24. Let, {Xn , n = 0, 1, . . .} be a time-homogeneous DTMC with state space S = {0, 1, 2, 3, 4} and one-step
transition probability matrix  
1 0 0 0 0
 0.5 0 0.5 0 0 
 
P= 0 0.5 0 0.5 0 .

 0 0 0.5 0 0.5 
0 0 0 0 1
(a) Classify the states of the chain as transient, +ve recurrent or null recurrent.

6
(b) When P (X0 = 2) = 1, find the expected number of times the Markov chain visits state 1 before being

2
absorbed.

5-
(c) When P (X0 = 1) = 1, find the probability that the Markov chain gets absorbed in state 0 .
25. A rumor-spreading paradigm is one method of information dissemination over a network. Assume that there

2
are 5 hosts connected to the network. One host starts off by sending a message. Every round, the message
20
is sent by one host to another host who is selected independently and uniformly at random from the other
4 hosts. When all hosts have received the message, the process ends. Create a discrete-time model of this
process with Markov chains
er
(a) Xn be state of host (i = 1, 2, . . . , 5) who received the message at the end of nth round.
(b) Yn be number of hosts having the message at the end of nth round.
t

Find one step transition probability matrix for the above DTMC. Classify the states of the chains as transient,
es

positive recurrent or null recurrent.

26. Consider a Markov chain with state space {0, 1, 2, 3, 4} and transition matrix
m

 
1 0 0 0 0
Se

 0 3 1 0 0 
 4 4
 0 3 1

 1 14 4 0 0  .
1 1 

4 4 0 4 4
1 1
0 0 0
II

2 2

(a) Classify the states of the chain.

(b) Determine the stationary distribution for states 1 and 2.
(c) For the transient states, calculate µij , the expected number of visits to transient state j, given that the
process started in transient state i.
(d) Find P {X5 = 2 | X3 = 1}.
27. Let us consider a Markov chain with states space S = {0, 1, 2, 3, 4} and probability transition matrix
0 14 0 34 0
 
 1 0 1 0 0 
 2 2 
P=  0 0 11 02 0  .

 0 0 0 
3 3
0 0 0 0 1

4
 (a) If the chain, starts from state 0, find the probability of absorption in state 3 and state 5.
(b) If the chain, starts from state 3, determine the expected number of visits that the chain makes to state
3 before getting absorbed.
28. Let p00 = 1 and, for j > 0, pjj = p, pjj−1 = q where p + q = 1, define the transition probability matrix of
DTMC.
(n)
(a) Find fj0 , the probability that absorption takes place exactly at the nth step given that the initial state
is j.
(b) Find the expectation of this distribution.
29. Think about doing a rabbit mating experiment. The evolution of a specific gene that is present in both
types G and g is compared. A rabbit has two genes, either GG (dominant), Gg (hybrid, where the order is
immaterial and gG is same to Gg) or gg (recessive). When two rabbits are mated, the progeny has an equal
chance of receiving a gene from each parent. The progeny will either be dominant with probability 21 or
hybrid with probability 12 if a dominant (GG) with a hybrid (Gg) are mate. Begin by mating a hybrid with
a rabbit of the specified character (GG,Gg, or gG). Through several generations, the procedure is repeated,

6
always mating with a hybrid, and the progeny is mated with another hybrid. Start with a hybrid rabbit.

2
Let Yn be the probability distribution of the character of the rabbit of the nth generation. Then, compute
Y3 (gg).

2 5-
20
t er
es
m
Se
II