Given a transition matrix for markov chain $ P \in \mathbb R^{dxd} $ such that $$ P_{i,j} \geq 0,\quad
1 \leq (i,j) \leq d, \quad
\sum_{j=1 \in d }P_{i,j} $$
and $i=1,….,d$.
Let $ x_{0}$ be probability vector and
$$ x_{0} \in \mathbb R^{d},\quad \sum_{j=1 \in d} x_{i} =1, \quad x_{k+1} = Px_{k},\quad k \in \mathbb N_{0} $$
given that vector
$ x^{*}$ is an equilibrium such that
$$ Px^{*} =x^{*},\quad x^{*}\geq 1 ,\quad \sum_{j=1 \in d } x_{i}^{*} = 1 .$$
I want to use Farkas' lemma to proof the existence of equilibrium vector $x^{*}$.
I'm assuming I should derive a system of equations that must be satisfied or otherwise $x_{0} \in $ some conic combination but I'm struggling to derive that
Best Answer
Let $P$ be a $d \times d$ stochastic matrix, i.e., all the entries are nonnegative and $\sum_{j=1}^d P_{ij}=1$ for all $i \in [1,d]$. The goal is to show there exists a probability vector $x \in {\mathbb R}^d$ so that $P^Tx=x$. Let $A$ be the $d+1$ times $d$ matrix whose first $d$ rows coincide with $I-P^T$, and the last row of $A$ is the all ones vector. Let $b \in {\mathbb R^{d+1}}$ be the vector consisting of $d$ zeros followed by a single $1$. Then the goal is equivalent to proving existence of $x \in {\mathbb R^d}$ such that $$x \ge 0\,, \qquad Ax=b \,. \tag{1}$$ By Farkas' Lemma [1], it suffices to prove that there is no $y \in {\mathbb R^{d+1}}$ that satisfies the inequalities $$A^Ty \ge 0 \,, \qquad b^T y <0 \,. \tag{2} $$ The system $(2)$ can be rewritten as $$(I-P)\widetilde{y}+y_{d+1}{\bf 1} \ge 0 \,, \qquad y_{d+1} <0 \,, \tag{3}$$ where $\widetilde{y} \in {\mathbb R}^d$ is the projection of $y$ to the first $d$ coordinates, and ${\bf 1}$ is the all ones column vector of length $d$. Suppose that $y \in {\mathbb R^{d+1}}$ satisfies $(3)$ and that $y_k=\min_{i \in [1,d]} y_i$. Then any weighted average of $y_1,\ldots,y_d$ is at least $y_k$, so $y_k-(P\widetilde{y})_k \le 0$, and row $k$ of $(3)$ yields a contradiction. Since there is no solution to $(2)$, the goal $(1)$ must have a solution.
[1] https://en.wikipedia.org/wiki/Farkas%27_lemma