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

Improve this question
$\endgroup$
4
  • $\begingroup$ Perron-Frobenius. $\endgroup$
    – cardinal
    Commented Sep 21, 2012 at 10:30
  • 2
    $\begingroup$ @cardinal Why not make it an answer with a little elaboration? $\endgroup$
    – Michael R. Chernick
    Commented Sep 21, 2012 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
    Commented Sep 21, 2012 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
    Commented Sep 21, 2012 at 23:21

1 Answer 1

Reset to default
5
$\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}$.

Improve this answer
$\endgroup$
1
  • 1
    $\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
    Commented Apr 8, 2017 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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