DEPARTMENT OF MATHEMATICS
INDIAN INSTITUTE OF TECHNOLOGY GUWAHATI
MA225 Probability Theory and Random Processes July - November 2025
Problem Sheet 10 NS
(n)
You may use the following: Let us define fij = P (X1 ̸= j, · · · , Xn−1 ̸= j, Xn = j | X0 = i). This is
P∞ (n)
the probability that state j is first visited from state i at time n. Write fij = n=1 fij which is the
(n)
probability that state j is ever visited from state i. If fij = 1, then {fij } is a probability distribution (first
passage time distribution).
(n) (n)
When j = i and i is recurrent, {fii } is the recurrence (or first-return) time distribution (i.e., fii =
(n) (n)
Pi (Ti = n)) and fii = ∞ is fi in our notation. Also, mi = Ei (Ti ) = ∞
P P
n=1 fii n=1 nfii is the mean
recurrence time.
1. Let {X n , n ≥ 0} be a Markov
chain with three states 0, 1, 2 and with transition probability matrix
1/2 1/2 0
P = 1/3 1/3 1/3 and the initial distribution P (X0 = i) = 13 , i = 0, 1, 2. Compute P {X2 =
0 1/2 1/2
2, X0 = 1}, P {X1 ̸= X0 }, P {X3 = 1|X1 = 0}, P {X2 = 2, X1 = 1|X0 = 2}, P {X2 = 1} and
P {X0 = 1|X1 = 1}. Now, draw the state transition diagram and find the communicating classes. Is
the chain reducible, recurrent (null or non-null)? What are the periods of the states? Determine the
stationary distribution. Is this the same as the limiting distribution? If so, why?
2. Check whether the following processes are Markov chains or not. If they are, then find the one-step
state transition probability matrix P and draw the state transition probability diagram. Also, find the
initial distribution. Find the communicating classes and classify the states according to transient and
recurrent states. Determine the limiting and the stationary distributions if it exists.
(a) Consider the experiment of tossing a coin repeatedly. Let p be the probability of head in a single
trial. The state of the system at time n is the number of heads minus the number of tails in first
n tosses.
(b) Consider a sequence of trials each consisting in placing a ball at random in any of N given cells.
Let there be an indefinite supply of balls and let Xn be the number of empty cells after n balls
are placed.
3. Consider the Markov chain Xn ∈ {0, 1, 2, 3} starting with state X0 = 1 and with the following
transition probability matrix
1 0 0 0
0.1 0.2 0.5 0.2
P = 0.1
0.2 0.6 0.1
0.2 0.2 0.3 0.3
Determine the probability that the process never visits state 2 .
4. The one-step
transition probability matrix
for a Markov chain with state space {0, 1, 2, 3, 4} is given
0 1 0 0 0
1/3 2/3 0 0 0
by P = 0 1/2 0 0 1/2
.
0 0 0 1/4 3/4
0 0 0 1/2 1/2
(a) Indicate the communicating classes and all the closed sets in this Markov chain. Also classify the
states into recurrent or transient states with proper justification.
1
(b) Find the period of state 0.
(c) Find if possible a proper subset of a closed communicating class which is again closed.
(d) Find if possible the stationary distribution of the Markov chain corresponding to a closed subset
C of S containing state 3. What will be the limiting distribution of the Markov chain with state
space C?
(n) (n) (n)
(e) Find the values of f01 , f22 , f23 , f24 , f20 , f21 , and limn→∞ p01 , limn→∞ p33 , limn→∞ p22 .
(f) What is the expected number of times the system is in state 2?
(g) Suppose the chain starts in state 1, what is the expected number of steps until the system is in
state 4?
5. Prove that for an irreducible Markov chain with N states it is possible to go from any state to any
other state in at most N − 1 steps.
6. Consider a Markov chain on the vertices of a triangle: the chain moves from one vertex to another
with probability 1/2. Find the probability that, in n steps, the chain returns to the vertex it started
from.
7. Find an example of a finite state space Markov chain with at least one transient state and has a limiting
or long run distribution that is the same as its stationary distribution.