Question

Let a Markov chain contain \(r\) states. Prove the following: (a) If a state \(k\) can be reached from \(j\), then it can be reached in \(r-1\) steps or less. (b) If \(j\) is a recurrent state, there exists \(\alpha(0<\alpha<1)\) such that for \(n>r\) the probability that first return to state \(j\) oeeurs after \(n\) transitions is \(\leq \alpha^{n}\).

Short answer

In summary, for a Markov chain with \(r\) states: (a) If state \(k\) can be reached from state \(j\), then it can be reached in \(r-1\) steps or less, as proven by the Pigeonhole Principle. (b) If state \(j\) is recurrent, there exists a constant \(\alpha\) (\(0 < \alpha < 1\)) such that for \(n > r\), the probability of first returning to state \(j\) after \(n\) transitions is less than or equal to \(\alpha^{n}\), as demonstrated through the properties of the Markov chain and the definition of a recurrent state.

Step-by-step solution

Understanding the problem

A Markov chain is a stochastic process that satisfies the Markov property, which states that the future state depends only on the present state and not on the previous states. In this context, we have a Markov chain with r states. Now we have to prove two statements about this Markov chain.

Prove statement (a) using the Pigeonhole Principle

To show that if state k can be reached from state j, then it can be reached in r-1 steps or fewer, let's consider the following: After (r-1) steps, state j can reach at most (r-1) other states. Now, if state k cannot be reached within (r-1) steps, then after exactly r steps, state j would have to reach at least r different states, which is not possible as our Markov chain has only r states. Using the Pigeonhole Principle, we can deduce that state k must be reachable within r-1 steps or fewer.

Prove statement (b) by defining a recurrent state and using Markov chain properties

A recurrent state is a state that once reached, will be reached again with probability 1. In other words, if we are at state j, we will eventually return to state j with certainty. Let P_j(n) be the probability of returning to state j for the first time after exactly n transitions. We have to find a constant α (0 < α < 1) such that P_j(n) <= α^n for n > r. We know that state j is recurrent, and since there are r states in the Markov chain, we can write: P_j(n) = P(State j is reached for the first time after n transitions) By using the Markov chain properties, we can express P_j(n) in terms of the transition probabilities: \(P_j(n) = \sum_{i=1}^{r} P_j(i)P(i, j, n-i)\) Now, we can find an upper bound for P_j(n) by considering the maximum of the transition probabilities involved in this expression: \(P_j^{max} = max\{P_j(i)\}\) \(P^{max}(i, j, n-i) = max\{P(i, j, n-i)\}\) Using these maximum probabilities, we can say: \(P_j(n) \leq \sum_{i=1}^{r} P_j^{max} P^{max}(i, j, n-i) = rP_j^{max}P^{max}(i, j, n-r)\) Now, since \(0 < P_j^{max} < 1\) and \(0 < P^{max}(i, j, n-r) < 1\), we can say that there exists α = rP_j^{max}P^{max}(1, j, n-r), which satisfies the condition \(0 < α < 1\), and for n > r: \(P_j(n) \leq \alpha^n\) This completes the proof of statement (b).