Title: Markov Chains

Q: Markov chain
A: Let $X = (X_0, X_1, \cdots)$ be a sequence of random variables taking values in some set $S$, the \emph{state space}, which is taken to be countable.
  We say $X$ has the \emph{Markov property} if for all $n\geq 0, i_0,\cdots, i_{n + 1}\in S$, we have
  \[
    \P(X_{n + 1} = i_{n + 1} \mid X_0 = i_0, \cdots, X_n = i_n) = \P(X_{n + 1} = i_{n + 1} \mid X_n = i_n).
  \]
  If $X$ has the Markov property, then we call it a \emph{Markov chain}.
  We assume \emph{homogeneity} i.e. the conditional probabilities $\P(X_{n + 1} = j \mid X_n = i)$ do not depend on $n$.

Q: Initial distribution
A: The initial distribution is $\lambda_i = \P(X_0 = i)$. We can write this as a vector $\lambda = (\lambda_i: i \in S)$.
Since $\lambda_i$ is a probability distribution, it is a distribution i.e. $\lambda_i\geq 0$ and $\sum_i\lambda_i=1$.

Q: Transition probabilities
A: The transition probabilities $p_{i, j} = \P(X_{n + 1} = j \mid X_n = i)$. We can write this as a matrix $P = (p_{i, j})_{i, j\in S}$.
Now $p_{i, j} \geq 0$ since $p_{ij}$ is a probability. We also have
      \[
        \sum_j p_{i,j} = \sum_j \P(X_{1} = j \mid X_0 = i) = 1
      \]
      since $\P(X_1 = \ph \mid X_0 = i)$ is a probability distribution function.
Hence $P$ is a \emph{stochastic matrix}, i.e. it is non-negative and the rows sum to $1$.

Q: Markov chain determination
A: Let $\lambda$ be a distribution (on $S$) and $P$ a stochastic matrix. Let $X = (X_0, X_1, \cdots)$ be a chain and $A_k$ be the event $X_k = i_k$. $X$ is a MC with initial distribution $\lambda$ and transition matrix $(p_{ij})$ iff
  \[
    \P\left(\bigcap_{j=0}^n A_j\right) = \lambda_{i_0}p_{i_0, i_1}p_{i_1, i_2}\cdots p_{i_{n - 1}, i_n}. \tag{$*$}
  \]
  for all $n, i_0, \cdots, i_n$
\begin{proof}
  ($\Rightarrow$) When $n = 0$, $(*)$ says $\P(A_0) = \lambda_{i_0}$. This is true by definition of $\lambda$.
  Assume $(*)$ for all $n < N$. Then
  \begin{align*}
    \P\left(\bigcap_{j=0}^N A_j\right) &= \P\left(\bigcap_{j=0}^{N-1} A_j\right) \P\left( \left.\bigcap_{j=0}^{N} A_j\right| \bigcap_{j=0}^{N-1}A_j \right) \\
    &= \lambda_{i_0} p_{i_0, i_1}\cdots p_{i_{N - 2}, i_{N - 1}} \P(A_{N} \mid \bigcap_{j=0}^{N-1}A_j)\\
    &= \lambda_{i_0} p_{i_0, i_1}\cdots p_{i_{N - 2}, i_{N - 1}} \P(A_{N} \mid A_{N - 1})\\
    &= \lambda_{i_0} p_{i_0, i_1}\cdots p_{i_{N - 2}, i_{N - 1}} p_{i_{N - 1}, i_N}
  \end{align*}
  by the Markov condition, so done by induction.
  ($\Leftarrow$) For $n = 0$, we have $\P(A_0) = \lambda_{i_0}$. Otherwise,
  \begin{align*}
   \P\left(A_n \mid \bigcap_{j=0}^{n-1} A_j\right)&= \frac{\P(A_0\cap \cdots \cap A_n)}{\P(A_0\cap \cdots \cap A_{n - 1})}\\
    &= p_{i_{n - 1}, i_n}
  \end{align*}
  which is independent of $i_0, \cdots, i_{n - 2}$. So this is Markov with transition matrix $(p_{ij})$ and initial distribution $\lambda$.
\end{proof}

Q: Chapman-Kolmogorov equation
A: \begin{thm}
The $m+n$-step transition probability is given by
  \[
    p_{i, j}(m + n) = \sum_{k\in S} p_{i, k}(m) p_{k, j}(n).
  \]
Equivalently, in terms of a transition matrix multiplication:
\[
  P(m + n) = P(m)P(n).
\]
\end{thm}
\begin{proof}
Using the Extended Markov Property
\begin{align*}
  p_{ij}(m + n) &= \P(X_{m + n}\mid X_0 = i)\\
  &= \sum_k \P(X_{m + n} = j\mid X_m = k, X_0 = i)\P(X_m = k\mid X_0 = i)\\
  &= \sum_k \P(X_{m + n} = j\mid X_m = k)\P(X_m = k \mid X_0 = i)\\
  &= \sum_k p_{i, k}(m)p_{k, j}(n).
\end{align*}
\end{proof}

Q: Computing the $n$-step transition matrix
A: By the Chapman-Kolmogorov equation
\[
  P(n) = P(1)P(n - 1) = \cdots = P(1)^n = P^n.
\]
We now have two possible methods to calculate $P^n$.
\begin{enumerate}
\item Solve $\det(P-\lambda I)=0$ for the eigenvalues. Then we can write $P=R\diag(\lambda_1,\ldots)R^{-1}$ for the matrix of eigenvectors $R$. So $P^n=R\diag(\lambda_1^n,\ldots)R^{-1}$. Now if you don't want to compute $R$, then you can write $P(n)_{11}$ as a linear combination of $\lambda_i^n$ and solve for the coefficients using small values of $n$.
\item We can write down a recurrence relation
  \begin{align*}
    p_{1, 1}(n + 1) &= p_{1, 1}(n)p_{11}+ p_{1, 2}(n)p_{21} +\ldots \\
&= p_{1, 1}(n)p_{11}+ (1-p_{11})(n)p_{21} +\ldots
  \end{align*}
This can be solved with standard methods for difference equations.
\end{enumerate}
The other components can be obtained by symmetry and stochasiticity or similar methods.

Q: Communicating Classes
A: Given two states $i, j\in S$, we write $i \to j$ if $\exists n \geq 0$ such that $p_{i, j}(n) > 0$.
  We write $i \leftrightarrow j$ if $i \to j$ and $j \to i$. If $i \leftrightarrow j$, we say $i$ and $j$ \emph{communicate}.
\begin{prop}
  $\leftrightarrow$ is an equivalence relation. The equivalence classes of $\leftrightarrow$ are \emph{communicating classes}.
\end{prop}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item Reflexive: we have $i \leftrightarrow i$ since $p_{i, i}(0) = 1$.
    \item Symmetric: if $i\leftrightarrow j$, then $i\to j$ and $j\to i$ so $j\leftrightarrow i$.
    \item Transitive: suppose $i \to j$ and $j \to k$. Then $\exists m,n \geq 0$ such that $p_{i, j}(m) > 0$ and $p_{j, k}(n) > 0$. Hence
\begin{align*}
p_{i, k}(m + n) &= \sum_{r} p_{i, r}(m)p_{r k}(n) \\
&\geq p_{i, j}(m)p_{j, k}(n)\\
&> 0.
\end{align*}
So $i \to k$. Similarly, if $j \to i$ and $k \to j$, then $k \to i$.
  \end{enumerate}
\end{proof}

Q: Irreducible chain
A: A Markov chain is \emph{irreducible} if there is a unique communication class.
\begin{prop}
Let $X$ be a MC with finite communicating classes. Then $\exists N\in\N$ such that $(X_n)_{n\geq N}$ lies in a single communication class.
\end{prop}
\begin{proof}
Suppose $\exists a_k\geq 0$ such that $(X_n)_{n\geq a_k}$ has $k\in\N$ communicating classes $\{ C_1, \ldots C_k \}$.
If $(X_n)_{n\geq a_k}$ lies in a single class, then done.
Otherwise, wlog letting $X_{a_k}=x_k\in C_k$, $\exists a_{k-1}>a_k$ such that $X_{a_{k-1}}=x_{k-1}\not\in C_k$. Then $x_k\to x_{k-1}$ so $x_{k-1}\not\to x_k$. So $(X_n)_{n\geq a_{k-1}}$ lies in $k-1$ communicating classes $\{ C_1, \ldots C_{k-1} \}$.
So done by induction where $N=a_1$.
\end{proof}
Hence we can wlog take such chains to be irreducible.

Q: Closed subset of the state space
A: A subset $C\subseteq S$ is \emph{closed} if for all $i \in C, j\not\in C:p_{i, j} = 0$.
\begin{prop}
  A subset $C$ is closed iff
\[
i\in C, i\to j \implies j \in C \tag{$*$}
\]
\end{prop}
\begin{proof}
  Assume $C$ is closed, $i \in C, i \to j$. Since $i \to j$, $\exists m\geq 0$ such that $p_{i, j}(m) > 0$. Expanding the Chapman-Kolmogorov equation, we have
  \[
    p_{i, j}(m) = \sum_{i_1, \cdots, i_{m - 1}} p_{i, i_1}p_{i_1, i_2}, \cdots, p_{i_{m - 1},j} > 0.
  \]
  So there is some route $i, i_1, \cdots, i_{m - 1}, j$ such that $p_{i, i_1}, p_{i_1, i_2}, \cdots, p_{i_{m - 1}, j} > 0$. Since $p_{i, i_1} > 0$, we have $i_1\in C$. Since $p_{i_1,i_2} > 0$, we have $i_2\in C$. By induction, we get that $j \in C$.
 Conversely, assume $(*)$. Then for any $i\in C, j\not\in C$, we must have $i\not\to j$. So in particular $p_{i, j} = 0$.
\end{proof}

Q: Absorbing state
A: A state $i$ is absorbing if $\{ i \}$ is a closed class.

Q: First passage time and probability
A: The \emph{first passage time} of $j \in S$ starting from $i$ is
  \[
    T_j = \min\{n \geq 1: X_n = j\}.
  \]
  The \emph{first passage probability} is
  \[
    f_{ij}(n) = \P_i(T_j = n).
  \]

Q: Recurrent state
A: A state $i\in S$ is \emph{recurrent} (or \emph{persistent}) if
  \[
    \P_i (T_i < \infty) = 1,
  \]
  ie. we will eventually get back to the state. Otherwise, we call the state \emph{transient}.

Q: Convolution of first passage and transition probabilities
A: \begin{thm}
  \[
    P_{ij}(s) = \delta_{ij} + F_{ij}(s)P_{jj}(s),
  \]
  for $-1 < s \leq 1$.
\end{thm}
\begin{proof}
  Using the law of total probability
  \begin{align*}
    p_{ij}(n) &= \sum_{m = 1}^n \P_i(X_n = j\mid T_j = m) \P_i(T_j = m) \\
    &= \sum_{m = 1}^n \P(X_n = j\mid X_m = j) \P_i(T_j = m)\\
    &= \sum_{m = 1}^n p_{jj}(n - m) f_{ij}(m) \\
 \sum_{n = 1}^\infty p_{ij}(n) s^n &= \sum_{n = 1}^\infty \sum_{m = 1}^n p_{jj}(n - m)s^{n - m} f_{ij}(m)s^m \\
&= \sum_{1\leq m \leq n \leq \infty} p_{jj}(n - m)s^{n - m} f_{ij}(m)s^m \\
&= \sum_{m=1}^\infty f_{ij}(m)s^m \sum_{n=m}^\infty p_{jj}(n - m)s^{n - m}  \\
&= \sum_{m=1}^\infty f_{ij}(m)s^m \sum_{r=0}^\infty p_{jj}(r)s^{r}  \\
P_{ij}(s) - p_{ij}(0) &= (F_{ij}(s)-f_{ij}(0)) P_{jj}(s) \\
P_{ij}(s) - \delta_{ij} &= F_{ij}(s)P_{jj}(s) .
\end{align*}
\end{proof}

Q: Series condition for recurrence
A: \begin{thm}
  $i$ is recurrent iff $\sum_n p_{ii}(n) = \infty$.
\end{thm}
\begin{proof}
 Recall that for $|s|<1$
\[
P_{ij}(s)-\delta_{ij}=F_{ij}(s)P_{ij}(s).
\]
 Substituting $j = i$ gives
  \[
    P_{ii}(s) = \frac{1}{1 - F_{ii} (s)}
  \]
  where
\begin{align*}
F_{ii}(s) &=  \sum_{n = 1}^\infty f_{ii}(n) s^n \\
&< \sum_n f_{ii}(n) \\
&= \P_i(T_i < \infty) \\
&\leq 1.
\end{align*}
 so $F_{ii}(s)<1$. Taking the limit as $s \to 1^-$ using Abel's lemma gives
\begin{align*}
P_{ii}(1) &= \frac{1}{1 - F_{ii} (1)} \\
\sum_n p_{ii}(n) &=\frac{1}{1 - \sum_n f_{ii}(n)} \\
 &=\frac{1}{1 - \P_i(T_i < \infty)}.
\end{align*}
Hence
\[
\sum_n p_{ii}(n) = \infty \iff  \P_i(T_i < \infty) = 1.
\]
\end{proof}

Q: Recurrence is a class property
A: \begin{thm}
  Let $C$ be a communicating class. Then either every state in $C$ is recurrent, or every state is transient.
\end{thm}
\begin{proof}\leavevmode
Let $i,j$ be distinct sets in $C$. Then $i \leftrightarrow j$, i.e. $\exists m,n\geq 0$ such that
\begin{align*}
p_{ij}(m) &= \alpha > 0 \\
p_{ji}(n) &= \beta > 0
\end{align*}
So for each $k$, we have
      \[
        p_{ii}(m + k + n) \geq p_{ij}(m) p_{j, j}(k) p_{ji}(n) = \alpha\beta p_{jj}(k).
      \]
Now if $\sum_k p_{jj}(k) = \infty$, then $\sum_r p_{ii}(r) = \infty$. So $j$ recurrent implies $i$ recurrent and vice versa by symmetry.
\end{proof}

Q: Recurrent vs Closed
A: Let $C$ be a communicating class. If $C$ is recurrent, then $C$ is closed.
\begin{proof}
If $C$ is not closed, then there is a non-zero probability that we leave the class (and never get back). So the states are not recurrent.
\end{proof}

Q: Recurrence in a finite state space
A: \begin{thm}
  In a finite state space, $S$, there exists at least one recurrent state. In particular, if the chain is irreducible, then every state is recurrent.
\end{thm}
\begin{proof}
Suppose that every state in $S$ is transient. Then for any $i,j\in S$, $p_{ij}(n)\to 0$ as $n\to\infty$. This contradicts the fact that for each $n\in\N$
  \[
    \sum_{j\in S}p_{ij}(n) = 1.
  \]
\end{proof}

Q: Transition probability to a transient state
A: If $j$ is transient and $i\in S$, then $p_{ij}(n) \to 0$ as $n\to\infty$.
\begin{proof}
Recall that for every $i,j\in S$:
  \[
    P_{ij}(s) = \delta_{ij} + P_{jj}(s) F_{ij}(s).
  \]
Since $j$ is transient, $\sum_n p_{jj}(n) = P_{jj}(1) < \infty$. Also, $F_{ij}(1)=\P_i(T_j < \infty)\leq 1$. So $P_{ij}(1) < \infty$. By Abel's lemma
  \[
    P_{ij}(1) = \sum_n p_{ij}(n).
  \]
  Since this is finite, we must have $p_{ij}(n)\to 0$ as $n\to\infty$.
\end{proof}

Q: Recurrence in a 1-D random walk
A: \begin{thm}[P\'olya's theorem]
  The 1-D random walk is irreducible and recurrent.
\end{thm}
\begin{proof}
 We want to show that $\sum p_{00}(n) = \infty$. The probability of returning in $2n$ steps can be written using Stirling's formula as
  \begin{align*}
    p_{00}(2n) &= \P(n\text{ steps left}, n\text{ steps right}) \\
&= \binom{2n}{n} \left(\frac{1}{2}\right)^{2n} \\
&\sim \frac{e^{-2n}(2n)^{2n+1/2}\sqrt{2\pi}}{2^{2n}\left(e^{-n}n^{n+1/2}\sqrt{2\pi}\right)^2} \\
 &= \frac{1}{\sqrt{\pi n}}.
  \end{align*}
  So $\sum_{n\in\N} p_{00}(2n) = \infty$.
\end{proof}

Q: Recurrence in a 2-D random walk
A: \begin{thm}
The 2-D random walk is irreducible and recurrent.
\end{thm}
\begin{proof}
The probability of returning to the origin after $2n$ steps with $m$ left/right steps is
  \begin{align*}
    p_{0, 0}(2n) &= \left(\frac{1}{4}\right)^{2n} \sum_{m = 0}^n \binom{2n}{m, m, n - m, n - m} \\
    &= \left(\frac{1}{4}\right)^{2n} \sum_{m = 0}^n \frac{(2n)!}{(m!)^2 ((n - m)!)^2} \\
    &= \left(\frac{1}{4}\right)^{2n} \binom{2n}{n}\sum_{m = 0}^n \left(\frac{n!}{m!(n - m)!}\right)^2\\
    &= \left(\frac{1}{4}\right)^{2n} \binom{2n}{n}\sum_{m = 0}^n \binom{n}{m}\binom{n}{n - m}\\
    &= \left(\frac{1}{4}\right)^{2n} \binom{2n}{n}^2\\
    &\sim \frac{1}{\pi n}.
  \end{align*}
\end{proof}

Q: Recurrence in 3-D random walk
A: \begin{thm}[P\'olya's Theorem]
A random walk on $\Z^d$ is irreducible and transient for $d\geq 3$.
\end{thm}
\begin{proof}
The probability of returning to the origin in $2n$ steps with $i, j, k$ steps along each of the axes is
\begin{align*}
p_{0, 0}(2n) &= \left(\frac{1}{6}\right)^{2n}\sum_{i + j + k = n}\frac{(2n)!}{(i!j!k!)^2} \\
 &= \left(\frac{1}{6}\right)^{2n} \binom{2n}{n} \sum \left(\frac{n!}{i!j!k!}\right)^2\\
    &= \left(\frac{1}{2}\right)^{2n} \binom{2n}{n} \sum \left(\frac{n!}{3^n i!j!k!}\right)^2\\
    &\leq \left(\frac{1}{2}\right)^{2n}\binom{2n}{n} \max\left(\frac{n!}{3^n i!j!k!}\right)\sum \frac{n!}{3^n i!j!k!}\\
&= \left(\frac{1}{2}\right)^{2n}\binom{2n}{n} \max\left(\frac{n!}{3^n i!j!k!}\right) \P(A) \\
    &= \left(\frac{1}{2}\right)^{2n}\binom{2n}{n} \max\left(\frac{n!}{3^n i!j!k!}\right) \\
    &\leq \left(\frac{1}{2}\right)^{2n}\binom{2n}{n} \frac{n!}{3^n}\left(\frac{1}{\lfloor n/3\rfloor!}\right)^3\\
&\leq \frac{\sqrt{2\pi}e^{-n}n^{n+1/2}}{3^n\sqrt{\pi n}\left( \sqrt{2\pi}e^{-n/3}(n/3)^{n/3 + 1/2}\right)^3}\\
&=\frac{\sqrt{2\pi}n^{n+1/2}}{3^n\sqrt{\pi n}(2\pi)^{3/2}(n/3)^{n + 3/2}} \\
&=\frac{1}{2}\left( \frac{3}{\pi}\right)^{3/2}n^{-3/2}
  \end{align*}
where $A$ is the event that $n$ balls land $i,j,k$ in 3 bins. So $\sum p_{0,0}(2n) < \infty$ and the chain is transient. We can prove similarly for higher dimensions.
\end{proof}

Q: Relationship between recurrence in $1$ and $2$ dimensional random walks
A: Write $X_n = (A_n, B_n)$. Then wrt axes rotated by $\pi/4$ we have $X_n'=(U_n/\sqrt{2}, V_n/\sqrt{2})$ where
\begin{align*}
  U_n &= A_n - B_n\\
  V_n &= A_n + B_n.
\end{align*}
In each step, either $A_n$ or $B_n$ change by one step. So $U_n$ and $V_n$ \emph{both} change by $1$. Hence $U_n, V_n$ are 1-D random walks.
They are also symmetric:
\begin{align*}
\P(U_{n+1} &= U_n + 1)\\
&=\P(A_{n+1}=A_n+1) + \P(B_{n+1} = B_n - 1)\\
& = \frac{1}{4} + \frac{1}{4} \\
&= \frac{1}{2}
\end{align*}
and independent:
\begin{align*}
\P(U_{n+1} = U_n + 1, V_{n+1}=V_n + 1) &= \P(A_{n+1} = A_n + 1)\\
& =\frac{1}{4} \\
&= \frac{1}{2}\frac{1}{2}\\
&=\P(U_{n+1} = U_n + 1)\P(V_{n+1}=V_n+1)
\end{align*}
(the other 3 cases are similar).
 So we have
\begin{align*}
  p_{0, 0}(2n) &= \P(A_n = B_n = 0)\\
  &= \P(U_n = V_n = 0)\\
  &= \P(U_n = 0)\P (V_n = 0)\\
  &= \left[\binom{2n}{n}\left(\frac{1}{2}\right)^{2n}\right]^2.
\end{align*}

Q: Recurrence in higher dimensional random walks
A: \begin{thm}(P\'olya's Theorem)
Let $X=(X_n)$ be a random walk on $\Z^d$ with $d\geq 3$. Then $X$ is irreducible and transient.
\end{thm}
\begin{proof}
Let $\bar{X}$ be the projection of $X$ onto the first three coordinates. Then $X=0\implies\bar{X}=0$. Define
\begin{align*}
T_0 &= \text{ first return time of $X$ to $0$} \\
\bar{T}_0 &=\text{ first return time of $\bar{X}$ to $0$}.
\end{align*}
Then since $\bar X$ is transient
\begin{align*}
\bar{T}_0&\leq T_0 \\
0< \P(\bar T_0 = \infty) &\leq \P(T_0=\infty).
\end{align*}
So $X$ is transient.
\end{proof}

Q: Hitting times
A: The \emph{hitting time} of $A \subseteq S$ is the random variable $H^A = \min\{n \geq 0: X_n \in A\}$ where $\min\emptyset=\infty$. In particular, if $X_0\in A$, then $H^A = 0$.
The \emph{hitting probability} is
  \[
    h_i^A = \P_i(H^A < \infty) = \P_i(\text{ever reach }A).
  \]
If $A$ is closed, then $h_i^A$ is an \emph{absorption probability}.
The \emph{mean hitting time} of $A$ is $k_i^A=\E_i(H^A)$. Note that if $h_i^A<1$, then $k_i^A=\infty$.

Q: Classification of hitting probabilities
A: \begin{thm}
  The vector $(h_i^A: i \in S)$ satisfies
  \[
    h_i^A =
    \begin{cases}
      1 & i \in A\\
      \sum_{j \in S}p_{i, j}h_j^A & i \not \in A
    \end{cases},
  \]
  and is \emph{minimal} in that for any non-negative solution $(x_i: i \in S)$ to these equations, we have $h_i^a \leq x_i$ for all $i$.
\end{thm}
\begin{proof}
  By definition, $h_i^A = 1$ if $i \in A$. Otherwise
  \[
    h_i^A = \P_i(H^A < \infty) = \sum_{j\in S} \P_i(H^A < \infty \mid X_1 = j)p_{i, j} = \sum_{j\in S}h_{j}^A p_{i, j}.
  \]
  Now suppose $x = (x_i: i \in S)$ is a non-negative solution. If $i \in A$, then $h_i^A = x_i = 1$. Otherwise
  \begin{align*}
    x_i &= \sum_{j\in S} p_{i, j}x_j \\
    &= \sum_{j \in A}p_{i, j}x_j + \sum_{j \not\in A}p_{i, j}x_j \\
    &= \sum_{j \in A}p_{i, j} + \sum_{j \not\in A}p_{i, j}x_j \\
    &= \sum_{j \in A} p_{i, j} + \sum_{j \not\in A} p_{i, j}\left(\sum_{k\in S} p_{i, k} x_k\right) \\
    &= \sum_{j \in A} p_{i, j} + \sum_{j \not\in A} p_{i, j}\left(\sum_{k\in A} p_{i, k} x_k + \sum_{k \not\in A} p_{i, k}x_k\right)\\
    &\geq \P_i (H^A = 1) + \sum_{j \not \in A, k \in A}p_{i, j}p_{j, k}\\
    &= \P_i(H^A = 1) + \P_i(H^A = 2)\\
    &= \P_i (H^A \leq 2).
  \end{align*}
  By induction, we obtain
  \[
    x_i \geq \P_i(H^A \leq n)
  \]
  for all $n$. Taking the limit as $n \to \infty$, we get
  \[
    x_i \geq \P_i(H^A < \infty) = h_i^A.
  \]
\end{proof}

Q: Classification of mean hitting times
A: \begin{thm}
  $(k_i^A: i \in S)$ is the minimal non-negative solution to
  \[
    k_i^A =
    \begin{cases}
      0 & i \in A\\
      1 + \sum_j p_{i, k}k_j^A & i \not\in A.
    \end{cases}
  \]
\end{thm}
\begin{proof}
By definition, $k_i^A = 0$ if $i \in A$. Otherwise
  \[
    k_i^A = \E_i(H^A) = 1+\sum_{j\in S} \E_j(H_i^A)p_{i, j}= 1+\sum_{j\in S} k_j^Ap_{i, j}.
  \]
   Now let $(y_i : i\in S)$ be a non-negative solution. If $i \in A$, we get $y_i = k_i^A = 0$. Otherwise
  \begin{align*}
    y_i &= 1 + \sum_{j\in S} p_{i, j}y_j\\
    &= 1 + \sum_{j \in A}p_{i, j}y_j + \sum_{j\not\in A}p_{i, j}y_j\\
    &= 1 + \sum_{j\not\in A}p_{i, j}y_j\\
    &= 1 + \sum_{j \not\in A}p_{i, j}\left(1 + \sum_{k\not\in A} p_{j, k}y_k\right)\\
    &\geq 1 + \sum_{j \not\in A} p_{i, j} + \sum_{j \not\in A}\sum_{k\not\in A} p_{i, j}p_{j, k}y_k\\
    &= \P_i(H^A \geq 1) + \P_i(H^A \geq 2).
  \end{align*}
  By induction, we know that
  \[
    y_i \geq \P_i (H^A \geq 1) + \cdots + \P_i(H^A \geq n)
  \]
  for all $n$. Let $n\to \infty$. Then we get
  \[
    y_i \geq \sum_{m \geq 1}\P_i(H^A \geq m) = k_i^A.
  \]
\end{proof}

Q: Probability of gambler's ruin
A: Consider the biased 1-D random walk where $\{0\}$ is an absorbing state, we move right with probabity $p$ and $q=1-p$. We know $h_i= h_i^{\{0\}}$ is the minimal solution to
  \[
    h_i =
    \begin{cases}
      1 & i = 0\\
      qh_{i - 1} + ph_{i + 1} & i \not= 0.
    \end{cases}
  \]
  This is a difference equation
  \[
    ph_{i + 1} - h_i + qh_{i - 1} = 0,\quad i \geq 1
  \]
  with the boundary condition $h_0 = 1$. The auxiliary quadratic has two roots: $1$ and $q/p$.
  If $p \not= q$, ie. $p \not= \frac{1}{2}$, then the solution has the form
  \[
    h_i = A + B\left(\frac{q}{p}\right)^i
  \]
  for $i \geq 0$ where $h_0 = 1=A+B$.
If $p < q$, requiring $h_i\leq 1$ requires $B = 0$. Since $h_0 = 1$, we have $h_i = 1$ for all $i$.
If $p>q$, then
  \[
    h_i = \left(\frac{q}{p}\right)^i + A\left(1 - \left(\frac{q}{p}\right)^i\right)
  \]
so $h_i \to A$ as $i \to\infty$. Since $h_i \geq 0$, we know that $A \geq 0$. So $h_i$ is minimised when $A=0$ and thus
  \[
    h_i = \left(\frac{q}{p}\right)^i.
  \]
If $p=q$, then $h_i = A+Bi$ so the only bounded solution with $h_0=1$ is $h_i=1$.

Q: Birth-death chain
A: Let $(p_i: i \geq 1)$ satisfy $p_i \in (0, 1)$. We let $q_i = 1 - p_i$. Consider the MC with state space $\N$ and transition probabilities
  \[
    p_{i, i + 1} = p_i,\quad p_{i, i - 1} = q_i.
  \]
We let $\{0\}$ be \emph{absorbing}, i.e. $p_{0,0}=1$. Define $h_i = h_i^{\{0\}}$. We seek the minimal solution to
  \[
    h_0 = 1,\quad p_i h_{i + 1} - h_i + q_i h_{i - 1} = 0,\quad i \geq 1.
  \]
We rewrite this as
  \begin{align*}
    p_i h_{i + 1} - h_i + q_i h_{i - 1} &= p_i h_{i + 1} - (p_i + q_i) h_i + q_i h_{i - 1} \\
    &= p_i (h_{i + 1} - h_i) - q_i(h_i - h_{i - 1}).
  \end{align*}
 Define $u_i = h_{i - 1} - h_i$. Then our equation becomes
  \[
    u_{i + 1} = \frac{q_i}{p_i} u_i.
  \]
  We can iterate this to become
  \[
    u_{i + 1} = \left(\frac{q_i}{p_i}\right)\left(\frac{q_{i - 1}}{p_{i - 1}}\right) \cdots \left(\frac{q_1}{p_1}\right) u_1.
  \]
  We let
  \[
    \gamma_i = \frac{q_1q_2\cdots q_i}{p_1p_2\cdots p_i}
  \]
such that $u_{i + 1} = \gamma_i u_1$. Set $\gamma_0 = 1$ so this holds even for $i=0$. Summing the equation $u_i = h_{i - 1} - h_i$ we obtain the telescopic sum
  \[
    h_0 - h_i = u_1 + u_2 + \cdots + u_i.
  \]
  Using the fact that $h_0 = 1$, we get
  \[
    h_i = 1 - u_1(\gamma_0 + \gamma_1 + \cdots + \gamma_{i - 1}).
  \]
Define $S = \sum_{i = 0}^\infty \gamma_i$.
If $S = \infty$, then requiring $h_i\leq 1$ forces $u_1 = 0$.
If $S<\infty$, then the minimal solution with $h_i\geq 0$ is $u_1=1/S$ and
  \[
    h_i = 1-\frac{\sum_{k = 0}^{i-1} \gamma_k}{\sum_{k = 0}^\infty \gamma_k} =\frac{\sum_{k = i}^\infty \gamma_k}{\sum_{k = 0}^\infty \gamma_k}.
  \]

Q: Stopping time
A: Let $X$ be a Markov chain. A random variable $T: X \to \N\cup \{\infty\}$ is a \emph{stopping time} for the chain $X = (X_n)$ if for all $n \geq 0$ the event $\{T = n\}$ is given in terms of $X_0, \cdots, X_n$.

Q: Strong Markov property
A: Let $X$ be a Markov chain with transition matrix $P$, and let $T$ be a stopping time for $X$. Given $T < \infty$ and $X_T = i$, the chain $(X_{T + k}: k \geq 0)$ is a Markov chain with transition matrix $P$ with initial distribution $X_{T} = i$, and is independent of $X_0, \cdots, X_{T-1}$.

Q: Time to gambler's ruin
A: We want to find the time it takes to get to $0$, ie.
  \[
    H = \inf\{n \geq 0: X_n = 0\}.
  \]
We define the generating function
  \[
    G_i(s) = \E_i(s^H) = \sum_{n = 0}^\infty s^n \P_i(H = n),\quad |s| < 1.
  \]
  We have
  \begin{align*}
    G_1(s) = \E_1(s^H) &= p\E_1(s^H\mid X_1 = 2) + q\E_1(s^H\mid X_1 = 0) \\
&=p\E_1(s^{1+H_0+H_1}) + qs \\
&=ps\E_1(s^{H_0})\E_1(S^{H_1}) + qs \\
&= psG_1^2 + qs
  \end{align*}
where $H_i$ is the time taken to go from $i+1$ to $i$. This has two solutions
  \[
    G_1 (s) = \frac{1 \pm \sqrt{1 - 4pqs^2}}{2ps}.
  \]
Since $G_1(0)=0$ and $G$ is continuous, we must take the negative root, ie.
  \[
    G_1 (s) = \frac{1 - \sqrt{1 - 4pqs^2}}{2ps} = \sum_{k=1}^\infty \frac{(2k-2)! (pq)^k}{k!(k-1)!p} s^{2k-1}.
  \]
  Then $\P_1(H=n)$ is the coefficient of $s^n$, $\P_1(H<\infty)=\lim_{s\to 1^-} G(s)=\min(1,q/p)$ and $\E_1(H)=\lim_{s\to 1^-} G'(s)=1/(q-p)$.

Q: Mean recurrence time
A: Let $T_i$ be the first passage time to a state $i$. Then the \emph{mean recurrence time} of $i$ is
  \[
    \mu_i = \E_i(T_i) =
    \begin{cases}
      \infty & i\text{ transient}\\
      \sum_{n = 1}^\infty n f_{i, i}(n) & i\text{ recurrent}.
    \end{cases}
  \]

Q: Null and positive state
A: If $i$ is recurrent, then we call $i$ a \emph{null state} if the expected first passage time $\mu_i = \infty$. Otherwise $i$ is \emph{non-null} or \emph{positive}.

Q: Period
A: The \emph{period} of a state $i$ is $d_i = \gcd\{n \geq 1: p_{i, i}(n)> 0\}$.
  A state is \emph{aperiodic} if $d_i = 1$.

Q: Ergodic state
A: A state $i$ is \emph{ergodic} if it is aperiodic and positive recurrent.
Note this is actually a class property since period and positive recurrence are class properties.

Q: Period is a class property
A: \begin{thm}
  If $i \leftrightarrow j$ are communicating, then $d_i = d_j$.
\end{thm}
\begin{proof}
Assume $i \leftrightarrow j$. Then there are $m, n \geq 1$ with $p_{i, j}(m), p_{j, i}(n) > 0$. By the Chapman-Kolmogorov equation, we know that
      \[
        p_{ii}(m + r + n) \geq p_{ij}(m)p_{j, j}(r)p_{ji}(n) \geq \alpha p_{jj}(r)
      \]
      where $\alpha = p_{ij}(m) p_{j, i}(n) > 0$. Now let $D_j = \{r \geq 1: p_{jj}(r) > 0\}$ such that $d_j = \gcd D_j$.
By the above inequality, $r \in D_j \implies m + r + n \in D_i \implies d_i \mid m + r + n$. Also putting $r=0$ gives $n + m \in D_i $ and hence $d_i \mid m + n$. So $\forall r \in D_j: d_i \mid r$. Hence $\gcd D_i \mid \gcd D_j$. By symmetry, $\gcd D_j \mid \gcd D_i$ as well. So $\gcd D_i = \gcd D_j$.
\end{proof}

Q: Recurrent states are reached
A: \begin{prop}
  If the chain is irreducible and $j \in S$ is recurrent, then
  \[
    \P(X_n = j\text{ for some }n \geq 1) = 1,
  \]
  regardless of the distribution of $X_0$.
\end{prop}
\begin{proof}
  Let
  \[
    f_{i, j} = \P_i(X_n = j\text{ for some }n \geq 1).
  \]
  Since $j \to i$, $\exists m \geq 1$ minimal with $p_{j, i}(m) > 0$. Since $m$ is minimal
  \[
    p_{j, i}(m) = \P_j(X_m = i, X_r \not= j\text{ for }r < m)
  \]
and hence
  \[
    p_{j, i}(m)(1 - f_{i, j}) \leq 1 - f_{j, j}.
  \]
Hence $f_{j, j} = 1 \implies f_{i, j} = 1$.
  Now let $\lambda_k = \P(X_j = k)$ be our initial distribution. Then
  \[
    \P(X_n = j\text{ for some }n \geq 1) = \sum_{i\in S} \lambda_i f_{ij} = 1.
  \]
\end{proof}

Q: Invariant distribution
A: Let $X_n$ be a Markov chain with transition probabilities $P$. The distribution $\pi = (\pi_k: k \in S)$ is an \emph{invariant distribution} if
  \begin{enumerate}
    \item $\pi_k \geq 0$, $\sum_k \pi_k = 1$.
    \item $\pi = \pi P$.
  \end{enumerate}
The first condition ensures that $\pi$ is a distribution and the second holds if $\lambda P^n\to \pi$ since
\[
  \lambda P^{n + 1} = (\lambda P^n) P.
\]

Q: Expected visits to a state between recurrences
A: \begin{prop}
  For an irreducible recurrent chain $X_n$, $k \in S$, $\rho = (\rho_i: i \in S)$ defined by
  \[
    \rho_i = \E_k(W_i); W_i = \sum_{m = 1}^\infty \mathbbm{1}(X_m = i, T_k \geq m)=\sum_{m = 1}^{T_k} \mathbbm{1}(X_m = i),
  \]
  we have
  \begin{enumerate*}
    \item $\rho_k = 1$
    \item $\sum_i \rho_i = \mu_k$
    \item $\rho = \rho P$
    \item $0 < \rho_i < \infty$ for all $i \in S$.
  \end{enumerate*}
\end{prop}
\begin{proof}\leavevmode
  \begin{enumerate}
    \item For $m < T_k$, $X_m \not= k$ and $X_{T_k}=k$. So $W_k=1$ and thus $\rho_k=1$.
    \item We can compute
      \[
        \sum_i \rho_i = \sum_i \E_k(W_i)= \E_k\left(\sum_i W_i\right)= \E_k(T_k) = \mu_k.
     \]
    \item By the Markov property
      \begin{align*}
        \rho_j &= \E_k(W_j)\\
        &= \E_k\left(\sum_{m \geq 1}\mathbbm{1}(X_m = j, T_k \geq m)\right) \\
        &= \sum_{m\geq 1}\P_k(X_m = j, T_k \geq m)\\
        &= \sum_{m \geq 1}\sum_{i \in S} \P_k(X_m = j \mid X_{m - 1} = i, T_k \geq m) \P_k(X_{m - 1} = i, T_k \geq m)\\
        &= \sum_{i \in S} p_{i, j} \sum_{m \geq 1} \P_k(X_{m - 1} = i, T_k \geq m) \\
        &= \sum_{i \in S} p_{i, j} \sum_{r = 0}^\infty \P_k(X_r = i, T_k \geq r + 1)
      \end{align*}
\textbf{Case} $i = k$. For $r = 0$: $\P_k(X_0 = k, T_k \geq 1)=1=\rho_k$ and $r \neq 0$: $\P_k(X_r = k, T_k \geq r + 1)=0$.
\textbf{Case} $i \not= k$. For $r = 0$: $\P_k(X_0 = i, T_k \geq r + 1)=0$, $r \geq 1$: $\P_k(X_r = i, T_k \geq r + 1)=\P_k(X_r = i, T_k \geq r)$ and the sum is $\sum_{r \geq 1} \P_k (X_{r} = i, T_k \geq r) = \rho_i$.
    \item By induction on (iii) $\rho =\rho P^n$ for $n \geq 1$. So $\forall m, n\in \N$: $ \rho_i \geq \rho_k p_{k, i}(n)$, $\rho_k \geq \rho_i p_{i, k}(m)$. By irreducibility, $\exists m, n$ s.t. $p_{i, k}(m), p_{k, i}(n) > 0$ and $\rho_k p_{k, i}(n) \leq \rho_i \leq \frac{\rho_k}{p_{i, k}(m)}$. Done by (i).
  \end{enumerate}
\end{proof}

Q: Existence and uniqueness of invariant distributions
A: \begin{thm}
  Consider an irreducible MC. Then
  \begin{enumerate}
    \item If some state is PR, then there exists an invariant distribution.
    \item If $\exists$ invariant distribution $\pi$, then every state is PR and $\pi_i = \frac{1}{\mu_i}$ for $i \in S$. So $\pi$ is unique.
  \end{enumerate}
\end{thm}
\begin{proof}
  \begin{enumerate}
    \item Let $k$ be a PR state. Then $\pi_i = \rho_i / \mu_k$ satisfies $\pi_i \geq 0$ with $\sum_i \pi_i = 1$, and is an invariant distribution.
    \item \textbf{Non-zero}. $\forall n \in \N: \pi = \pi P^n$ hence $\forall i, j \in S$, $n \in \N: \pi_i \geq \pi_j p_{j,i}(n)$. Since $\sum \pi_i = 1$, $\exists k: \pi_k > 0$. By irreducibility, $\exists n\in \N: p_{k,i}(n) > 0$. So $\pi_i \geq \pi_k p_{k,i}(n) > 0$.
 \textbf{Recurrent}. Suppose all states are transient. So $p_{j, i}(n) \to 0 (\forall i, j\in S)$. Then $0<\pi_i = \sum_j \pi_j p_{j, i}(n)\to 0$ as $n\to\infty$ by bounded convergence. Contradiction.
 \textbf{PR}. Let $X_n$ be a MC with distn $\pi$ and $a_r = \P(X_m \not= i \text{ for }0 \leq i \leq r)$. Then
      \[
        \pi_i \mu_i=  \sum_{n = 1}^\infty \pi_i\P_i (T_i \geq n)= \sum_{n = 1}^\infty \P(T_i \geq n, X_0 = i).
      \]
For $n=1$: $\P(T_i \geq 1, X_0 = i) = \P(X_0 = i) = \pi_i$, and $n \geq 2$: $\P(T_i \geq n, X_0 = i) = \P(X_0 = i, X_m \not= i\text{ for } 1 \leq m \leq n - 1)= a_{n-2} - a_{n-1}$ by invariance. By telescoping
      \begin{align*}
\pi_i \mu_i &= \lim_{N\to \infty} [\pi_i + a_0 - a_{N - 1}]\\
        &= \pi_i + a_0 + \lim_{N \to \infty} a_N \\
        &= \P(X_0 = i) + \P(X_0 \not= i) + \P(X_m \not= i \text{ for all }m)
      \end{align*}
So $\pi_i \mu_i=1$, $\pi_i > 0$, as required.
  \end{enumerate}
\end{proof}

Q: Sufficient condition for convergence
A: \begin{thm}
  Consider a MC that is irreducible, positive recurrent and aperiodic. Then
  \[
    p_{i,k}(n) \to \pi_k \text{ as }n \to \infty
  \]
where $\pi$ is the unique invariant distribution.
\end{thm}
\begin{proof}
Let $Z_n = (X_n, Y_n)$ where $X=(X_n),Y=(Y_n)$ are independent MCs each with state space $S$ and transition matrix $P$. Then $Z=(Z_n)$ is a MC on state space $S^2$ with transition probabilities
  \[
    p_{ij, k\ell} = p_{i, k} p_{j, \ell}.
  \]
\textbf{Irreduciblility}. Since $X,Y$ are irreducible and aperiodic, $\exists A,B\subseteq\N$ with relatively prime members such that $0\not\in p_{i,k} (A)$ or $p_{j,\ell}(B)$. By the Frobenius problem $\exists n\in A\cap B$ such that
  \[
    p_{ij, k\ell}(n) = p_{i,k} (n) p_{j,\ell}(n)>0.
  \]
\textbf{Positive recurrence}. Since $X,Y$ are positive recurrent, $\exists !\pi$ for $P$. Hence $Z$ has invariant distribution $\nu_{ij}=\pi_i\pi_j$ since
\[
\P(Z_n=(i,j)) = \P(X_n=i)\P(Y_n=j)\to \pi_i\pi_j.
\]
\textbf{Coupling}. Let $(X_0,Y_0)=(i,j)$. Then fix $s \in S$, and let
\[
    T = \inf\{n: Z_n  = (s, s)\}
  \]
be a stopping time for $Z$. Now $X_n,Y_n$ are identically distributed for $n\geq T$ and hence
  \begin{align*}
    p_{i, k}(n) &= \P_{ij}(X_n = k)\\
    &= \P_{ij} (X_n = k, T \leq n) + \P_{ij} (X_n = k, T > n)\\
    &= \P_{ij}(Y_n = k, T \leq n) + \P_{ij} (X_n = k, T > n)\\
    &\leq \P_{ij}(Y_n = k) + \P_{ij}(T > n)\\
    &= p_{j,k}(n) + \P_{ij}(T > n).
  \end{align*}
Since $Z$ is recurrent, $\P_{ij}(T<\infty)=1$ and thus
  \[
    |p_{i, k}(n) - p_{j, k}(n)| \leq \P_{ij} (T > n) \to 0 \text{ as }n\to\infty.
  \]
  Finally by bounded convergence
\[
    \pi_k - p_{i, k}(n)= \sum_j \pi_j (p_{j, k}(n) - p_{i, k}(n))\to 0\text{ as }n\to\infty.
\]
\end{proof}

Q: Bounded convergence theorem
A: \begin{thm}
Let $(X_n:n\in\N)$ and $X$ be random variables on a countable state space $\Omega$. If $X_n\to X$,  $\forall n\in\N: \P(|X_n|\leq Y)=1$ and $\P(|X|\leq Z)=1$, then
\[
\E[X_n]\to\E[X].
\]
\end{thm}
\begin{proof}
Let $F\subseteq \Omega$ be finite. Then
      \begin{align*}
        |\E[X_n]-\E[X]| &= |\E[X_n-X]| \\
&=\left|\sum_{\omega\in\Omega} p(\omega) (x_n(\omega)-x(\omega))\right|\\
        &= \left|\sum_{\omega \in F}p(\omega) (x_n(\omega)-x(\omega)) + \sum_{\omega\not\in F} p(\omega)(x_n(\omega)-x(\omega))\right| \\
&\leq \sum_{\omega \in F}p(\omega) |x_n(\omega)-x(\omega)| + \sum_{\omega\not\in F} p(\omega)|x_n(\omega)-x(\omega))| \\
&\leq \sum_{\omega \in F} |x_n(\omega)-x(\omega)| +M\sum_{\omega\not\in F} p(\omega) \\
&\to M\sum_{\omega\not\in F} p(\omega) \text{ as }n\to\infty\\
&\to 0 \text{ as }F\to\Omega
      \end{align*}
where $M=Y+Z$.
\end{proof}

Q: Upper bound on the Frobenius problem
A: Let $p_1,\ldots p_k\in\N$ with $k\geq 2$ and $\gcd(p_1,\ldots p_k)=1$. Then $\exists N\in\N:\forall n\geq N: \exists i_1,\ldots i_k\geq 0$ such that
\[
n=i_1p_1+\ldots + i_kp_k.
\]
\begin{proof}
Since $\gcd(p_1,\ldots p_k)=1$, by Bezout's Theorem, $\forall n \in\Z: \exists h_1,\ldots h_k\in\Z$ such that
\[
n=h_1p_1+\ldots + h_kp_k. \tag{$*$}
\]
By the division algorithm $\forall j\neq 1: \exists a_j, r_j$ such that
\[
h_j=p_1a_j+r_j
\]
 where $0\leq r_j\leq p_1-1$. So $\forall j\neq 1:$
\[
 h_jp_j=p_1h_jp_j+r_jp_j.
\]
Substituting into $(*)$ gives
\[
n=(h_1+p_2h_2+\ldots + p_kh_k)p_1 + r_2p_2+\ldots + r_kp_k
\]
where recall $0\leq r_j\leq p_1-1$ for $j\neq 2$.
Now pick $N=-p_1+(p_1-1)(p_2+\ldots + p_k)$. Then $\forall n\geq N$:
\[
N\leq n\leq(h_1+p_2h_2+\ldots + p_kh_k)p_1 + N
\]
and hence
\[
(h_1+p_2h_2+\ldots + p_kh_k)\geq 0
\]
as required.
\end{proof}

Q: Reversal of a MC
A: \begin{thm}
  Let $X$ be positive recurrent, irreducible MC with invariant distribution $\pi$. Suppose that $X_0$ has distribution $\pi$. Then $Y$ defined by
  \[
    Y_{k} = X_{N - k}
  \]
  is a MC with transition matrix $\hat{P} = (\hat{p}_{i, j}: i, j \in S)$, where
  \[
    \hat{p}_{i, j} = \left(\frac{\pi_j}{\pi_i}\right) p_{j, i}.
  \]
  Also $\pi$ is invariant for $\hat{P}$.
\end{thm}
\begin{proof}
\textbf{Stochastic}. We have $\hat{p}_{i,j} \geq 0$ and $\forall i\in S$:
  \[
    \sum_j \hat{p}_{i, j} = \frac{1}{\pi_i} \sum_j \pi_j p_{j, i} = \frac{1}{\pi_i} \pi_i = 1
  \]
since $\pi = \pi P$.
\textbf{Invariant}.We have
  \[
    \sum_i \pi_i \hat{p}_{i, j} = \sum_i \pi_j p_{j, i} = \pi_j
  \]
  since $P$ is stochastic.
\textbf{Markov}. We have
  \begin{align*}
    \P(Y_0 = i_0, \cdots, Y_k = i_k) &= \P(X_{N - k} = i_k, X_{N - k + 1} = i_{k - 1}, \cdots, X_N = i_0)\\
    &= \pi_{i_k} p_{i_k, i_{k - 1}} p_{i_{k - 1}, p_{k - 2}} \cdots p_{i_1, i_0}\\
    &= (\pi_{i_k} p_{i_k, i_{k - 1}}) p_{i_{k - 1}, p_{k - 2}} \cdots p_{i_1, i_0}\\
    &= \hat{p}_{i_{k - 1} i_k} (\pi_{i_{k - 1}} p_{i_{k - 1}, p_{k - 2}}) \cdots p_{i_1, i_0}\\
    &= \cdots\\
    &= \pi_{i_0} \hat{p}_{i_0, i} \hat{p}_{i_1, i_2} \cdots \hat{p}_{i_{k - 1}, i_k}.
  \end{align*}
\end{proof}

Q: Reversible chain
A: An irreducible Markov chain $X = (X_0, \cdots, X_N)$ in its invariant distribution $\pi$ is \emph{reversible} if its reversal has the same transition probabilities as does $X$, ie
  \[
    \pi_i p_{i, j} = \pi_j p_{j, i}
  \]
  for all $i, j \in S$.
  This equation is known as the \emph{detailed balance equation}. In general, if $\lambda$ is a distribution that satisfies
  \[
    \lambda_i p_{i, j} = \lambda_j p_{j, i},
  \]
  we say $(P, \lambda)$ is in \emph{detailed balance}.

Q: Invariant distribution for reversible chains
A: \begin{prop}
  Let $P$ be the transition matrix of an irreducible Markov chain $X$. Suppose $(P, \lambda)$ is in detailed balance. Then $\lambda$ is the \emph{unique} invariant distribution and the chain is reversible (when $X_0$ has distribution $\lambda$).
\end{prop}
\begin{proof}
We can see that $\lambda$ is invariant:
  \[
    \sum_j \lambda_j p_{j, i} = \sum_j \lambda_i p_{i, j} = \lambda_i \sum_j p_{i, j} = \lambda_i.
  \]
Hence $\lambda$ is the unique invariant distribution and the chain is reversible (when $X_0$ has distribution $\lambda$).
\end{proof}