9
$\begingroup$

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N \times N$ stochastic matrix $\mathbf{M}$ (in which every column sums to $1$) whose second-largest (in absolute value) eigenvalue is $\lambda$. The constraint is only on $\vert \lambda \vert$ and it does not matter if $\lambda$ is complex.

The first (largest-magnitude) eigenvalue is always $1$. The rest of the eigenvalues are arbitrary.

I need the procedure (if one exists) to always converge with a correct answer with probability $1$ (if it is iterative).

I need this in Markov chain simulations and I want to control the convergence rate from the initial distributions to the equilibrium one.

EDIT: It is also important to know that randomly generating a stochastic matrix in Matlab (shown in the figure below) yields a relatively small second-largest eigenvalue, indicating that the probability of having large second-largest eigenvalue is small and it needs to be crafted. You can also see the eigenvalue $1$ that always exists in isolation on the far right. The figure below is the spectra of $10000$ randomly generated $16 \times 16$ stochastic matrices. enter image description here

As pointed out in the comments, I found a paper that constructs a doubly stochastic matrix explicitly from a given positive spectrum. However, the constructed matrices are, in fact, very concentrated around the diagonal (these can be called lazy Markov chains since they tend to stay where they are). This result explains why it is extremely unlikely that a randomly generated stochastic matrix would have eigenvalues closer to $1$ than shown in the above figure. This means there is only local transitions between Markov chain states with very weak global transitions. Is that indeed implied by asking for large eigenvalues of the transition matrix?

Here is a surface plot of a $100 \times 100$ stochastic matrix constructed from a randomly generated positive spectrum as explained in this paper.

enter image description here

I also found a result here saying that lazy, reversible Markov chains have positive spectra, which is in line with the above result.

$\endgroup$
3
  • $\begingroup$ For fixed $N$, the eigenvalues of all stochastic matrices do not fill up the unit ball so this will not be possible for every $\lambda$. For the $3\times 3$ case, see here: math.stackexchange.com/questions/141212/… $\endgroup$
    – user940
    Mar 11, 2014 at 21:55
  • $\begingroup$ Thanks Mr. Byron for the very informative post. In your question, the point $1$ is still not an isolated eigenvalue, so real eigenvalues can be used. I indeed found a paper (sciencedirect.com/science/article/pii/0024379584900181#) that explicitly constructs a doubly stochastic matrix having a prescribed positive spectrum. So at least the real axis between $0$ and $1$ is covered. $\endgroup$
    – Ahmed Nassar
    Mar 11, 2014 at 23:24
  • 1
    $\begingroup$ What if you take your "lazy" doubly stochastic matrix $M$ (with arbitrary positive spectrum) and look at $S^{-1} M S$ where $S$ is a random stochastic matrix? The result should still be stochastic matrix and it should have the same spectrum as $M$ but "look more random". $\endgroup$
    – Charles Bouillaguet
    Apr 23, 2020 at 8:26

0

Reset to default

You must log in to answer this question.