Proving a formula for the stationary distribution of a finite irreducible Markov chain

Question

Let $\{X_n\}_{n=1}^{\infty}$ be an irreducible Markov chain on a finite state space $S = \{1,2,\ldots,N\}$. Let $P$ be its transition matrix (i.e. $P_{ij} = P(X_{n+1} = j | X_n = i)$ for all $(i,j) \in S^2$). Show that the Markov chain has a (unique) stationary distribution given by $$\pi = (1,1,\ldots,1) (I - P + Q)^{-1},$$ where $I$ is the $N \times N$ identity matrix and $Q$ is the $N \times N$ matrix whose entries are all 1.

My attempt: I take it for granted (by a theorem in my text) that a finite irreducible Markov chain has a unique stationary distribution (i.e. there exists a probability vector $\pi$ such that $\pi P = \pi$), so I'm just trying to show that the above formula for $\pi$ is correct.

First I establish that $(I-P+Q)$ is invertible: Suppose $\vec{0} = (I-P+Q)\vec{x}$. This implies that \begin{align*} \vec{0} &= \vec{x} - P \vec{x} + Q \vec{x} \\[2pt] &= \pi \vec{x} - \pi P \vec{x} + \pi Q \vec{x} && \text{(Multiplying by } \pi \text{ on the left}) \\[2pt] &= \pi \vec{x} - \pi \vec{x} + \pi Q \vec{x} && (\pi P = \pi) \\[2pt] &= \pi Q \vec{x}. \end{align*} So we have $\vec{0} = \pi Q \vec{x}$. By a theorem from my text, the entries of $\pi$ are strictly positive, so it follows that $\vec{0} = Q \vec{x}$. Substituting this into the first of the above equations gives $\vec{0} = \vec{x} - P \vec{x}$, which implies $P \vec{x} = \vec{x}$. Therefore, $Q \vec{x} - P \vec{x} = (Q-P)\vec{x} = -\vec{x}$. Now since $Q_{ij} = 1$ and $0 \leq P_{ij} \leq 1$ for all $(i,j)$, the entries of the matrix $Q-P$ are all nonnegative. Thus, the only way for $(Q-P) \vec{x} = -\vec{x}$ to be true is if $\vec{x} = 0$. And this shows that $(I-P+Q)\vec{x} = \vec{0} \implies \vec{x} = \vec{0}$, and so $(I-P+Q)$ is invertible.

At this point I got stuck. I don't see how to show the given formula for $\pi$. Of course the most direct approach would be to show that $$(1,1,\ldots,1) (I-P+Q)^{-1} P = (1,1,\ldots,1) (I-P+Q)^{-1}, $$ but I have no idea how to proceed with this. Any help would be greatly appreciated!

Answer 1

so $Q = \mathbf {11}^T$ and you are satisfied that $(I-P+Q)^{-1}$ exists.

The easy approach is to compute the 'inverse problem'
$\mathbf \pi^T(I-P+Q) = \mathbf \pi^T -\mathbf \pi^TP +\mathbf \pi^T\mathbf {11}^T = \mathbf \pi^T - \mathbf \pi^T +\mathbf 1^T =\mathbf 1^T$

multiplying each side on the right by $(I-P+Q)^{-1}$ gives
$\mathbf \pi^T = \mathbf 1^T(I-P+Q)^{-1}$
as desired

re Invertibility:
an easy approach is to consider applying Schur Triangularization with unitary

$V := \bigg[\begin{array}{c|c|c|c}\frac{1}{\sqrt{n}}\mathbf 1 & \mathbf v_2 &\cdots & \mathbf v_{n}\end{array}\bigg]$
$P=VRV^{-1}=VRV^{*}$
where $R=\begin{bmatrix} 1 & \mathbf x_{n-1}^T\\ \mathbf 0 & \mathbf R_{n-1} \end{bmatrix}$ and $\det\big(I_{n-1}-\mathbf R_{n-1}\big)\neq 0$
(because the Peron root is simple by irreducibility)

$I-P+\mathbf{11}^T = \mathbf V\big(I -R +n\mathbf e_1\mathbf e_1^T\big)V^*$
$\longrightarrow\det\big(I-P+\mathbf{11}^T\big) = n \cdot \det\big(I_{n-1} -\mathbf R_{n-1}\big)\neq 0$

Answer 2

(This is a long comment.) In your proof of the invertibility of $I-P+Q$, you wrote:

the entries of the matrix $Q-P$ are all nonnegative. Thus, the only way for $(Q-P) \vec{x} = -\vec{x}$ to be true is if $\vec{x} = 0$.

This isn't quite correct. For instance, $-1$ is an eigenvalue of $Q-P=\pmatrix{0&1\\ 1&0}$ when $P=I_2$.

You need to use the condition that $P$ is irreducible. Suppose $(I-P+Q)x=0$. Then $\mathbf1^Tx=0$: \begin{aligned} 0 &=\mathbf\pi^T(I-P+\mathbf 1\mathbf1^T)x\\ &=\mathbf\pi^Tx-(\mathbf\pi^TP)x+(\mathbf\pi^T\mathbf 1)(\mathbf1^Tx)\\ &=\mathbf\pi^Tx-\mathbf\pi^Tx+\mathbf1^Tx\\ &=\mathbf1^Tx. \end{aligned} It follows that $0=(I-P+\mathbf 1\mathbf1^T)x=x-Px$. That is, $Px=x$. Hence $x$ lies in the eigenspace of $P$ corresponding to the eigenvalue $1$. However, as $P$ is an irreducible row-stochastic matrix, $x$ must be a scalar multiple of $\mathbf1$, by Perron-Frobenius theorem. The equality $\mathbf1^Tx=0$ thus implies that $x=0$. Therefore $I-P+Q$ is invertible.