[proofplan] We must establish three things: that $\hat{P}$ is a stochastic matrix, that $\pi$ is invariant for $\hat{P}$, and that $Y = (Y_0, Y_1, \ldots, Y_N)$ is a Markov chain with initial distribution $\pi$ and transition matrix $\hat{P}$. For the first two claims, the key input is the invariance equation $\pi P = \pi$, which ensures the row sums of $\hat{P}$ equal one. For the Markov property, we compute the finite-dimensional distributions of $Y$ using the [Path Probability Formula](/theorems/2205) applied to the forward chain $X$, then convert each factor $\pi_{i_m} p_{i_m, i_{m-1}}$ into $\pi_{i_{m-1}} \hat{p}_{i_{m-1}, i_m}$ using the defining relation $\pi_i \hat{p}_{i,j} = \pi_j p_{j,i}$, yielding exactly the finite-dimensional distributions of a $\operatorname{Markov}(\pi, \hat{P})$ chain. [/proofplan] [step:Verify that $\hat{P}$ is a stochastic matrix] Since $X$ is irreducible and positive recurrent, the [Existence and Uniqueness of Invariant Distribution](/theorems/2223) guarantees that $\pi_i = 1/\mu_i > 0$ for every $i \in S$. Each entry $\hat{p}_{i,j} = \pi_j p_{j,i} / \pi_i$ is therefore well-defined and non-negative, because $\pi_j > 0$, $\pi_i > 0$, and $p_{j,i} \geq 0$. For the row sums, fix $i \in S$ and compute \begin{align*} \sum_{j \in S} \hat{p}_{i,j} = \sum_{j \in S} \frac{\pi_j}{\pi_i} p_{j,i} = \frac{1}{\pi_i} \sum_{j \in S} \pi_j p_{j,i}. \end{align*} The invariance equation $\pi = \pi P$ states that $\sum_{j \in S} \pi_j p_{j,i} = \pi_i$ for every $i \in S$. Substituting: \begin{align*} \sum_{j \in S} \hat{p}_{i,j} = \frac{\pi_i}{\pi_i} = 1. \end{align*} Hence every row of $\hat{P}$ sums to one, and $\hat{P}$ is a stochastic matrix. [guided] We need to check two things: every entry of $\hat{P}$ is non-negative, and every row sums to one. The first is immediate from the formula $\hat{p}_{i,j} = \pi_j p_{j,i} / \pi_i$, since all three quantities $\pi_j$, $p_{j,i}$, and $\pi_i$ are non-negative, and $\pi_i > 0$ (so the division is well-defined). The positivity $\pi_i > 0$ is not automatic for an arbitrary distribution -- it follows from the [Existence and Uniqueness of Invariant Distribution](/theorems/2223), which guarantees $\pi_i = 1/\mu_i > 0$ for every state $i$ in an irreducible, positive recurrent chain. The row-sum computation is where the invariance of $\pi$ is consumed. Fix any $i \in S$. We compute \begin{align*} \sum_{j \in S} \hat{p}_{i,j} = \sum_{j \in S} \frac{\pi_j}{\pi_i} p_{j,i} = \frac{1}{\pi_i} \sum_{j \in S} \pi_j p_{j,i}. \end{align*} The sum $\sum_{j \in S} \pi_j p_{j,i}$ is the $i$-th entry of the row vector $\pi P$. Since $\pi$ is invariant for $P$, the equation $\pi P = \pi$ gives $\sum_{j \in S} \pi_j p_{j,i} = \pi_i$. Substituting: \begin{align*} \sum_{j \in S} \hat{p}_{i,j} = \frac{\pi_i}{\pi_i} = 1. \end{align*} Why does this fail if $\pi$ is replaced by an arbitrary distribution $\lambda$? In that case, $\sum_j \lambda_j p_{j,i}$ need not equal $\lambda_i$, so the row sums of the matrix $\hat{p}_{i,j} = \lambda_j p_{j,i} / \lambda_i$ need not equal one. The invariance of $\pi$ is essential. [/guided] [/step] [step:Verify that $\pi$ is invariant for $\hat{P}$] Compute the $j$-th entry of $\pi \hat{P}$: \begin{align*} \sum_{i \in S} \pi_i \hat{p}_{i,j} = \sum_{i \in S} \pi_i \cdot \frac{\pi_j}{\pi_i} p_{j,i} = \pi_j \sum_{i \in S} p_{j,i} = \pi_j \cdot 1 = \pi_j, \end{align*} where the last equality uses the fact that $P$ is a stochastic matrix, so each row sums to one: $\sum_{i \in S} p_{j,i} = 1$. Hence $\pi \hat{P} = \pi$, and $\pi$ is invariant for $\hat{P}$. [guided] We want to show $(\pi \hat{P})_j = \pi_j$ for every $j \in S$. Substituting the definition $\hat{p}_{i,j} = \pi_j p_{j,i} / \pi_i$: \begin{align*} (\pi \hat{P})_j = \sum_{i \in S} \pi_i \hat{p}_{i,j} = \sum_{i \in S} \pi_i \cdot \frac{\pi_j}{\pi_i} p_{j,i} = \sum_{i \in S} \pi_j p_{j,i} = \pi_j \sum_{i \in S} p_{j,i}. \end{align*} The key cancellation is $\pi_i / \pi_i = 1$. The remaining sum $\sum_{i \in S} p_{j,i}$ runs over row $j$ of the stochastic matrix $P$, which sums to one by the [Properties of the Initial Distribution and Transition Matrix](/theorems/2204). Hence $(\pi \hat{P})_j = \pi_j$. Notice the structural asymmetry between the two verifications. In the previous step (row sums of $\hat{P}$), we used $\pi P = \pi$ and never used the row-sum property of $P$. Here, we use $\sum_i p_{j,i} = 1$ and never use the invariance of $\pi$. Each property of $\pi$ and $P$ is consumed exactly once. [/guided] [/step] [step:Compute the finite-dimensional distributions of $Y$ using the forward chain] Fix $0 \leq k \leq N$ and states $i_0, i_1, \ldots, i_k \in S$. By definition, $Y_m = X_{N-m}$, so \begin{align*} \mathbb{P}(Y_0 = i_0, Y_1 = i_1, \ldots, Y_k = i_k) = \mathbb{P}(X_N = i_0, X_{N-1} = i_1, \ldots, X_{N-k} = i_k). \end{align*} The event on the right specifies the values of $X$ at times $N-k, N-k+1, \ldots, N$. Since $X$ is a Markov chain started from $\pi$ (so that $X_0 \sim \pi$) and $\pi$ is invariant for $P$, the chain is stationary: $X_n \sim \pi$ for every $n \geq 0$, and in particular $X_{N-k} \sim \pi$. By the [Path Probability Formula](/theorems/2205) applied to the subsequence $(X_{N-k}, X_{N-k+1}, \ldots, X_N)$, the joint probability equals \begin{align*} \mathbb{P}(X_{N-k} = i_k, X_{N-k+1} = i_{k-1}, \ldots, X_N = i_0) = \pi_{i_k} \, p_{i_k, i_{k-1}} \, p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0}. \end{align*} [guided] We want $\mathbb{P}(Y_0 = i_0, \ldots, Y_k = i_k)$. By definition, $Y_m = X_{N-m}$, so this is $\mathbb{P}(X_N = i_0, X_{N-1} = i_1, \ldots, X_{N-k} = i_k)$. To apply the [Path Probability Formula](/theorems/2205), we need to express this as a joint probability of consecutive values of $X$. Rewriting the event in forward-time order: $(X_{N-k} = i_k, X_{N-k+1} = i_{k-1}, \ldots, X_N = i_0)$. The Path Probability Formula states that for a $\operatorname{Markov}(\lambda, P)$ chain, the joint probability of visiting states $j_0, j_1, \ldots, j_k$ at consecutive times $m, m+1, \ldots, m+k$ equals $\mathbb{P}(X_m = j_0) \cdot p_{j_0, j_1} \cdots p_{j_{k-1}, j_k}$, provided $X_m$ has a known marginal distribution. What is the marginal distribution of $X_{N-k}$? Since $X_0 \sim \pi$ and $\pi$ is invariant for $P$, the chain is stationary: for any $n \geq 0$, $\mathbb{P}(X_n = i) = (\pi P^n)_i = \pi_i$. In particular, $X_{N-k} \sim \pi$. Therefore the Path Probability Formula gives \begin{align*} \mathbb{P}(X_{N-k} = i_k, X_{N-k+1} = i_{k-1}, \ldots, X_N = i_0) = \pi_{i_k} \, p_{i_k, i_{k-1}} \, p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0}. \end{align*} Note carefully the index reversal: $Y_0 = i_0$ corresponds to $X_N = i_0$ (the last time), while $Y_k = i_k$ corresponds to $X_{N-k} = i_k$ (the earliest time). So the forward-chain product starts at $i_k$ and steps through $i_{k-1}, i_{k-2}, \ldots, i_0$. [/guided] [/step] [step:Convert to the reversed transition matrix via the identity $\pi_i \hat{p}_{i,j} = \pi_j p_{j,i}$] The defining formula $\hat{p}_{i,j} = \pi_j p_{j,i} / \pi_i$ can be rearranged to \begin{align*} \pi_j p_{j,i} = \pi_i \hat{p}_{i,j} \quad \text{for all } i, j \in S. \end{align*} Apply this identity to the rightmost factor in the product from the previous step, with $i = i_0$ and $j = i_1$: \begin{align*} \pi_{i_k} \, p_{i_k, i_{k-1}} \cdots p_{i_2, i_1} \cdot p_{i_1, i_0} = \pi_{i_k} \, p_{i_k, i_{k-1}} \cdots p_{i_2, i_1} \cdot \frac{\pi_{i_0} \hat{p}_{i_0, i_1}}{\pi_{i_0}} \cdot \frac{\pi_{i_0}}{\smash{1}}. \end{align*} More precisely, replace $p_{i_1, i_0} = \pi_{i_0} \hat{p}_{i_0, i_1} / \pi_{i_1}$ to obtain \begin{align*} \pi_{i_k} \, p_{i_k, i_{k-1}} \cdots p_{i_2, i_1} \cdot p_{i_1, i_0} = \pi_{i_k} \, p_{i_k, i_{k-1}} \cdots p_{i_2, i_1} \cdot \frac{\pi_{i_0}}{\pi_{i_1}} \hat{p}_{i_0, i_1}. \end{align*} Now replace $\pi_{i_1} p_{i_1, i_0}$ as a single unit. We proceed inductively from right to left. At each stage, the leading factor $\pi_{i_m}$ pairs with $p_{i_m, i_{m-1}}$ to produce $\pi_{i_{m-1}} \hat{p}_{i_{m-1}, i_m}$. Carrying this out for $m = k, k-1, \ldots, 1$: \begin{align*} \pi_{i_k} \, p_{i_k, i_{k-1}} \, p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0} &= \pi_{i_{k-1}} \hat{p}_{i_{k-1}, i_k} \, p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0} \\ &= \pi_{i_{k-2}} \hat{p}_{i_{k-2}, i_{k-1}} \hat{p}_{i_{k-1}, i_k} \, p_{i_{k-2}, i_{k-3}} \cdots p_{i_1, i_0} \\ &\;\;\vdots \\ &= \pi_{i_0} \, \hat{p}_{i_0, i_1} \, \hat{p}_{i_1, i_2} \cdots \hat{p}_{i_{k-1}, i_k}. \end{align*} [guided] The identity $\pi_j p_{j,i} = \pi_i \hat{p}_{i,j}$ is the algebraic engine of the proof. We use it to "peel off" forward-chain factors one at a time and replace them with reversed-chain factors. Let us carry out the induction explicitly. Starting from the product $\pi_{i_k} \, p_{i_k, i_{k-1}} \, p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0}$, apply the identity with $j = i_k$ and $i = i_{k-1}$: \begin{align*} \pi_{i_k} p_{i_k, i_{k-1}} = \pi_{i_{k-1}} \hat{p}_{i_{k-1}, i_k}. \end{align*} This replaces the first two factors $\pi_{i_k} p_{i_k, i_{k-1}}$ with $\pi_{i_{k-1}} \hat{p}_{i_{k-1}, i_k}$. The remaining factors $p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0}$ are unchanged, giving \begin{align*} \pi_{i_{k-1}} \hat{p}_{i_{k-1}, i_k} \cdot p_{i_{k-1}, i_{k-2}} \cdots p_{i_1, i_0}. \end{align*} Now apply the identity again with $j = i_{k-1}$ and $i = i_{k-2}$: \begin{align*} \pi_{i_{k-1}} p_{i_{k-1}, i_{k-2}} = \pi_{i_{k-2}} \hat{p}_{i_{k-2}, i_{k-1}}. \end{align*} This yields $\pi_{i_{k-2}} \hat{p}_{i_{k-2}, i_{k-1}} \hat{p}_{i_{k-1}, i_k} \cdot p_{i_{k-2}, i_{k-3}} \cdots p_{i_1, i_0}$. At each stage, the leading $\pi$ factor moves one index to the left, and one more forward-chain transition is converted to a reversed-chain transition. After $k$ applications (the last one converting $\pi_{i_1} p_{i_1, i_0} = \pi_{i_0} \hat{p}_{i_0, i_1}$), all forward-chain factors have been consumed, and we arrive at \begin{align*} \pi_{i_0} \, \hat{p}_{i_0, i_1} \, \hat{p}_{i_1, i_2} \cdots \hat{p}_{i_{k-1}, i_k}. \end{align*} The mechanism is a "telescoping" of the $\pi$ factors: $\pi_{i_k}$ is absorbed into the first conversion and replaced by $\pi_{i_{k-1}}$, which is then absorbed into the second conversion and replaced by $\pi_{i_{k-2}}$, and so on until $\pi_{i_0}$ remains as the sole leading factor. [/guided] [/step] [step:Conclude that $Y$ is $\operatorname{Markov}(\pi, \hat{P})$ by matching finite-dimensional distributions] Combining the results of the previous two steps: \begin{align*} \mathbb{P}(Y_0 = i_0, Y_1 = i_1, \ldots, Y_k = i_k) = \pi_{i_0} \, \hat{p}_{i_0, i_1} \, \hat{p}_{i_1, i_2} \cdots \hat{p}_{i_{k-1}, i_k}. \end{align*} This holds for all $0 \leq k \leq N$ and all states $i_0, \ldots, i_k \in S$. By the [Path Probability Formula](/theorems/2205), a process has initial distribution $\pi$ and transition matrix $\hat{P}$ if and only if its finite-dimensional distributions take exactly this product form. Since $\hat{P}$ is a stochastic matrix (verified in the first step), the [Path Probability Formula](/theorems/2205) applies, and we conclude that $Y$ is a Markov chain with initial distribution $\pi$ and transition matrix $\hat{P}$. Since $\pi$ is invariant for $\hat{P}$ (verified in the second step), this completes the proof that the reversed chain $Y$ is Markov with transition matrix $\hat{P}$ and that $\pi$ is invariant for $\hat{P}$. [guided] We have shown that the finite-dimensional distributions of $Y$ have the form \begin{align*} \mathbb{P}(Y_0 = i_0, Y_1 = i_1, \ldots, Y_k = i_k) = \pi_{i_0} \, \hat{p}_{i_0, i_1} \, \hat{p}_{i_1, i_2} \cdots \hat{p}_{i_{k-1}, i_k}. \end{align*} Why does this suffice? The [Path Probability Formula](/theorems/2205) provides a characterisation: a process $(Z_n)$ is a $\operatorname{Markov}(\lambda, Q)$ chain if and only if for every $k \geq 0$ and every choice of states $j_0, \ldots, j_k$, \begin{align*} \mathbb{P}(Z_0 = j_0, \ldots, Z_k = j_k) = \lambda_{j_0} \, q_{j_0, j_1} \cdots q_{j_{k-1}, j_k}. \end{align*} Our computation shows that $Y$ satisfies this characterisation with $\lambda = \pi$ and $Q = \hat{P}$. We verified in the first step that $\hat{P}$ is a stochastic matrix (non-negative entries, rows summing to one) -- this is a prerequisite for $\hat{P}$ to serve as a transition matrix. The Path Probability Formula then confirms that $Y$ is a Markov chain with the claimed initial distribution and transition matrix. Finally, the invariance $\pi \hat{P} = \pi$ (verified in the second step) completes the theorem: the reversed chain $Y$ is $\operatorname{Markov}(\pi, \hat{P})$, and $\pi$ is invariant for $\hat{P}$. [/guided] [/step]