STAT 333

Midterm 2
Winter 2025

Question MC 1 2 3 Total
Points 40 19 6 15 80

Instructions

1. You have 90 minutes for this test.

2. The first part consists of multiple choice questions. Answers must be recorded on the bubble sheet provided on
the last page of the test. You may tear off the bubble sheet, but you must record your answers there and submit it.
3. Answer the questions in the spaces provided. You may use Pages 11 – 12 of the test for any additional work you
would like to be graded. If you use this space, make it as clear as possible in the corresponding question that your
answer continues on Pages 11 – 12.
4. You may use a 8.5×11 (US letter) paper of notes (front and back) which can be hand-written or typeset, and a non
programmable calculator.

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 1 of 12

Multiple Choice
Pages 2 – 5 will not be graded. You must record your answers in the bubble sheet at the very end of the exam.
You may tear off the bubble sheet, but you must submit it. Each question has exactly one correct answer and is worth 2
marks.

1. A discrete time Markov chain is time-homogeneous when

(a) It has finitely many states.

(b) The transition probability from state i to state j at time n is constant in i for all i, n.
(c) The transition probability from state i to state j at time n is constant in n for all i, j.
(d) The transition probability from state i to state j at time n is constant in j for all j, n.
(e) The rows and columns of the transition probability matrix all sum to 1.

2. Consider a DTMC with state space S and let i, j ∈ S with i → j. Which of the following must be true?

(a) If i is recurrent, then j is recurrent.

(b) If i is transient, then j is transient.
(c) If j is recurrent, then i is recurrent.
(n)
(d) We have Pj,i > 0 for at least one n ∈ N.
(e) We have fi,j = 1.

3. A simple random walk on Z with Pi,i+1 = p = 1 − Pi,i−1 is never

(a) Aperiodic
(b) Irreducible
(c) Doubly-stochastic
(d) A Birth and Death process
(e) Time-homogeneous

4. A simple random walk on Z is:

(a) Always null recurrent.
(b) Either positive recurrent or transient depending on the probability of moving up or down.
(c) Always recurrent.
(d) Always transient.
(e) Either null recurrent or transient depending on the probability of moving up or down.

5. For a symmetric random walk on Z the random time of first return to 0 starting at 0:
(a) Can be infinite with positive probability.
(b) Has finite expected value.
(c) Cannot be infinite with positive probability but has infinite expected value.
(d) Is equal to 2 with probability 1/4.
(e) Is equal to 17 with positive probability.

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 2 of 12

 6. Suppose that {Xn : n ∈ N0 } is a DTMC with state space S. Let w, x, y, z ∈ S Which of the following is not always
true?

(a) If x ↔ y and y ↔ z, then x ↔ z.

(b) If x → y and y → z then x → z.
(c) If x → y and y → x then x ↔ y.
(d) If w ↔ x and y ↔ z and x ↔ y then w ↔ z.
(e) If w ↔ x and y ↔ z and x → y then w ↔ z.

7. Which of the following is not equivalent to the statement “x ∈ S is a recurrent state”:

(a) Px (Tx < ∞) = 1.
(b) Ex [Nx ] = ∞.
(c) Px (Nx = ∞) = 1
(d) Ex [Tx ] < ∞
n
P
(e) n≥0 Px,x = ∞

 n
8. For a state x ∈ S of a DTMC define Lx = n ∈ N : Px,x > 0 and let dx denote the period of x. Which statement
is false:
(a) If x ↔ y then Lx = Ly .
(b) dx = gcd(Lx ).
(c) If x ↔ y then dx = dy .
(d) If x ↔ y then dx = gcd(Ly ).
(e) If a, b ∈ Lx then (a + b) ∈ Lx

9. Which of the following is not a property shared by all states in a communicating class?
(a) Null Recurrence.
(b) Recurrence.
(c) Transience.
(d) Period.
(e) Expected return time.

hP i
(x) Tx
10. For a recurrent state x ∈ S and the measure ν (x) on S with mass function given by νy = Ex n=1 1[Xn =y] which
of the following is false:

(a) ν (x) (S) = Ex [Tx ].

hP i
(x) Tx
(b) νy = Ex n=0 [Xn =y] for all y ∈ S
1
(x)
(c) νx = 1.
(x)
(d) νy > 0 if and only if x ↔ y
(x)
(e) ν is invariant.

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 3 of 12

 11. Consider a DTMC with state space N0 = {0, 1, . . . } with TPM P . Assume that P is doubly stochastic. Let i, j ∈ N0 .
Which of the following is not always true?
(a) Pi,j ≤ 1
(b) Pi,j ≥ 0
P∞
(c) j=0 Pi,j = 1
P∞
(d) i=0 Pi,j = 1
(e) Pi,j = Pj,i .

12. For a DTMC on a finite state space:

(a) It is possible to have an invariant measure supported on a transient class.
(b) It is possible for the chain to have a null recurrent class.
(c) There must be at least one recurrent state and it may not be positive recurrent.
(d) There must be at least one recurrent state and it must be positive recurrent.
(e) It is possible to have no recurrent states.

13. Consider a Galton–Watson branching process with offspring distribution q with q0 > 0, µ = E[ξ1,1 ]= 1 and σ 2 =
PXn iid
Var(ξ1,1 ) for ξ1,1 ∼ q. That is, X0 = x > 0 (initial population) and for n ∈ N, Xn+1 = i=1 ξn,i where ξn,i ∼ q.
Which of the following is false:
(a) E[Xn+1 | Xn ] = Xn .
(b) Var(E[Xn+1 |Xn ]) = Var(Xn )
(c) Var(Xn+1 |Xn ) = σ 2 Xn
(d) State 0 is transient.
(e) All of the above are true (select this if you think (a) – (d) are all false).

14. For a Galton–Watson branching process with offspring distribution q with q0 > 0, µ = E[ξ1,1 ] and σ 2 = Var(ξ1,1 )
for ξ1,1 ∼ q and Mq is the MGF of ξ1,1 ∼ q, which of the following is true:
(a) The population has a positive probability of not going extinct if and only if µ ≥ 1.
(b) The population has a positive probability of not going extinct if and only if σ ≤ 1.
(c) The probability of extinction is a solution to the equation β = Mq (log(β)).
(d) Mq (log(β)) is strictly concave in β for some choices of q.
(e) The probability of extinction by time n is decreasing as a function of n.

15. Let {Xn : n ∈ N0 } be a DTMC with one-step TPM P . Let π be a distribution. Which of the following is always
true?
(a) If DB(P, π), then πP = π.
(b) If πP = π, then DB(P, π).
(c) If πP = π, then lim P(Xn = i | X0 = j) = πj .
n→∞
(d) If πP = π, then Xn ∼ π for all n ∈ N.
(e) If πP = π and X0 ∼ π, then (X0 , X1 , X2 ) has the same distribution as (X2 , X1 , X0 ).

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 4 of 12

 16. In which of the following cases is identifying an invariant distribution for P a TPM on S = N ∪ {0} (assuming it
exists) most challenging:
(a) P is doubly stochastic.
(b) P satisfies a detailed balance condition with some given distribution π.
(c) P is a “birth-death process” (a.k.a. P is tri-diagonal).
(d) P is a “regenerative process” (it either increases by 1 or returns to 0 on each step).
(e) P = 12 (Q + R) where Q and R are TPMs with given invariant distributions µ and ν respectively.

17. Consider a DTMC with state space S and TPM P . Let x ∈ S be recurrent and y ∈ S be transient. Which of the
following must be false?
(n)
(a) Px,y > 0 for at least one n ∈ N.
(n)
(b) Py,x > 0 for at least one n ∈ N.
P∞ (n) P∞ (n)
(c) n=1 Py,y < n=1 Px,x .
P∞ (n)
(d) n=1 Px,x = ∞
(e) x ̸↔ y.

18. Let {Xn : n ∈ N0 } be a DTMC with one-step TPM P . Which of the following is not always true?

(a) Any invariant measure ν satisfies ν = νP .

(b) Any invariant measure can be scaled to be an invariant distribution.
(c) Any invariant distribution is an invariant measure.
(d) Any positive linear combination of invariant measures is an invariant measure.
(e) All of the above (select this if you think (a) – (d) are always true).

19. Suppose the DTMC {Xn : n ∈ N0 } is a Birth-Death process. Which of the following is definitely true?

(a) The state space is Z.

(b) Xn cannot take negative values.
(c) P(Xn+1 = i | Xn = j) = 0 if |i − j| > 1.
(d) The chain is irreducible.
(e) The chain has at least one recurrent class.

20. Consider an irreducible DTMC {Xn } with space space N0 = {0, 1, . . . } and TPM P . Suppose that π is an invariant
distribution for this DTMC, and that X0 ∼ π. Which of the following is not necessarily true?

(a) Xn ∼ π.
P∞
(b) πi = j=0 πj Pj,i .
(c) πP = π
(d) πi Pi,j = πj Pj,i .
(e) All of the above are false (select this if you think all of the above are true)

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 5 of 12

 Written Answer Questions
1. [19] Consider a DTMC {Xn : n ∈ N0 } with state space S = {0, 1, 2}, initial distribution α0 = (1/2, 1/4, 1/4) and
one step TPM  
1/4 3/4 0
P = 1/4 1/4 1/2 .
0 1/4 3/4

(a) [2] Find P(X1 = 1).

(b) [2] Find E[X1 ].

(c) [2] Find P(X0 = 0, X1 = 1, X2 = 2).

(d) [3] Find P(X3 ̸= 0, X2 = 0 | X0 = 1).

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 6 of 12

 (e) [2] Write down the communication class(es) for this DTMC. For each communication class, write down if it is
null recurrent, positive recurrent, or transient.

(f) [3] Compute an invariant distribution for this chain. Is it unique?

(g) [3] What is the long run fraction of the time the chain spends in state 0? Is this the same as lim P(Xn = 0 |
n→∞
X0 = 1)?

1
Pn
(h) [2] Determine lim n+1 i=0 Xi2 .
n→∞

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 7 of 12

 2. [6] A Rubik’s cube is a children’s toy shaped like a cube (6 faces) formed by 3 × 3 × 3 sub-cubes that are all distinct.
A “face” below refers to a 3 × 3 × 1 square of sub-cubes at one side of the Rubik’s cube. Each face can be rotated
individually by an angle of π/2, π, or 3π/2. Each choice of face (of which there are 6) and each angle of rotation
(of which there are 3 options, 4 if you included no rotation) leads to a different configuration of the sub-cubes (the
state) which is distinct from the current state. The cube has 1 special configuration called “solved”. Let the set
of all configurations accessible from “solved” be S. There is some very large number of possible configurations, so
|S| = N < ∞. Every move can be undone in one move by picking the same face and the supplementary rotation.
Any pair of states that can be reached from the “solved” state can both reach the “solved” state and reach each
other (e.g. by undoing the exact sequence of moves that takes the “solved” state to the first state, then doing the
sequence of moves that takes solved to the second state).
I don’t know how to how to solve the Rubik’s cube (go from any state to “solved” efficiently). So, my strategy for
solving is the same as my strategy for randomizing the cube: for each move I make, I randomly pick a face and
randomly pick a rotation amount from {π/2, π, 3π/2}, both uniformly at random, and I perform the corresponding
move. You do not need to compute the exact value of N , just leave your answers in terms of N and S.

(a) [2] Explain why you know the uniform distribution on configurations must be invariant for the DTMC formed
by my sequence of moves.

(b) [2] What is the long run fraction of time that my cube is solved? From what result do you know this and
explain why it applied?

(c) [2] If I start with a solved Rubik’s cube, what is the expected time until it is solved again?

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 8 of 12

 3. [15] Let S = {0, ..., 5}. We will define some TPMs on S by the following:
( (
1/3 : j − i even 1/2 : j − i ∈ {0, 3, −3} 1
Qi,j = Ri,j = P = (Q + R) (1)
0 : else 0 : else 2

In words: Q updates the state by moving by a random even number while R moves by a random multiple of 3. Note
also that 0 is an even number.

(a) [3] Which of Q, R and P are irreducible? For any that are not irreducible, describe their communicating
classes.

(b) [2] Can any of P, Q, R be periodic with period d ≥ 2?

(c) [2] Show that Q, R both satisfy a detailed balance condition with respect to the uniform distribution π =
Unif(S), i.e., show DB(Q, π) and DB(R, π) hold.

(d) [2] Is it also true that DB(P, π) holds?

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 9 of 12

 (e) [2] Starting at i ∈ S what is the long run fraction of the time a DTMC with TPM Q spends in j ∈ S?

(f) [2] Starting at i ∈ S what is the long run fraction of the time a DTMC with TPM R spends in j ∈ S?

(g) [2] Starting at i ∈ S what is the long run fraction of the time a DTMC with TPM P spends in j ∈ S?

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 10 of 12

 Extra space for answers. Please make it as clear as possible which question your answer relates to.

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 11 of 12

 Extra space for answers. Please make it as clear as possible which question your answer relates to.

University of Waterloo STAT 333 – Midterm 2 – Winter 2025 Page 12 of 12