0
$\begingroup$

Let $X$ be a finite set and $M$ a Markov chain over it, one can find its limit state vector(s) $v$ under certain conditions. I'm curious about the converse: Given a vector $v$, how to find all Markov chains $M$ such that $v$ is one and the only one limit state of $M$?

$\endgroup$
2
$\begingroup$

The answer below is incorrect (see comments)


Here is something that works if $v$ has no zero entries. Let $D$ denote the diagonal matrix $$ D = \operatorname{diag}(v) = \pmatrix{v_1 \\ & \ddots \\ && v_n}. $$ If $P$ is a row-stochastic matrix, then $P$ is the transition matrix with unique stationary distribution $v$ if and only if the eigenvalue $\lambda = 1$ of $P^T$ has geometric multiplicity (GM) $1$ and $v$ is an associated eigenvector.

This is the equivalent to the condition that $DP^TD^{-1}$ and $[DP^TD^{-1}]^T = D^{-1}PD$ are doubly-stochastic with eigenvalue $\lambda = 1$ having GM $1$.

Putting all this together: $P$ is the transition matrix of a Markov chain with the desired property if and only if there exists a doubly stochastic matrix $Q$ with $\operatorname{rank}(Q - I) = n-1$ for which $P = DQD^{-1}$.

If you are simply interested in generating a random such $P$, note that a randomly generated doubly stochastic matrix $Q$ will work "with probability $1$".

$\endgroup$
8
  • $\begingroup$ Nice trick on turning $v$ into $D$! Thanks! .. could be a digression, but does it also work "with probability 1" if I require $P$ to be a reversible markov chain? $\endgroup$
    – Student
    Oct 4 '20 at 11:28
  • $\begingroup$ I haven’t said anything about enforcing the requirements for reversibility. In fact, I suspect that there is exactly one reversible markov chain with the given stationary distribution $\endgroup$ Oct 4 '20 at 11:32
  • $\begingroup$ Actually that statement about uniqueness is definitely wrong. In any case, the reversibility condition changes things significantly $\endgroup$ Oct 4 '20 at 11:34
  • $\begingroup$ I'm looking at a specific paper, in which the final vector is "deformed". The authors went on demonstrating a way to find a (deformed) reversible Markov chain, using the "auxiliary variable method".. I hope that's unique in any sense.. perhaps this deserves to be another thread. $\endgroup$
    – Student
    Oct 4 '20 at 14:32
  • $\begingroup$ I think it deserves to be another thread $\endgroup$ Oct 4 '20 at 15:24

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.