Exercise 4.31 (Unit eigenvectors of stochastic matrices)

Question

We say that an n$	imes$n matrix P,with entries $P_{ij}$, is stochastic if all of its entries are nonnegative
and

$$\displaystyle \sum_{i=1}^n P_{ij} = 1,\quad \forall i,$$

that is, the sum of the entries of each row is equal to 1.
Use duality to show that if P is a stochastic matrix, then the system of equations 
$$p^{\prime}P = p^{\prime}, \quad p \geq 0,$$ 
has a nonzero solution. (Note that the vector p can be normalized so that its
components sum to one. Then, the result in this exercise establishes that every
finite state Markov chain has an invariant probability distribution.)

Aqa Arman · Accepted Answer

$$p^{\prime}P = p^{\prime},\quad p^{\prime} \geq 0 \iff p^{\prime}(P-I)=0,\quad p^{\prime} \geq 0$$

\begin{center}
\begin{tabular}{c c c}
    max $\sum p_i$ &
    &
    min $0^{\prime}x$ \
    $p^{\prime}(P-I)=0$ & 
    $\overset{dual}{\iff}$ &
    $(P-I)x \geq \mathbbm{1}$\
    $p\geq 0$
\end{tabular}
\end{center}

If we show that primal is infeasible, using strong duality and the fact that  $0\in 	ext{(D)} 
eq \phi$, we can show that dual optimum is $+\infty$. Then there exists a p for each h such that $\sum p_i > h$ so $\exists p
eq 0$. \
Let us assume otherwise and have a $x\in 	ext{primal}$. 
$$(P-I)x \geq \mathbbm{1} \implies Px = x + \mathbbm{1} \ \implies Px = [P_1^{\prime}x, ..., P_n^{\prime}x]^{\prime}$$
Note that $\sum_j P_{ij} = 1, P_{ij}\geq 0$. So we have:
$$Px\leq [max(x),..., max(x)] := ho \qquad 	ext{where max(x) is the maximum element of vector x.}$$ 
If $i^* = argmax(x)$, then it is obvious that 
$$ho_{i^*} < (x+\mathbbm{1})_{i^*} = (Px)_{i^*}$$
which is a contradiction

Neeraj · Answer

Let $P \in \mathbb{R}^{n \times n}$ be a stochastic matrix, i.e., $P_{ij} \geq 0$ and $\sum_{j=1}^n P_{ij} = 1$ for all $i$. We aim to show that the system
$$
p^\top P = p^\top, \quad p \geq 0, \quad p \neq 0
$$
has a solution.

This is equivalent to finding a nonzero $p \geq 0$ such that
$$
p^\top (P - I) = 0.
$$
Let $A := P^\top - I$. Then we seek $x \geq 0$, $x \neq 0$, with $A x = 0$.

By Farkas' Lemma, exactly one of the following holds:
\begin{align*}
\text{(i)} &\quad A x = 0, \ x \geq 0, \ x \neq 0, \
\text{(ii)} &\quad \exists y \in \mathbb{R}^n \text{ such that } y^\top A > 0.
\end{align*}

We will show that (ii) is not possible. Suppose $y^\top A > 0$, i.e.,
$$
y^\top(P^\top - I) = (P y - y)^\top > 0 \quad \Rightarrow \quad P y > y \text{ (componentwise)}.
$$
But since $P$ is stochastic, each row is a convex combination of the entries of $y$, so $P y \leq \max_j y_j$. Hence, $P y > y$ is impossible.

Thus, (ii) has no solution, and by Farkas' Lemma, (i) holds. Therefore, there exists $x \geq 0$, $x \neq 0$ such that $A x = 0$, i.e., 
$$
(P^\top - I) x = 0 \Rightarrow P^\top x = x \Rightarrow x^\top P = x^\top.
$$
Hence, $x \geq 0$, $x \neq 0$ is a solution to the system $p^\top P = p^\top$, $p \geq 0$.
\qed

max $\sum p_{i}$		min $0^{'} x$
$p^{'} (P - I) = 0$	$\overset{dual}{⟺}$	$(P - I) x \geq 1$
$p \geq 0$

Exercise 4.31 (Unit eigenvectors of stochastic matrices)

Answers

Comments

Comments

Exercise 4.31 (Unit eigenvectors of stochastic matrices)

Answers

Comments

Comments

Add answer