Question

Given a finite aperiodic irreducible Markov chain, prove that for some \(n\) all torms of \(P^{3}\) are positive.

Short answer

Given a finite aperiodic irreducible Markov chain, we want to prove that for some power \(n\) of the transition probability matrix \(P\), all terms of \(P^n\) are positive. Using the properties of finite, aperiodic, and irreducible Markov chains, we find a common power of \(P\) for all state pairs. We then choose \(n = 3 * k_{max}\) and express the nth power of the transition probability matrix as \(P^n = (P^3)^{k_{max}}\). By showing that all the terms of \(P^n\) are positive, we can conclude that all the terms of \(P^3\) are also positive.

Step-by-step solution

Understand Properties of Finite, Aperiodic, and Irreducible Markov Chains #

A Markov chain is a stochastic process that satisfies the Markov property, which means that future states only depend on the current state and not on the past states. In this exercise, we are concerned with finite, aperiodic, and irreducible Markov chains. Let's understand what these properties mean: 1. Finite: A Markov chain is finite if it has a finite number of states. In our case, we can define a finite state space as \(S = \{s_1, s_2, ..., s_n\}\), where \(n\) is the number of states. 2. Aperiodic: A state \(i\) in a Markov chain is said to be aperiodic if the greatest common divisor of the set of all time steps that the two visits to the state \(i\) is 1. In simpler terms, a state is aperiodic if it doesn't have a fixed period. A Markov chain is aperiodic if all its states are aperiodic. 3. Irreducible: A Markov chain is irreducible if there exists a non-zero probability of transitioning between any two states after a finite number of steps. This means that for any pair of states \(i\) and \(j\), there exists some \(k>0\) such that the transition probabilities are positive: \(P_{ij}^{(k)}>0\). Now that we've understood these properties, let's continue with the proof.

Find a Common Power of P for All State Pairs #

Since the given Markov chain is finite, aperiodic, and irreducible, we know that there is some non-zero probability of transitioning between any two states after a finite number of steps. To simplify the proof, we will try to find a common power of the transition probability matrix \(P\) that works for all possible state pairs. Since the Markov chain is irreducible, for every pair of states \(i\) and \(j\), there exists some positive integer \(k_{ij}\) such that \(P_{ij}^{(k_{ij})}>0\). Note that \(k_{max} = max\{k_{ij}\}\) is also finite since there are finitely many state pairs in our Markov chain.

Prove That P^(3) Has All Positive Entries #

In this step, we are going to show that for \(n=3\), the matrix \(P^n\) has all positive entries. Let \(n = 3 * k_{max}\). Now, we can write down the nth power of the transition probability matrix as follows: \[P^n = (P^3)^{k_{max}}\] We will show that all the terms of \(P^3\) are positive. Consider any two states \(i\) and \(j\). Since the Markov chain is irreducible, we know that there is some positive integer \(k_{ij}\) such that \(P_{ij}^{(k_{ij})}>0\). Moreover, due to aperiodicity, this property extends to all multiples of \(k_{ij}\). In other words, for any positive integer \(m\), we have: \(P_{ij}^{(m*k_{ij})}>0\) For our proof, we will choose \(m=k_{max}\) and hence, \(P_{ij}^{(k_{max}*k_{ij})}>0\) But we already know that \(n=3*k_{max}\), so we can rewrite the above equation as: \(P_{ij}^{(n)}>0\) Now, since all the terms of \(P^n\) are positive, and we expressed \(P^n = (P^3)^{k_{max}}\), it implies that all the terms of the matrix \(P^3\) are also positive. That concludes our proof. We have shown that for a given finite aperiodic irreducible Markov chain, all the terms of the matrix \(P^3\) are positive.