2
$\begingroup$

I am trying to understand the following proof that every finite-state Markov chain has a stationary distribution. The proof is from here.

Let $P$ be the $k \times k$ (stochastic) transition probability matrix for our Markov chain. Now,

... $1$ is an eigenvalue for $P$ and therefore also for $P^t$ . Writing a $P^t$ invariant $v$ as $v = v^+ − v^−$ with $v^+ , v^− \in ( > \mathbb{R}_+ )^k$ , we obtain $P^t v^± = v^±$ because $P^t$ preserves the positive cone; if $v^+\neq 0$ take $ν = ( \sum v^+_i )^{-1} · v^+,$ otherwise normalize $v^−$.

The main thing I don't understand is

we obtain $P^t v^± = v^±$ because $P^t$ preserves the positive cone

Why is this true?

I also don't understand why $( \sum v^+_i )^{-1} · v^+$ works if $v^+ \neq 0$.

Is there any easier way to show that every finite state Markov chain has a stationary probability distribution?

$\endgroup$
  • $\begingroup$ For your second question, what must a state distribution vector look like and what can you say about the elements of the scaled version of $v^+$? $\endgroup$ – amd Dec 2 '18 at 0:23
  • $\begingroup$ They add up to 1, makes sense. I get that part now $\endgroup$ – jackson5 Dec 2 '18 at 0:25
1
$\begingroup$

The wording in this article is a little ambiguous. I thought of two interpretations, the first of which is incorrect. The second is correct but it doesn't explain the bit about "preservation of the positive cone".

It looks like it may be a case of mistakenly using that a mapping fixes a subset when it only preserves a subset. (I.e. $f|_X = \text{id}_X$ vs $\text{im}(f) \subset X$.)

Interpretation 1. Maybe the statement below is being claimed:

(*) Let $C$ be the positive cone. If $P^tv = v$ then for all $v^+,v^- \in C$ such that $v = v^+ - v^-$ we have $P^tv^+ = v^+$.

This is false unless $P$ is the identity matrix. Let $x \in C$, then according to (*) then $\bar v^\pm = v^\pm + x$ must satisfy $P^t\bar v^+ = \bar v^+$ as well. But linearity says then $P^tx = x$ too. So $P^t$ fixes the positive cone. This is only true if $P$ is the identity matrix because the span of the positive cone is the whole space.

Interpretation 2. Maybe instead it means to set $v^+$ to be the vector of positive entries of $v$ with 0s in place of negatives. E.g. if $v = (1,0,2,-7)$ then $v^+ = (1,0,2,0)$ and $v^- = (0,0,0,7)$. Then the claim would be:

If $P^tv = v$ then we have $P^tv^+ = v^+$ where $v^+$ is the vector of positive entries described above.

This is true, but I don't think the cited article offers any explanation as to why, and I don't know how to prove it without using Frobenius-Perron, which is maybe a harder theorem than the one we are trying to prove.

It is a trivial consequence of Frobenius-Perron in the case of an irreducible stochastic matrix, because one has either $v = v^+$ or $v = v^-$. This is because there is a stationary state $v$ (by F-P) and the eigenspace for $\lambda = 1$ is simple (also F-P). So any invariant vector is a scalar multiple of it and also has this property.

For reducible matrices the eigenspace for $\lambda = 1$ is no longer simple, so we can do things like $v = v_1 - v_2$ where $v_i$ is the stationary state for the $i$th block. Then $v^+ = v_1, v^- = v_2$. Following the suggestion in the article, one would then find a stationary distribution by normalizing just the positive part $v^+ = v_1$.

$\endgroup$
0
$\begingroup$

To your last question, as to whether there is a simpler way of proving existence of a stationary distribution for finite state Markov chains, that depends what tools you have at your disposal. Here is a nice and short consequence of a fixed point theorem:

Let a Markov chain $\mathbf{P}$ over $d$ states. The simplex $\Delta_d$ is a convex and compact subset of $\mathbb{R}^d$, which is a Euclidean vector space with usual inner product. We can look at the kernel as the following linear operator, \begin{equation} \begin{split} \mathbf{P} : \Delta_d &\to \Delta_d \\ \mu &\mapsto \mu \mathbf{P} \end{split} \end{equation} As $\|\mathbf{P}\|_2 \leq \sqrt{d} < \infty$, the operator is bounded and therefore continuous. As a consequence, we can apply Brouwer's fixed point theorem to show that $\exists \pi \in \Delta_d, \pi \mathbf{P} = \pi$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.