8
$\begingroup$

The theorem is "If a transition matrix for an irreducible Markov chain with a finite state space S is doubly stochastic, its (unique) invariant measure is uniform over S."

If a Markov Chain has a doubly-stochastic transition matrix, I read that its limiting probabilities make up the uniform distribution, but I do not quite understand why.

I have been trying to come up with, and locate, an understandable proof for this. But the proofs I find all gloss over details I don't understand, like proposition 15.5 here (why does it work to just use the [1,...1] vectors?) Could someone point me to (or write) a more simple/detailed proof?

(Though not part of anything I will hand in at school, it is part of a course I'm taking so I guess I'll tag it with homework in either case.)

$\endgroup$
  • $\begingroup$ Perron-Frobenius. $\endgroup$ – cardinal Sep 21 '12 at 10:30
  • 1
    $\begingroup$ @cardinal Why not make it an answer with a little elaboration? $\endgroup$ – Michael Chernick Sep 21 '12 at 16:34
  • 1
    $\begingroup$ You are missing the necessary conditions that the Markov Chain is irreducible and not periodic. These can be combined into the condition that for some $n$, every entry of $P^n$ is positive. There are finitely many, so say all are at least $c$. You can bound the convergence rate in terms of $c$. $\endgroup$ – Douglas Zare Sep 21 '12 at 17:45
  • $\begingroup$ You're right, Douglas. I have now copied the proposition in the linked PDF verbatim to avoid any confusion. Thanks. $\endgroup$ – Christian Neverdal Sep 21 '12 at 23:21
4
$\begingroup$

Suppose we have an $M+1$-state irreducible and aperiodic Markov chain, with states $m_j$, $j=0,1,\ldots, M$, with a doubly stochastic transition matrix (i.e., $\sum_{i=0}^M P_{i,j}=1$ for all $j$). Then the limiting distribution is $\pi_j=\frac{1}{M+1}$.

Proof

First note that the $\pi_j$ is the unique solution to $\pi_j=\sum_{i=0}^M \pi_iP_{i,j}$ and $\sum_{i=0}^M\pi_i=1$.

Try $\pi_i=1$. This gives $\pi_j=\sum_{i=0}^M \pi_iP_{i,j}=\sum_{i=0}^M P_{i,j}=1$ (because the matrix is doubly stochastic). Thus $\pi_i=1$ is a solution to the first set of equations, and to make it a solution to the second normalize by dividing by $M+1$.

By uniqueness, $\pi_j=\frac{1}{M+1}$.

$\endgroup$
  • $\begingroup$ This does not answer OP's question. OP doesn't assume aperiodicity. The proof linked by OP does answer the question, though. The reason why the vector of ones works is that by definition, $\nu$ is an invariant measure if $\nu P=\nu$. Since the columns of $P$ all sum to one, $[1,\cdots,1]P=[1,\cdots,1]$. So the vector of ones is an invariant measure. $\endgroup$ – Ceph Apr 8 '17 at 13:41

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.