3
$\begingroup$

Exercise 1.13 in the Levin-Peres-Wilmer book, http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf asks for a direct proof that the stationary distribution of an irreducible chain is unique. Note that Corollary 1.17 ibid. gives a very slick proof of this fact, but it's not "direct". They give a hint as follows: "Given stationary distributions $\pi_1$ and $\pi_2$, consider the state $x$ that minimizes $\pi_1(x)/\pi_2(x)$ and show that all $y$ with $P(x, y) > 0$ have $\pi_1(y)/\pi_2(y)=\pi_1(x)/\pi_2(x)$."

I couldn't get it to work and would appreciate additional hints.

$\endgroup$
  • $\begingroup$ I think you need to use the stationary equation $\pi(x) = \sum_z \pi(z) P(z,x)$ and also the fact that $a = b\frac{a}{b}$ for $b>0$. $\endgroup$ – Michael Jun 20 '17 at 21:04
  • $\begingroup$ One problem I have with this method is: (i) It assumes there exists such a minimizing state $x$ (this is not obvious for infinite state spaces), (ii) I find it easier to show this is true for all $y$ with $P(y,x)>0$, perhaps your hint had a typo or there is a parallel way to do it that uses the $P(x,y)$. $\endgroup$ – Michael Jun 20 '17 at 21:17
  • $\begingroup$ The chain is assumed to be on a finite state space. $\endgroup$ – Aryeh Jun 20 '17 at 21:33
  • $\begingroup$ @Michael I'm afraid I still don't follow. Where do you use the minimality of $\pi_1(x)/\pi_2(x)$? $\endgroup$ – Aryeh Jun 21 '17 at 8:01
  • $\begingroup$ Let $r = \min_z[a(z)/b(z)]$ so $a(z) \geq rb(z)$ for all $z$. $\endgroup$ – Michael Jun 21 '17 at 8:16
3
$\begingroup$

Let us give the full proof, which is the same as Aryeh's, but extends it so that it does not require that $P(z,x) > 0$ for all states $z$.

Hence, as in Aryeh's proof (repeated below for the sake of completeness), let us consider $a$ and $b$, two stationary distributions. Also let $x$ the minimizer of $z \mapsto a(z)/b(z)$ and call $r=a(x)/b(x)$. Clearly it has to be the case that $r < \infty$ since by stationarity and irreducibility it holds that $b(z) > 0$ for all $z$. We get:

$$ \begin{aligned} a(x) &= \sum_z a(z)P(z,x) \\ &= \sum_{z} \frac{a(z)}{b(z)}b(z) P(z,x) \\ &\geq \sum_{z} r b(z) P(z,x)\\ &= r \sum_z b(z) P(z,x) \\ &= r b(x)\\ &= a(x) \end{aligned} $$

But for equality to hold throughout the whole expression, we need equality to hold for all summands in the inequality ($\geq$) of line 3.

This implies that $\frac{a(z)}{b(z)}P(z,x) = rP(z,x)$ for all $z$. In particular, for all $z$ such that $P(z,x)>0$ we get that $\frac{a(z)}{b(z)}=r$.

However, to conclude, we need this to hold for all $z$, not just the ones with $P(z,x) > 0$.

Let us pick another $z$ such that $P(z,x)=0$. By irreducibility of the chain, there exists however some $n$ such that $P^n(z,x) > 0$, where $P^n$ denotes the $n$-step transition probabilities.

Repeating the same argument as above with the $n$-step Chapman-Kolmogorov equations (i.e. $a(x) = \sum_z a(z)P^n(z,x)$), we see that also $a(z)/b(z)=r$.

Hence $a(z)/b(z)=a(x)/b(x)$ holds for all states $z$, and since $\sum a(z)=\sum b(z)=1$ we conclude that $a=b$.

$\endgroup$
2
$\begingroup$

Following Michael's suggestions in the comments, I think no explicit assumptions of the type $P(x,y)>0$ are needed. Denoting $a:=\pi_1$ and $b:=\pi_2$, we have $$ a(x) = \sum_z a(z)P(z,x)\ge\sum_z rb(z)P(z,x)=rb(x).$$ But in fact $a(x)=rb(x)$, since $x$ was chosen to minimize the ratio $a(x)/b(x)$. This means that none of the inequalities $a(z)\ge rb(z)$ can be strong and in fact must all be equalities, whence $a=b$.

Edit: ack, the $P(z,x)>0$ assumption is needed to make that final conclusion.

$\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.