Spring 2018, Math 171
Week 3

Stopping/NonStopping times

Let \(T_1, T_2\) be stopping times for some Markov Chain \(\{X_n:n \ge 0\}\). Which of the following will also necessarily be stopping times? Prove your claims.

(Discussed) \(T_3=5\)

\(T_4=T_1 + T_2 + 1\)

(Discussed) \(T_5=T_1 + T_2  1\)
 (Solution) \(T_5\) will not necessarily be a stopping time. Suppose \(\{X_n:n \ge 0\}\) is the Markov Chain corresponding to the transition matrix \[P = \begin{matrix} & \mathbf 0 & \mathbf 1 \cr \mathbf 0 & 1/2 & 1/2 \cr \mathbf 1 & 0 & 1 \end{matrix}\] Suppose further that \(T_1 = \min\{n \ge 0: X_n = \mathbf 0\}\) and \(T_2 = \min\{n \ge 0: X_n = \mathbf 1\}\). If \(T_5\) were a stopping time we would have \(P(T_5 = n  X_n = x_n, \dots, X_0=x_0)\in \{0, 1\} \; \forall n\). However, by definition of \(T_5\)\[P(T_5 = 0  X_0=\mathbf 0) = P(T_1 + T_2 = 1  X_0=\mathbf 0)\] by directly enumerating the possibilities we see \[= P(T_1 = 1, T_2 = 0  X_0=\mathbf 0)\] \[+ P(T_1 = 0, T_2 = 1  X_0=\mathbf 0)\] and now using the Multiplication Rule \[= P(T_1 = 1  T_2 = 0, X_0=\mathbf 0)P(T_2 = 0  X_0=\mathbf 0)\] \[+ P(T_2 = 1  T_1 = 0, X_0=\mathbf 0)P(T_1 = 0  X_0=\mathbf 0)\] since \(T_1\) and \(T_2\) are stopping times this simplifies to \[= P(T_1 = 1  X_0=\mathbf 0)P(T_2 = 0  X_0=\mathbf 0)\]\[ + P(T_2 = 1  X_0=\mathbf 0)P(T_1 = 0  X_0=\mathbf 0)\] each term of which can be computed \[=0 \cdot 0 + \frac 1 2 \cdot 1\]\[= \frac 1 2 \notin \{0, 1\}\]


(Discussed) Solve problem 4(ii) on HW 2
 (Discussed) Show Lemma 1.3 from the textbook


Classification of States

Consider the Markov chain defined by the following transition matrix: \[P = \begin{matrix} & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 & \mathbf 7 & \mathbf 8 \cr \mathbf 1 & 0.5 & 0 & 0.5 & 0 & 0 & 0 & 0 & 0 \cr \mathbf 2 & 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0 & 0 \cr \mathbf 3 & 0 & 0 & 0 & 0.5 & 0 & 0 & 0 & 0.5 \cr \mathbf 4 & 0 & 0 & 0.5 & 0 & 0.5 & 0 & 0 & 0 \cr \mathbf 5 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \cr \mathbf 6 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \cr \mathbf 7 & 0 & 0 & 0 & 0 & 0 & 0.5 & 0 & 0.5 \cr \mathbf 8 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{matrix}\] Identify the transient and recurrent states, and the irreducible closed sets in the Markov chain. Give reasons for your answers.

Consider the Markov chain defined by the following transition matrix: \[P = \begin{matrix} & \mathbf 1 & \mathbf 2 & \mathbf 3 & \mathbf 4 & \mathbf 5 & \mathbf 6 \cr \mathbf 1 & 0 & 0 & 1 & 0 & 0 & 0 \cr \mathbf 2 & 0 & 0 & 0 & 0 & 0 & 1 \cr \mathbf 3 & 0 & 0 & 0 & 0 & 1 & 0 \cr \mathbf 4 & 0.25 & 0.25 & 0 & 0.5 & 0 & 0 \cr \mathbf 5 & 1 & 0 & 0 & 0 & 0 & 0 \cr \mathbf 6 & 0 & 0.5 & 0 & 0 & 0 & 0.5 \end{matrix}\] Identify the transient and recurrent states, and the irreducible closed sets in the Markov chain. Give reasons for your answers.


Stationary Distributions
Recall a stationary distribution is a vector \(\pi\) satisfying: \[\sum _i \pi(i)=1\] \[\pi(i)\ge 0, \quad \forall i\] \[\pi P = \pi\]

Compute any and all stationary distributions of \[P = \begin{bmatrix} 0 & 0 & 1 \cr 1 & 0 & 0 \cr 0 & 1 & 0 \end{bmatrix}\] If you claim \(P\) has a unique stationary distribution, please justify.

(Partially Discussed) Under what circumstances is the stationary distribution of \[P = \begin{bmatrix} 1r & 0 & r \cr p & 1p & 0 \cr 0 & q & 1q \end{bmatrix}\] unique? Justify your answer. Compute the stationary distribution in this case.

Compute any and all stationary distributions of \[P = \begin{bmatrix} 1 & 0 \cr 0 & 1 \end{bmatrix}\] If you claim \(P\) has a unique stationary distribution, please justify.

Compute any and all stationary distributions of \[P = \begin{bmatrix} P_1 & 0 \cr 0 & P_2 \end{bmatrix}\] where \(P_1\) has a unique stationary distribution \(\pi_1\) and \(P_2\) has a unique stationary distribution \(\pi_2\). If you claim \(P\) has a unique stationary distribution, please justify.

Compute any and all stationary distributions of \[P = \begin{bmatrix} 0 & p & 0 & 1p \cr q & 0 & 1q & 0 \cr 0 & 1r & 0 & r \cr 1s & 0 & s & 0 \end{bmatrix}\] If you claim \(P\) has a unique stationary distribution, please justify.
