Title: Part IB / Markov Chains
Tags: Invariant_Distribution Transience_Recurrence Markov_Chains_Introduction Communicating_Classes Convergence_To_Equilibrium Hitting_Times Time_Reversibility Ergodic_Theorem Powers_Of_Transition_Matrix Strong_Markov

Q: Definition. A stochastic process is called a Markov chain if for all \(n \geq 0\) and for all \(x_1 \dots x_{n+1} \in I\) [...]
A: \[\mathbb{P}(X_{n=1} = x_{n+1}| X_n = x_n, \dots X_1 = x_1) = \mathbb{P}(X_{n=1} = x_{n+1} | X_n = x_n)\]
Back Extra: They retain no memory of the past

Q: Definition. What is a time homogeneous Markov chain and what is the transition matrix?
A: \(\mathbb{P}(X_{n+1} = y | X_n = x )\) is independent of n \(\forall x,y\)

Q: Definition. What is a stochastic matrix?
A: When the sum of each row of the transition matrix is equal to 1.
\[\sum_{y \in I} P(x,y) = 1\]

Q: Definition. X is Markov(\(\lambda, P\)) if it has initial distribution \(\lambda\) and it has transition matrix P:
[...]
[...]
A: i) \(\mathbb{P}(X_0 = x) = \lambda(x) \forall x \in I \); ii) \(\mathbb{P}(X_{n+1} = x_{n+1} | X_n = x_n, \dots, X_0 = x_0) = P(x_n, x_{n+1})\)
Back Extra: The set I is called the state space of the Markov chain.

Q: Theorem. X is Markov\((\lambda, P)\) iff \(\forall n \geq 0\), \(\forall x_0, \dots, x_n \in I\)[...]
A: \[\mathbb{P}(X_0 = x_0, \dots, X_n = x_n) = \lambda(x_0)P(x_0,x_1) \dots P(x_{n-1}, x_n)\]
Back Extra: Use definition of conditional probability to go from left to right.
For the opposite direction use the left to show it gives the equation for the transition matrix.

Q: Theorem. Simple Markov Property. Suppose that X is Markov\((\lambda, P)\) with values in I and let \(m \in \mathbb{N}\). Then conditional on \(X_m = i\) the process \((X_{m+n})_{n \geq 0}\) is Markov\((\delta_i, P)\) and it is independent of \(X_0 \dots, X_m\).
A: First to show the process is Markov. We write \(\mathbb{P}(X_{m+n} = x_{m+n}, \dots , X_m = x_m | X_m = i)\) using the definition of conditional probability and using the law of total probability and the fact that X is Markov. We obtain \[\mathbb{P}(X_{m+n} = x_{m+n}, \dots , X_m = x_m | X_m = i) = \delta_{i x_m} p _{x_m x_{m+1}} \dots p_{x_{m+n-1} x_{m+n}}\]as required. Now to show it is inependent we want to show for some \(k \geq 0\) and \(x_1, \dots, x_{m-1}, x_{m+1}, \dots, x_{k+m} \in I\) and let \(m < i_1 \leq \dots \leq i_k\) \[\mathbb{P}(X_{i_1} = x_{m+1}, \dots , X_{i_k} = x_{k+m}, X_m = x_m , \dots , X_0 = x_0 | X_m = i) = \mathbb{P}(X_{i_1} = x_{m+1}, \dots , X_{i_k} = x_{k+m} | X_m = i)\mathbb{P}(X_m = x_m , \dots , X_0 = x_0 | X_m = i)\]We can use the definition of conditional probability, then the definition of what makes something Markov to rearrange into RHS.

Q: Theorem. Suppose that X is Markov(\(\lambda, P\)). Then for all \(n,m \geq 0\) and all \(x,y\) we have \[\mathbb{P}(X_n = x) = [...]\]\[\mathbb{P}(X_{n+m} = y | X_m = x) = [...]\]
A: (\lambda P^n)_x; p_{xy}(n)
Back Extra: \(p_{ij}(n)\) is the (i,j)th element of the n-th power of P.

Q: Definition. Let X be a Markov chain with transition matrix P and values in I. For two states x and y in I we say that x leads to y and write it \(x \to y\) [...]. We say x communicates with y if [...] and we denote it by \(x \leftrightarrow y\)
A: \[\mathbb{P}_x(X_n = y \text{ for some } n \geq 0) > 0\]; \(x \to y\) and \(y \to x\)

Q: Theorem. Let x and y be two states. Then the following are equivalent:
1) \(x \to y\)
2) there exists a sequence of states \(x_0 = x, x_1 \dots , x_k = y\) such that \(P(x_0, x_1) \dots P(x_{k-1}, x_k) > 0\)
3)there exists \(n \geq 0\) such that \(p_{xy}(n) > 0\)
A: (\(1 \iff 3\)) \[\{X_n = y \text{ for some } n\geq 0\} = \cup_{n \geq 0} \{X_n = y\}\]
So if \(\mathbb{P}_x(X_n = y \text{ for some} n \geq 0) > 0\), then there exists some \(n \geq 0\) such that \(\mathbb{P}_x(X_n = y) > 0\). Clearly if \(\mathbb{P}_x(X_n = y) > 0\) then \(x \to y\).
(\( 2 \iff 3\)) We have \[p_{xy}(n) = \sum_{x_1, \dots , x_{n-1}} P(x, x_1) \dots P(x_{n-1}, x_n)\]
Therefore the equivalence follows.

Q: Corollary. The relation \(\leftrightarrow\) defines an equivalence relation on I.
A: Clearly we have symmetry, also \(x \leftrightarrow x\) as \(n = 0, p_{xx}(0) = 1 > 0\). We can use a theorem that gives equivalent ways of writing \(x \to y\) to show transitivity.

Q: Definition. The equivalence classes induced by \( \leftrightarrow\) on I are called communicating classes. We say that a class C is closed if [...]. A transition matrix P is called irreducible if [...] A state x is called absorbing if [...]
A: whenever \(x \in C\) and \(x \to y\), then \(y \in C\); it has a single communicating class.; {x} is a closed class. In other words, the Markov chain starting from x always remains at x.

Q: Definition. The first hitting time of A by X is defined to be \(T_A : \Omega \to \{0,1, \dots\} \cup \{\infty\}\) [...]
A: \[T_A(\omega) = \inf \{n \geq 0 : X_n(\omega) \in A\}\]
Back Extra: \(\inf \emptyset  = \infty\)

Q: Definition. The hitting probability of A is defined to be the function \(h^A : I \to [0,1]\) given by [...]. The mean hitting time of A is defined to be the function \(k^A |: I \to \mathbb{R}_+ \cup \{\infty\}\) given by [...]
A: \[h_i^A = \mathbb{P}_i(T_A < \infty)\]; \[k_i^A = \mathbb{E}_i(T_A) = \sum_{n=0}^{\infty} n\mathbb{P}_i(T_A = n) + \infty \cdot \mathbb{P}_i(T_A = \infty)\]

Q: Theorem. Let \(A \subseteq I\). The vector of hitting probabilities \((h_i^A : i \in I)\) solves the following system of linear equations. \[ h_i^A = \left [ 1 \; \; \text{if } i  \in A, \sum_j P(i,j)h_j^A \; \text{otherwise} \right ]\]
Moreover, \((h_i^A)_{i \in I}\) is the minimal non-negative solution \((h_i^A \geq 0 \text{ for all i})\) to this system of equation in the sense that if \(x_i\) is another non-negative solution, then \(h_i^A \leq x_i\) for all \(i \in I\)
A: Rearranging stuff and using Markov property and conditional probability for first part.
For second part iterate over the states for some solution \(x_i\) and take limits.

Q: Theorem. The vector of mean hitting times is the minimal non-negative solution to the linear system \[k_i^A = \begin{cases} 0 \text{ if } i \in A \\ 1 + \sum_{j \not \in A} P(i,j) k_j^A, i \not \in A \end{cases}\]
A: If \(i \in A\) this is trivial. Suppose \(i \not \in A\). \[k_i^A = \mathbb{E}_i(T_A) = \sum_{n=0}^{\infty} \mathbb{P}_i(T_A > n) = 1 + \sum_{n=1}^{\infty} \mathbb{P}_i(T_A > n)\]
After simplifying and conditioning on \(X_1 = j\) and using the Markov property we have \[1 + \sum_{j \not \in A} P(i,j) \sum_{n=1}^{\infty} \mathbb{P}_j (X_0 \not \in A , \dots m X_{n-1} \not \in A) = 1 + \sum_{j \not \in A} P(i,j) \sum_{n=0}^{\infty} \mathbb{P}_j(T_A > n) = 1 + \sum_{j \not \in A}P(i,j) k_j^A\] So we know this is a solution and now we need minimality.
Again assume \(i \not \in A\). Now if we have some non-negative solution \(x_i\) then \[x_i = 1 + \sum_{j \not \in A} P(i,j)(1 + \sum_{k \not \in A} P(j,k)x_k) = \dots \]
Then using the fact that \(x_i\) is non-negative and and rewriting we get \[x_i \geq \sum_{k=0}^n \mathbb{P}_i(T_A > k) \to k_i^A\]

Q: Definition. A stopping time T is a random variable \(T : \Omega \to \{0,1, \dots\} \cup \{\infty\}\) with the property that [...]
A: \(\forall n, \{T = n\}\) depends only on \(X_0, \dots , X_n\)

Q: Definition. A state \(i \in I\) is called recurrent if [...] A state \(i \in I\) is called transient if [...]
A: \[\mathbb{P}_i (X_n = i \text{ for infinitely many n}) = 1\]; \[\mathbb{P}_i (X_n = i \text{ for infinitely many n}) = 0\]
Back Extra: This is in fact a dichotomy.

Q: Lemma. Let \(f_i = \mathbb{P}_i (T_i < \infty)\), and \(v_i = \sum_{l =0}^{\infty} 1(X_l = i) = \text{ total number of visits to i}\). We have \[\forall r, \mathbb{P}_i (v_i > r) = f_i^r\]
A: True for \(r = 0\) as \(\mathbb{P}_i (v_i > 0) = 1\)/ Suppose is holds for all \(r \leq k\), for \(r = k+1\), \[\mathbb{P}_i(v_i > k+1) = \mathbb{P}_i(T_i^{(k+1)} < \infty) = \mathbb{P}_i (T_i^{(k)} < \infty, T_i^{(k+1)} < \infty) = \mathbb{P}_i(T_i^{(k+1)} < \infty  | T_i^{(k)} < \infty) \cdot \mathbb{P}_i(T_i^{(k)} < \infty)\]
The \((T_i^{(k)})\) are stopppping times so by Strong Markov we have conditional on \( T_i^{(k)} < \infty\), the future is Markov\((\delta_i, P)\). So \(\mathbb{P}_i (T_i^{(k+1)} < \infty | T_i^{(k)} < \infty) = \mathbb{P}_i(T_i < \infty) = f_i\). Therefore we are done by induction.

Q: Theorem. Let \(i \in I\), we have the following dichotomy.
1) If \(\mathbb{P}_i (T_i < \infty) = 1\), then i is recurrent and \[\sum_{n \geq 0} p_{ii} (n) = \infty\]
2) If \(\mathbb{P}_i (T_i < \infty) < 1\), then i is transient and \[\sum_{n \geq 0} p_{ii} (n) < \infty\]
A: \(\mathbb{E}_i (v_i) = \mathbb{E}_i [\sum_{l=0}^{\infty} 1(X_l = i)] = \sum_{l=0}^{\infty} \mathbb{P}_i(X_l = 1) = \sum_{l = 0}^{\infty} p_{ii}(l)\)
1)If \(f_i = 1\), then we get \(\mathbb{P}_i(V_i = \infty) = 1 \implies \mathbb{E}_i(v_i) = \infty \implies \text{ i is recurrent}\)
2) If \(f_i < 1\), then we get \(\mathbb{E}_i (v_i) = \frac{1}{1 - f_i} < \infty \implies \mathbb{P}_i(v_i = \infty) = 0 \implies \text{ i is transient}\)

Q: Theorem. Let \(x,y \in I\) communicate, \(x \leftrightarrow y\). Then either they are both recurrent or both transient.
A: Suppose x is recurrent, we need to show y is then recurrent. We know \(\sum_{n=0}^{\infty} p_{xx}(n) = \infty\)\[x \leftrightarrow y \implies \exists l,m \geq 0 \text{ s.t. } p_{xy}(l) \cdot p_{yx}(m) > 0\] \[\sum_n p_{yy}(x) \geq \sum_n p_{yy}(n + m + l) \geq \sum_n p_{yx}(m) \cdot p_{xx}(n) \cdot p_{xy}(l) = p_{yx}(m) p_{xy}(l) \sum_n p_{xx}(n) = \infty \implies \text{ y is also recurrent.}\]

Q: Theorem. If C is a recurrent communicating class, then it must be closed.
A: Suppose C is not close. Then there must exists \(x \in C\) and \(y \not \in C\) s.t. \(x \to y\)\[\exists m \geq 0 \text{ s.t } p_{xy}(m) > 0\] \[\mathbb{P}_x (v_x < \infty) \geq \mathbb{P}_x (X_m = y) > 0 \text{ since } y \not \to x\]
So \(\mathbb{P}_x(v_x < \infty\ ) > 0\) and thus contradicts the assumption that x is recurrent.

Q: Theorem. A finite closed class is recurrent.
A: Let C be a finite closed class. Start from x. By the pigeonhole principle \(\exists y \in C\) \[\mathbb{P}_x (X_n = y \text{ for infinitely many n}) > 0\]
\(\exists m \geq 0 \) s.t. \(p_{yx}(m) > 0\) \[\mathbb{P}_y (X_n = y \text{ for infinitely many n}) \geq \mathbb{P}_y(X_m = x, X_n = y \text{ for infinitely many } n \geq m) = \mathbb{P}_y(X_n = y \text{ for infinitely many } n\geq m | X_m = x) \mathbb{P}_y(X_m = x) = \mathbb{P}_x (X_n = y) \text{ for infinitely many n } \cdot p_{yx}(m) > 0\] SO we showed \[\mathbb{P}_y (v_y = \infty) > 0\] but by the dichotomy we get that this probability must be 1 so y is recurrent and therefore all states recurrent.

Q: Theorem. Let P be irreducible and recurrent. Then \(\forall x,y \; \; \mathbb{P}_x (T_y < \infty) = 1\) where \(T_y = \inf \{n \geq 1 : X_n = y\}\)
A: \(\mathbb{P}_y (X_n = y \text{ for infinitely many n}) = 1\)
\(\exists m \geq 0\) s.t. \(p_{yx}(m) > 0\) as it is irreducible.
\(\mathbb{P}_y(X_n = y \text{ for inf. many n}) = \sum_z p_{yz}(m) \mathbb{P}_z (X_n = y \text{ for inf n})\) using simple Markov at m
This is the same as \(\sum_z \mathbb{P}_y(X_m = z, X_n = y \text{ for inf. } n \geq m)\) which is equal to 1.
As \(p_{yx}(m) > 0\) we must have \(\mathbb{P}_x (X_n = y \text{ for inf many n}) = 1\)
\(\mathbb{P}_x (X_n = y \text{ for inf many n}) = \mathbb{P}_x(T_y < \infty, X_n = y \text{ for inf many }n \geq T_y) = \mathbb{P}_x (X_n = y \text{ for inf many } n \geq T_y | T_y < \infty) \cdot \mathbb{P}_x(T_y < \infty)\) using Strong Markov at \(T_y\)
\( = \mathbb{P}_y(X_n = y \text{ for inf many n}) \mathbb{P}_x (T_y < \infty) = \mathbb{P}_x(T_y < \infty) \implies \mathbb{P}_x(T_y < \infty) = 1\)

Q: Definition. A simple symmetric random walk on \(\mathbb{Z}^d\) is the Markov chain with matrix [...]
A: \[P(x , x + e_i) = P(x, x - e_i) = \frac{1}{2d}\]

Q: Theorem. Simple random walk on \(\mathbb{Z}^d\) is recurrent if \(d = 1,2\).
A: (d = 1)\(\mathbb{P}_0 (X_{2n} = 0) = {2n \choose n} \cdot \frac{1}{2}^{2n} = \frac{(2n)!}{n!n!} \cdot \frac{1}{2^{2n}}\).
Using Stirlings formula tells us \(\mathbb{P}_0 (X_{2n} = 0) \sim \frac{1}{\sqrt{\pi n}}\) and therefore summing over n gives us infinity and we are done.
In fact in an asymmetric walk, we get \(\mathbb{P}_0(X_{2n} = 0) = {2n \choose n} \cdot p^n \cdot q^n \sim \frac{(4pq)^n}{\sqrt{\pi n}}\) so the sum over n is less than or equal to \(\sum_n (4pq)^n\), but if \(p \neq q\) and \(p +q = 1\) then \(4pq < 1\) and therefore the sum is finite and the assymetric walk is transient.
(d=2)
\(f(x,y) = \left ( \frac{x+y}{\sqrt{2}} , \frac{x-y}{\sqrt{2}}\right )\). \(X_n\) is a SRW on \(\mathbb{Z}^2\)
\(f(X_n) = (X_n^+, X_n^-)\), and \(X_n = 0 \iff X_n^+ = X_n^- = 0\).
\(X_n^+, X_n^-\) are independent SRW's on \(\mathbb{X}/\sqrt{2}\). (proof is long)
And so \[\sum_n \mathbb{P}_o (X_{2n} = 0) = \sum_n \mathbb{P}_0 (X_{2n}^+ = 0, X_{2n}^- = 0) = \sum_n \mathbb{P}_0 (X_{2n}^+ = 0) \cdot \mathbb{P}_0(X_{2n}^- = 0) \sim \sum_n \frac{1}{n} = \infty\].

Q: Definition. A probability distribution \(\pi = (\pi_i : i \in I)\) is called an invariant/equilibrium/stationary distribution for P if [...]
A: \[\pi = \pi P\]

Q: Theorem. Let X be a Markov chain with matrix P and invariant distribution \(\pi\). Then if \(X_0 \sim \pi, \forall n \; X_n \sim \pi\)
A: True for n = 0. Assume \(X_n \sim \pi\).
\[\mathbb{P}(X_{n+1} = j) = \sum_i \mathbb{P}(X_n = i , X_{n+1} = j) = \sum_i \mathbb{P}(X_n = i)P(i,j) = \sum_i \pi_i P(i,j) = \pi_j\]

Q: Theorem. Suppose that I is a finite state space and suppose that there exists \(i \in I\) such that for all j \[p_{ij}(n) \to \pi_j \text{ as } n \to \infty\] Then \(\pi = (\pi_j : j \in I)\) is an invariant distribution.
A: We show first that \(\pi\) is a probability distribution. Indeed we have \[\sum_{j \in I} \pi_j = \sum_{j \in I} \lim_{n \to \infty}p_{ij}(n) = \lim_{n \to \infty}\sum_{j \in I} p_{ij}(n) = 1\]
Now we prove that \(\pi = \pi P\). Let \(j \in I\). We have \[\pi_j = \lim_{n \to \infty} p_{ij}(n) = \lim_{n \to \infty} \sum_k p_{ik}(n-1) P(k,j) = \sum_k \lim_{n \to \infty} p_{ik}(n-1) P(k,j) = \sum_k \pi_k P(k,j)\]

Q: Definition. \(\lambda = (\lambda_i : i \in I)\) is called a measure if [...]. \(\lambda\) is called an invariant measure if [...]
A: \(\lambda_i \geq 0 \; \; \forall i\); \(\lambda = \lambda P\)

Q: Definition. Let \(k \in I\). Recall \[T_k = \inf \{n \geq 1 : X_n = k\}\] We define \[v_k (i) = [...]\]
A: \mathbb{E}_k \left [ \sum_{n=0}^{T_k - 1} \mathbb{1} (X_n = i)\right ]
Back Extra: The expected number of times the Markov chain visits the state i during an excursion from k.

Q: Theorem. Suppose P is irreducible and recurrent. Then \(v_k\) is an invariant measure, \(v_k = v_k P\) and \(0 < v_k (i) < \infty \; \forall i \in I \) and \(v_k(k) = 1\)
A: P recurrent implies \(T_k < \infty\) with probability 1 and \(X_{T_k} = k\).
\(v_k(i) = \mathbb{E}_k \left [ \sum_{n=1}^{T_k} 1(X_n = i) \right ] = \mathbb{E}_k \left [\sum_{n=1}^{\infty} 1(X_n = i)1( n \leq T_k)\right ]\)
\(= \sum_{n=1}^{\infty} \mathbb{P}_k(X_n = i, n \leq T_k) = \sum_{n=1}^{\infty} \sum_{j \in I} \mathbb{P}_k (X_n = i, X_{n-1} = j, n \leq T_k)\)
\( = \sum_{n=1}^{\infty} \sum_{j \in I} \mathbb{P}_k (X_n = i | X_{n-1} = j , n \leq T_k) \mathbb{P}_k (X_{n-1} = j, n \leq T_k)\)
\(T_k \geq n\) depends only on \(X_0, \dots , X_{n-1}\).
By the simple Markov property we get \[\mathbb{P}_k(X_n = i | X_{n-1} = k, n \leq T_k) = \mathbb{P}_k(X_n = i | X_{n-1} = j) = P(j,i)\]
So \(v_k (i) = \sum_{j \in I} P(j,i) \sum_{n=1}^{\infty} \mathbb{P}_k(X_{n-1} = k, n \leq T_k) = \sum_{n=0}^{\infty} \mathbb{P}_k (X_n = j, n+1 \leq T_k) = v_k(j)\)
So \(v_k(i) = \sum_j P(j,i) v_k(j) \implies v_k = v_k P\)
\(v_k (k) = 1\)
\(v_k = v_k P \implies v_k = v_k P^n \; \forall n\)
\(1 = v_k(k) = \sum_j v_k(j) P^m (j,k) \geq v_k (i) = p_{ik}(m)\)
P is irreducible so exists m s.t. \(p_{ik}(m) > 0 \implies v_k (i) \leq \frac{1}{P_{ik}(m)} < \infty\)
\(v_k(i) = \sum_j v_k(j)P^n(j,i)\)
exists l for which \(p_{ki}(l) > 0\)
Therefore \(v_k(i) \geq v_k(k) p_{ki}(l) = p_{ki}(l) > 0\).

Q: Theorem. Let P be irreducible and let \(\lambda\) be an invariant measure with \(\lambda_k = 1\). Then \(\lambda \geq v_k\). If P is recurrent, then \(\lambda = v_k\).
A: \(\lambda_k = 1 = v_k(k)\)
Let \(i \in I\) with \(i \neq k\). NTS \(\lambda_i \geq v_k(i)\)
\(\lambda = \lambda P \implies \lambda_i = \sum_j \lambda_j P(j,i) \implies \lambda_i = P(k,i) + \sum_{j_1 \neq k} \lambda_{j_1} P(j_1 , i) = P(k,i) + \sum_{j_1 \neq k} P(k, j_1)P(j_1, i) + \sum_{j_1 , j_2 \neq k} P(j_2 , j_1) P (j_1 , i) \lambda_{j_2}\)
Repeating this we get \[\lambda_i = P(k,i)+ \dots + \sum_{j_1 , \dots , j_n \neq k}P(j_n , j_{n-1}) \dots P(j_1, i) \lambda_{j_n}\]
So \[\lambda_i \geq \mathbb{P}_k (X_1 = i , T_k \geq 1) + \mathbb{P}_k (X_2 = i ,T_k \geq 2) + \dots + \mathbb{P}_k (X_n = i , T_k \geq n) = \sum_{l=1}^n \mathbb{P}_k (X_l = i, T_k \geq l) \to \sum_{l=1}^{\infty} \mathbb{P}_k (X_j = i, T_k \leq l)\]
\(i \neq k, v_k(i) = \sum_{l=1}^{\infty} \mathbb{P}_k(X_l = i, T_k \geq l)\)
So \(\lambda_i \geq v_k (i)\).
If P is recurrent we want to show \(\lambda_i - v_k(i) = 0\) for all i. Basically just condition off the k case for which we know it's true.

Q: Definition. Let \(i \in I\) be a recurrent state, \(T_i = \inf \{n \geq 1 : X_n = i\}\). We call i positive recurrent if [...]. If [...] we call i null recurrent.
A: \(\mathbb{E}_i [T_i] < \infty\); \(\mathbb{E}_i[T_i] = \infty\)

Q: Theorem. Suppose that P is irreducible. The following are equivalent:
1) every state is positive recurrent
2) some state is positive recurrent
3) there exists an invariant distribution \(\pi\)
If any of the above holds then, \(\pi_i = \frac{1}{\mathbb{E}_i [T_i]}\)
A: (1 -> 2) is trivial.
(2 -> 3) Suppose k is the positive recurrent state. \(v_k\) is invariant \[\sum_i v_k (i) = \mathbb{E}_k [T_k] < \infty \implies \pi_i = \frac{v_k (i)}{\mathbb{E}_k [T_k]}\] defines an invariant distribution.
(3 - > 1) \(\pi\) is an invariant distribution. Let \(k \in I\). NTS k is positive recurrent which is true iff \(\mathbb{E}_k [T_k] < \infty\).
First lets show \(\pi_k > 0\).
\(\pi\) is a distribution so \(\exists i \in I\) s.t. \(\pi_i > 0\) \[\pi_k \sum_j P^m (j,k)\pi_j \geq p_{ik}(m) \pi_i > 0 \text{ as } \exists m : p_{ik}(m) > 0\]
Define \(\lambda_i = \frac{\pi_i}{\pi_k}\) invariant measure of P.
So \(\lambda_k = 1 \implies \lambda \geq v_k \implies \lambda_i \geq v_k(i) \; \forall i\)
\(\mathbb{E}_k[T_k] = \sum_i v_k (i) \leq \sum_i \lambda_i = \sum_i \frac{\pi_i}{\pi_k} = \frac{1}{\pi_k}\) so \(\mathbb{E}_k[T_k] < \infty\).
We NTS \(\pi_k = \frac{1}{\mathbb{E}_k [T_k]}\).
k is positive recurrent, \(\lambda_i = \frac{\pi_i}{\pi_k}\) as it is an invariant measure, \(\lambda_k = 1\).
P recurrent implies \(\lambda = v_k \implies \mathbb{E}_k[T_k] = \sum_{i \in I}v_k(i) = \sum_{i \in I} \lambda_i = \sum_i \frac{\pi_i}{\pi_k} = \frac{1}{\pi_k}\)

Q: Lemma. Let X be a MC with P irreducible and has invariant distribution \(\pi\). Fix \(N \in \mathbb{N}\) and suppose that \(X_0 \sim \pi\). Then the process \((Y_n)_{0 \leq n \leq N}\) defined via \(Y_n = X_{N-n}\) is a Markov chain with transition matrix \[\hat{P}(x,y) = \frac{\pi(y)}{\pi(x)} P(y,x)\]
Moreover \(\hat{P}\) is irreducible and has invariant distribution \(\pi\)
A: First check that it is a transition matrix. \[\sum_y \hat{P}(x,y) = \sum_y \frac{\pi(y)}{\pi(x)} P (y,x) = \frac{\pi(x)}{\pi(x)} = 1\] where we have used that \(\pi\) is invariant.
Next show Y is a Markov chain. \[\mathbb{P}(Y_0 = y_0, \dots Y_N = y_N) = \mathbb{P}(X_N = y_0, \dots , X_0 = y_N) = \pi(y_N)P(y_N, y_{N-1}) \dots P(y_1 , y_0) = \pi(y_0)\hat{P}(y_0, y_1) \dots \hat{P}(y_{N-1}, y_N)\]
which shows that Y is Markov(\(\pi, \hat{P}\)).
Now let \(x,y\) be two states to show \(\hat{P}\) is irreducible. THen there exists a sequence of states \(x_0 = x, x_1, \dots , x_k = y\) such that \(P(x_0, x_1) \dots P(x_{k-1}, x_k) > 0\). But \[\hat{P}(x_k , x_{k-1}) \dots \hat{P}(x_1, x_0) = \pi(x_0)P(x_0 , x_1) \dots P(x_{k-1}, x_k)/\pi(x_k) > 0\]
Also \(\sum_x \pi(x) \hat{P}(x,y) = \sum_x \pi(x) \cdot \frac{\pi(y)}{\pi(x)} P(y,x) = \sum_x \pi(y) P(y,x) = \pi(y)\) so \(\pi\) is invariant for \(\hat{P}\).

Q: Definition. X is called time reversible if [...]
A: \(\hat{P} = P\). Equivalently, if \(\forall N \in \mathbb{N}\) when \(X_0 \sim \pi\), then \((X_0, \dots , X_N) \sim (X_N , \dots , X_0)\).

Q: Lemma. Suppose that \(\mu\) is a distribution satisfying \[\mu(x)P(x,y) = \mu(y)P(y,x)\] for all \(x,y\). Then \(\mu\) is an invariant distribution for P.
A: Taking the sum over all x of both sides of the equality of the statement we get \[\sum_x \mu(x) P(x,y) = \sum_x \mu(y) P(y,x) = \mu(y)\] where we used that P is a stochastic matrix, therefore \(\mu = \mu P\) which means that \(\mu\) an invariant distribution.

Q: Definition. Let P be a transition matrix and \(i \in I\). The period of i [...] If \(d_i = 1\) then i is called aperiodic.
A: \(d_i = \text{gcd} \{ n \geq 1: P^n(i,i) > 0\}\).

Q: Lemma. Let P be a transition matrix and i a state. Then \(d_i = 1\) iff \(P^n(i,i) > 0\) for all n large enough.
A: It is clear that if \(P^n(i,i) > 0\) for all n sufficiently large, then \(d_i = 1\).
Suppose next that \(d_i = 1\) and set \(D(i) = \{n \geq 1: P^n(i,i) > 0\}\). We first show that D(i) contains two consecutive integers. First of all if \(m,n \in D(i)\) then so is m+n.
Suppose now that the minimum distance between any two elements of D is \(r \geq 2\) and let \(n,m \in D(i)\) with \(n = m + r\). Let also \(k \in D(i)\) with \(k = lr+s\) with \(l \in \mathbb{N}\) and \(0 < s < r\), which exists since otherwise only multiples of r would be contained in \(D(i)\) and this would contradict that g.c.d\((D(i)) = 1\).
Letting \(a = (l+1)n\) and \(b = (l+1)m+k\) we see that both a and b are contained in D and \(a-b = r-s \in (0,r)\) and this contradicts the definition of r as the minimum distance between any two elements of D. Therefore D contains two consecutive numbers \(n_1, n_1+1\).
Since \(an_1 + b(n_1 + 1) \in D(i)\) for all a,b it easily follows that D contains all n sufficiently large and this completes the proof.

Q: Lemma. Let P be an irreducible transition matrix and let i be an aperiodic state. Then all states are aperiodic.
A: Let j be another state. Since i and j communicate there exists \(m,n \geq 0\) such that \(P^n(j,i) > 0\) and \(P^m(i,j) > 0\). Then for all \(s \geq 0\) sufficiently large we have \[P^{s+n+m}(j,j) \geq P^n(j,i)P^s(i,i)P^m(i,j) > 0\] which shows that \(P^l(j,j)\) is positive for all l sufficiently large, and hence j is also aperiodic.

Q: Theorem. Let P be irreducible and aperiodic with invariant distribution \(\pi\). Let \(X \sim \text{Markov}(\lambda , P)\). Then \(\forall y\) \[\lim_{n \to \infty} \mathbb{P}(X_n = y) = \pi(y)\] In particular, for all x,y taking \(\lambda = \delta_x\), we have \[\lim_{n \to \infty}P^n(x,y) = \pi(y)\]
A: The general idea is we define a Markov chain \((Y_n) \sim \text{Markov}(\pi , P)\) independent of X. Then define the process \((X_n, Y_n)\) on \(I \times I\), with initial distribution \(\lambda \times \pi\) and transition matrix given by \[\hat{P}((x_1, x_2), (y_1,y_2)) = P(x_1,y_1)P(x_2,y_2)\]
We then show it is irreducible using irreducibility and aperiodicity of P. Then we let T be the time at which X = Y. Then we also show \(\hat{\pi}(x,y) = \pi(x)\pi(y)\) is invariant for \(\hat{P}\), so now we know it is positive recurrent.
Now we define Z which is X before time T and Y after T. Now we show this is Markov(\(\lambda, P\)). Now we do some rearranging and get \[|\mathbb{P}(X_n = y) - \pi(y)| = |\mathbb{P}(Z_n = y) - \mathbb{P}(Y_n = y)| = |\mathbb{P}(X_n = y, T > n) + \mathbb{P}(Y_n = y, Y \leq n) - \mathbb{P}(Y_n = y, T > n) - \mathbb{P}(Y_n = y, T \leq n)| = |\mathbb{P}(X_n = y, T > n) - \mathbb{P}(Y_n = y, T > n)| \leq \mathbb{P}(T > n)\] and we know \(\mathbb{P}(T > n)\) tends to 0 as we have a finite hitting time so we complete the proof.

Q: Theorem. Let P be an irreducible and positive recurrent matrix with invariant distribution \(\pi\). Suppose that X starts according to a distribution \(\lambda\). Then for all x we have almost surely \[\frac{1}{n} \sum_{i=0}^{n-1} \mathbf{1}(X_i = x) \to \pi (x) \text{ as } n \to \infty\]
A: Let \(V_n(x) = \sum_{i=0}^{n-1} \mathbf{1}(X_i = x)\) for the total number of visits to x up to time n-1. Also recall the definition of the successive times at which X visits x: first we set \(T_x^{(0)} = 0\) and for \(k \geq 1\) inductively we set \[T_x^{(k+1)} = \inf \{n \geq T_x^{(k)} + 1 : X_n = x\}\] By recurrence we have \(\mathbb{P}(T_x < \infty) = 1\), by strong Markov property we have \[(X_{T_x + n})_{n \geq \infty}\] is Markov(\(\delta_x, P\)) independent of \(X_0 , \dots , X_T\). Since \(T_x < \infty\) it suffices to consider the case when \(\lambda = \delta_x\).
Define the successive excursion lengths from x by setting \[S_x^{(k)} = T_x(k) - T_x^{(k-1)}\] if \(T_x^{(k-1)} < \infty\) and 0 otherwise. By the definition of the return times we have \[T_x^{(V_n(x) - 1)} \leq n-1\] and \[T_x^{(V_n(x))} \geq n\]. Also \[T_x^{(V_n(x) - 1)} = S_x^{(1)} + \dots + S_x^{(V_n(x) - 1)}\] So the same inequalities apply to this sum. Divide everything by \(V_n(x)\) to get \[\frac{S_x^{(1)} + \dots + S_x^{(V_n(x) - 1)}}{V_n(x)} \leq \frac{n}{V_n(x)} \leq \frac{S_x^{(1)} + \dots + S_x^{(V_n(x))}}{V_n(x)}\] By recurrence, \(V_n(x) \to \infty\) as \(n \to \infty\) with probability 1. The strong law of large numbers asserts that \[\frac{S_x^{(1)} + \dots S_x^{(k)}}{k} \to \mathbb{E}(S_1^{(k)})\] as these are i.i.d. So we decide that \[\lim_{n \to \infty} \frac{V_n(x)}{n} = \frac{1}{m_x} = \pi (x)\]