Proof. Since \(\, i\longleftrightarrow j, \, \exists \, \) integers \(m\geq 0\) such that \(P^m_{ij} > 0\).
Similarly, \(P^n_{jk} > 0\) for any integer \(n\geq 0\) \begin {align*} P_{ik}^{n + m} & = \sum ^{\infty }_{l = 0} P^m_{il}\, P^n_{lk} \hspace {0.3cm}(\text {Kolmogrov equation})\\ & > P^{m}_{ij}\, P^n_{ik} \end {align*}

Hence \(P^{n + m}_{ik} > 0\). Implying \(i \longrightarrow k\). Similarly we can show that \(k\longrightarrow i\).
Combining \(i \longrightarrow k, \hspace {0.2cm} k \longrightarrow i\, \implies \, i\longleftrightarrow k\). □

Proof. Write \(i \leftrightarrow j\) when \(i\) and \(j\) communicate, meaning \(p_{ij}^{(m)}>0\) and \(p_{ji}^{(n)}>0\) for some \(m,n\). The classes are the equivalence classes of this relation, so it is enough to check it is an equivalence relation.

Reflexive: \(p_{ii}^{(0)}=1\), so \(i\leftrightarrow i\). Symmetric: immediate from the definition, which is symmetric in \(i\) and \(j\). Transitive: suppose \(i\leftrightarrow j\) and \(j\leftrightarrow k\), with \(p_{ij}^{(m)}>0\) and \(p_{jk}^{(n)}>0\). By the Chapman–Kolmogorov equation, \[p_{ik}^{(m+n)} = \sum _{r} p_{ir}^{(m)}p_{rk}^{(n)} \geq p_{ij}^{(m)}p_{jk}^{(n)} > 0,\] the inequality because every term of the sum is non-negative and \(r=j\) is one of them. The same argument in the other direction gives \(p_{ki}^{(\cdot )}>0\), so \(i\leftrightarrow k\).

Hence communication partitions the state space, and two communicating states lie in the same class. □

Proof. Let \(N\) be the number of returns to \(i\), counting the visits after time zero. Each time the chain is at \(i\) it returns again with probability \(f_{ii}\) and never returns with probability \(1-f_{ii}\), independently of the past by the Markov property and time homogeneity. So \(N\) is geometric: \[P(N = n) = f_{ii}^{\,n}\left (1-f_{ii}\right ),\qquad n=0,1,2,\dots \]

If \(f_{ii}<1\) then \(P(N=\infty )=0\) and \(E(N) = f_{ii}/(1-f_{ii})<\infty \), so the chain returns only finitely often: state \(i\) is transient. If \(f_{ii}=1\) then every trial succeeds, \(N=\infty \) with probability one, and the chain returns infinitely often: state \(i\) is recurrent. □

Proof. Define a random variable \(I_n\) as follows \[ I_n = \begin {cases} 1 & \text {if}\hspace {0.3cm} X_n = i\\ 0 & \text {if} \hspace {0.3cm} X_n \neq i\\ \end {cases}\] Hence \(\sum ^{\infty }_{n = 0} I_n\) represents total visits to state \(E_i\). \[E\left [\sum ^{\infty }_{n = 0} I_n \Big | X_0 = i\right ] = \infty \] if \(E_1\) i recurrent. \begin {align*} E\left [\sum ^{\infty }_{n = 0} I_n\, \Big |\, X_0 = i\right ] & = \sum ^{\infty }_{n = 0} \left [E(I_n /X_0 = i)\right ]\\ & = \sum ^{\infty }_{n = 0} \left [1\times P(I_n = 1\, / X_0 = 0) + 0\times P(I_n = 0/X_0 = i)\right ]\\ & = \sum ^{\infty }_{n = 0} P(X_n = i/ X_0 = i)\\ & = \sum ^{\infty }_{n = 0} P^n_{ii} \end {align*}

But \(E\left [\sum ^{\infty }_{n = 0} I_n \, \Big |\, X_0 = i\right ] = \infty \) \[\sum ^{\infty }_{n = 0} P^n_{ii} = \infty .\] □

Proof. Consider a Markov chain with State Space \(\{0, \, 1, \, \cdots \, , \, m\}\). If possible assume all states are transient. Then the chain will visit State 0 in \(T_0\) steps , 1 then transit into State 1 and remains there at \(T_1\) steps and transit to \(T_2\) and so hence after a finite number of steps no state will be visited which is a contradiction. Hence atleast one state is recurrent in a Markov chain which has finite number of states. □

Proof. Since State \(i\) is recurrent, \(\sum _nP^n_{ii} = \infty \). Also \(i\longleftrightarrow j\), therefore \(\exists \) non negative integers \(m\) and \(k\) such that \[P^{m}_{ij} > 0\hspace {0.5cm} , \hspace {0.5cm} P^k_{ji} > 0\] \begin {align*} P^{k+n+m}_{jj} & = \sum ^{\infty }_{r =0} P^k_{ir}\, P^n_{rr}\, P^m_{rj}\\ & > P^k_{ji}\, P^n_{ii}\, P^m_{ij} \end {align*}

Therefore \begin {align*} \sum _{n} P^{k + n + m}_{jj} & > \sum _n P^k_{ji}\, P^n_{ii}\, P^m_{ij}\\ & = P^k_{ji}\, P^m_{ij}\, \sum _n P^n_{ii}\\ & = \infty . \end {align*} □