A subchain of a Markov chain is also a Marchov chain. How to prove this ? Here is an idea. Suppose there is a Marchov subchain from \(X_i\) to \(X_n\)

\[ \begin{aligned} \cdots \rightarrow X_i \rightarrow \color{blue}{X_j \rightarrow \cdots} \rightarrow X_n \rightarrow \cdots \\ \end{aligned} \]

This means

\[ \begin{aligned} p(x_1, \cdots, x_i, \color{blue}{x_j, \cdots,} x_n, \cdots) &= p(x_1,x_2) p(x_3|x_2) \cdots \color{blue}{p(x_j|x_i) \cdots p(x_n|x_{n-1})} \cdots \\ &= p(x_1,x_2) {p(x_2,x_3) \over p(x_2)} \cdots {\color{blue}{p(x_i,x_j)} \over p(x_i)} \color{blue}{\cdots {p(x_n,x_{n-1}) \over p(x_{n-1})}} \cdots \\ \end{aligned} \]

Now remove the subchain from \(X_j\) to \(X_{n-1}\) inclusive, resulting in

\[ \begin{aligned} p(x_1, \cdots, \color{teal}{x_i, x_n}, \cdots) &= p(x_1,x_2) {p(x_2,x_3) \over p(x_2)} \cdots {\color{teal}{p(x_i, x_n)} \over p(x_i)} \cdots \\ \end{aligned} \]

All other parts remain unchanged, but this means

\[ \begin{aligned} \cdots \rightarrow X_i \rightarrow X_n \rightarrow \cdots \\ \end{aligned} \]

\(\Box\)

Formally, Let \(\mathscr{N}_n = \{1,2,...,n\}\,\) and let \(X_1 \rightarrow X_2 \rightarrow \cdots \rightarrow X_n\) form a Markov subchain. For any subset \(\alpha\) of \(\mathcal{N}_n\), denote \(X_i, i\in \alpha\) by \(X_\alpha\). Then for any disjoint subsets \(\alpha_1, \alpha_2, \cdots, \alpha_n\) of \(\mathcal{N}_n\) such that

\[ \begin{aligned} k_1 < k_2 < \cdots < k_m \end{aligned} \]

for all \(k_j \in \alpha_j,\, j = 1, 2, \cdots, m,\)

\[ \begin{aligned} X_{\alpha_1} \rightarrow X_{\alpha_2} \rightarrow \cdots \rightarrow X_{\alpha_m} \end{aligned} \]

forms a Markov subchain.

Source: Information Theory.

# posted by rot13(Unafba Pune) @ 9:10 AM