91Ó°ÊÓ

A Markov chain is a stochastic process with the Markov property, meaning that the future state is dependent only on the current state and not on the previous states. Formally, let \(X = (X_0, X_1, \dots , X_n)\) represent the sequence of states of a discrete-time Markov chain with a finite state space \(M\). Then, a Markov chain satisfies the property \(P(X_{n+1} = x_{n+1} | X_n = x_n, X_{n-1} = x_{n-1}, \dots , X_0 = x_0)=P(X_{n+1}=x_{n+1}|X_n = x_n)\), for all \(x_0, x_1, \ldots, x_n, x_{n+1}\) and all \(n \ge 0\).

In Markov chains, we say that state \(j\) is reachable from state \(i\) if there exists a sequence of steps such that the Markov chain can transition from state \(i\) to state \(j\). Mathematically, state \(j\) is reachable from state \(i\) if there exists an integer \(n \ge 1\) such that the probability of transitioning from state \(i\) to state \(j\) in exactly \(n\) steps, \(P_n(i, j)\), is greater than zero.

To prove that state \(j\) can be reached from state \(i\) in \(M\) steps or less, we first assume that state \(j\) is reachable from state \(i\). We then need to show that there exists an integer \(n \le M\) such that the probability of transitioning from state \(i\) to state \(j\) in exactly \(n\) steps, \(P_n(i, j)\), is greater than zero.

Since state \(j\) can be reached from state \(i\), there exists a sequence of steps of length at most \(M-1\), such that the probability of transitioning from state \(i\) to state \(j\) is greater than zero. We can imagine a directed graph with nodes representing the states and edges signifying possible transitions between these states, where the edge weights represent the transition probabilities. Let's consider the longest path from state \(i\) to state \(j\) in this graph. Since we have \(M\) states, this path cannot have a length greater than \(M-1\) without visiting at least one state more than once. If there's a state that is visited more than once in the path, we can remove the loop composed of the extra visit and obtain a shorter path with non-zero probability, as the transition probabilities are non-negative. Therefore, there exists a path of length at most \(M-1\) between state \(i\) and state \(j\), which means that it can be reached in \(M\) steps or less.