Invertibility in Markov processes

Question

In literature, it is written for Discrete Time Markov processes, if there exists unique stationary distribution $\Pi$, then this distribution can be obtained by following formula $$ \Pi^\top = \mathbf1^\top (P-I+\mathbf1\mathbf1^\top)^{-1}, $$ where $P$ is transition probability matrix and $I$ is identity and $\mathbf1$ is all ones vector. How can we guarantee that $(P-I+\mathbf1\mathbf1^\top)$ is always invertible? They usually mention it, but I have never seen proof. How this can be proven?

Answer 1

Suppose $P$ has a unique stationary distribution $\Pi$ and

\begin{equation} (P-I+\mathbf1\mathbf1^\top)x=0\label{eq:1}\tag1 \end{equation}

for some vector $x$. In particular,

\begin{equation} \Pi^\top P=\Pi^\top \qquad\text{and}\qquad \Pi^\top\mathbf1=1\,. \end{equation}

Multiplying Equation \ref{eq:1} by $\Pi^\top$ and substituting the last two identities yields

\begin{align} 0 &=\Pi^\top(P-I+\mathbf1\mathbf1^\top)x=(\Pi^\top P)x-\Pi^\top x+(\Pi^\top\mathbf1)\mathbf1^\top x=\Pi^\top x-\Pi^\top x+\mathbf1^\top x \\ &=\mathbf1^\top x\,.\label{eq:2}\tag2 \end{align}

Substituting back into Equation \ref{eq:1} yields

\begin{equation} 0=Px-x+\mathbf1\cdot0\implies x=Px\,. \end{equation}

Because $P$ has a unique stationary distribution, it has a unique closed communicating class $C$. Let $x_i$ be the largest element of $x$ such that $i\in C$ and $x_j$ be an arbitrary element of $x$ such that $j\in C$. Then there exists $n$ such that $P^n_{ij}>0$, so that

\begin{align} x=Px &\implies x=P^nx \\ &\implies x_i=P^n_{ij}x_j+\sum_{k\in C\setminus\{j\}}P^n_{ik}x_k && C \text{ is closed} \\ &\implies x_i\le P^n_{ij}x_j+\sum_{k\in C\setminus\{j\}}P^n_{ik}x_i && x_k\le x_i\\ &\implies x_i\le P^n_{ij}x_j+(1-P^n_{ij})x_i && \sum_{k\in C}P^n_{ik}=1 \\ &\implies P^n_{ij}x_i\le P^n_{ij}x_j \\ &\implies x_i\le x_j && P^n_{ij}>0\\ &\implies x_i=x_j\,, && x_i\ge x_j \end{align}

so for all $j\in C$, $x_j=x_i$, which we will call $r$.

For $i\notin C$, define

\begin{equation} p^{(n)}_i=\sum_{j\in C}P^n_{ij}\,. \end{equation}

Viewing $C$ as an absorbing set of states, $\lim_{n\rightarrow\infty}p^{(n)}_i=1$. Let $M=\max_i |x_i|$. Then $\forall i\in C$, $\forall\varepsilon>0$, $\exists N$ such that $\left|1-p^{(N)}_i\right|<\frac\varepsilon{|r|+M+1}$, so that

\begin{align} |x_i-r| &=\left|P^Nx_i-r\right| \\ &=\left|\sum_{j\in C}P^N_{ij}x_j+\sum_{k\notin C}P^N_{ik}x_k-r\right| \\ &\le\left|\sum_{j\in C}P^N_{ij}x_j-r\right|+\left|\sum_{k\notin C}P^N_{ik}x_k\right| \\ &\le\left|p^{(N)}_ir-r\right|+\left|1-p^{(N)}_i\right|M && x_j=r \text{ and } |x_k|\le M \\ &= \left|1-p^{(N)}\right|(|r|+M) \\ &<\varepsilon\,. \end{align}

Taking the limit as $\varepsilon\rightarrow0$ yields $x_i=r$. Then all elements of $x$ are equal to $r$, so by Equation \ref{eq:2},

\begin{equation} \mathbf1^\top x=0\implies r=0\implies x=0\,. \end{equation}

Then Equation \ref{eq:1} has only the trivial solution, so $P-I+\mathbf1\mathbf1^\top$ is invertible.

Answer 2

I don't really understand what $\mathbf{11}^T$ is but what might be helpful is Gershgorin's Circle Theorem.

It might allow you to bound the eigenvalues away from zero.