Question

A Markov chain is said to be a tree process if (i) \(\quad P_{i j}>0\) whenever \(P_{j i}>0\), (ii) for every pair of states \(i\) and \(j, i \neq j\), there is a unique sequence of distinct states \(i=i_{0}, i_{1}, \ldots, i_{n-1}, i_{n}=j\) such that $$ P_{i_{k}, i_{k+1}}>0, \quad k=0,1, \ldots, n-1 $$ In other words, a Markov chain is a tree process if for every pair of distinct states \(i\) and \(j\) there is a unique way for the process to go from \(i\) to \(j\) without reentering a state (and this path is the reverse of the unique path from \(j\) to \(i\) ). Argue that an ergodic tree process is time reversible.

Short answer

In conclusion, an ergodic tree process is time-reversible because, for any two distinct states i and j, there exists a unique path between them, and the joint probabilities of the forward and backward paths are the same. With some manipulation, this observation results in the time-reversibility condition, \( \pi_i P_{i j} = \pi_j P_{j i} \), being satisfied for all i and j. Hence, an ergodic tree process is time reversible.

Step-by-step solution

Define Time-Reversibility

Time-reversibility can be defined mathematically for a Markov chain as follows: If there exists a probability distribution \( \pi_i > 0 \), for all states i such that, \( \pi_i P_{i j} = \pi_j P_{j i} \) for all states i and j, then the Markov chain is time-reversible.

Identify Conditions for Time-Reversibility

To establish that an ergodic tree process is time-reversible, we must show that there exists a probability distribution \( \pi_i > 0 \) which satisfies the time-reversibility condition mentioned in step 1.

Proving an Ergodic Tree Process is Time-Reversible

As given in the exercise, a Markov chain is a tree process if it satisfies two conditions: (i) For every pair of states i and j, if \( P_{j i}>0 \), then \( P_{i j}>0 \) (ii) For each pair of distinct states i and j, there is a unique sequence of distinct states to go from i to j and vice versa. Since the tree process is ergodic, it must be irreducible and aperiodic. To prove time-reversibility, let's consider any two distinct states i and j in the ergodic tree process. As per the definition of tree process, there exists a unique path such that \( P_{i_{k}i_{k+1}} > 0 \) for all \( k = 0,1,...,n-1 \). Now, let's compute the joint probabilities for the forward and backward paths: Forward path \(P(i_i, i_2, \ldots, i_{n-1}, i_n )=\pi_{i_1}P_{i_1 i_2}\cdots P_{i_{n-1} i_n}\) Backward path \(P(i_n, i_{n-1}, \ldots, i_2, i_1 )=\pi_{i_n}P_{i_n i_{n-1}}\cdots P_{i_2 i_1}\) Since there is no loop in the tree process, the forward and backward paths are the same. Thus, \( \pi_{i_1}P_{i_1i_2}\cdots P_{i_{n-1}i_n} = \pi_{i_n}P_{i_n i_{n-1}}\cdots P_{i_2i_1} \) Now, let's rearrange the terms: \( \frac{\pi_{i_n}}{\pi_{i_1}} = \frac{P_{i_1i_2} \cdots P_{i_{n-1}i_n}}{P_{i_n i_{n-1}} \cdots P_{i_2 i_1}} \) Taking the first part of the unique path we get, \( \frac{\pi_{i_{1}}}{\pi_{i_{0}}} = \frac{P_{i_0 i_1}}{P_{i_1i_0}} \) Such a relationship can be generalized for all i and j with \( (\pi_i P_{i j} = \pi_j P_{j i}) \), which satisfies the definition of time-reversibility. Hence, we have proved that an ergodic tree process is time reversible.