Question

Prove that if the number of states in a Markov chain is \(M\), and if state \(j\) can be reached from state \(i\), then it can be reached in \(M\) steps or less.

Short answer

In a Markov chain with $M$ states, if state $j$ can be reached from state $i$, 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. This is because the longest possible path, represented by a directed graph with nodes for states and edges for transitions, cannot exceed $M-1$ steps without visiting a state more than once. Removing any loop with a revisit results in a shorter path with non-zero probability, proving that state $j$ can be reached in $M$ steps or less.

Step-by-step solution

Define the Markov chain and its properties

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\).

Reachability in Markov chains

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.

Formulating the proof

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.

Proving the statement

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.