R help - Oct 2009 - Generating a stochastic matrix with a specified second dominant eigenvalue

Hi,

 

Given a positive integer N, and a real number \lambda such that 0 < \lambda
< 1,  I would like to generate an N by N stochastic matrix (a matrix with
all the rows summing to 1), such that it has the second largest eigenvalue
equal to \lambda (Note: the dominant eigenvalue of a stochastic matrix is
1).  

 

I don't care what the other eigenvalues are.  The second eigenvalue is
important in that it governs the rate at which the random process given by
the stochastic matrix converges to its stationary distribution.

 

Does anyone know of an algorithm to do this?

 

Thanks for any help,

Ravi.

----------------------------------------------------------------------------
-------

Ravi Varadhan, Ph.D.

Assistant Professor, The Center on Aging and Health

Division of Geriatric Medicine and Gerontology 

Johns Hopkins University

Ph: (410) 502-2619

Fax: (410) 614-9625

Email: rvaradhan@jhmi.edu

Webpage:
<http://www.jhsph.edu/agingandhealth/People/Faculty_personal_pages/Varadhan.
html>
http://www.jhsph.edu/agingandhealth/People/Faculty_personal_pages/Varadhan.h
tml

 

----------------------------------------------------------------------------
--------


	[[alternative HTML version deleted]]

I just tried the following shot in the dark:

generate an N by N stochastic matrix, M.  I used

 M = matrix(runif(9),nrow=3)
 M = M/apply(M,1,sum)
 e=eigen(M)
 e$values[2]= .7  (pick your favorite lambda, you may need to fiddle 
                   with the others to guarantee this is second largest.)
 Q = e$vectors
 Qi = solve(Q)
 B = Q %*% diag(e$values) %*% Qi
> eigen(B)$values
[1]  1.00000000  0.70000000 -0.08518772
> apply(B,1,sum)
[1] 1 1 1

I haven't proven that this must work, but it seems to.  Since you can
verify that it worked afterwards, perhaps the proof is in the pudding.

albyn



On Thu, Oct 15, 2009 at 06:24:20PM -0400, Ravi Varadhan
wrote:
> Hi,
> 
>  
> 
> Given a positive integer N, and a real number \lambda such that 0 <
\lambda
> < 1,  I would like to generate an N by N stochastic matrix (a matrix
with
> all the rows summing to 1), such that it has the second largest eigenvalue
> equal to \lambda (Note: the dominant eigenvalue of a stochastic matrix is
> 1).  
> 
>  
> 
> I don't care what the other eigenvalues are.  The second eigenvalue is
> important in that it governs the rate at which the random process given by
> the stochastic matrix converges to its stationary distribution.
> 
>  
> 
> Does anyone know of an algorithm to do this?
> 
>  
> 
> Thanks for any help,
> 
> Ravi.
> 
>
----------------------------------------------------------------------------
> -------
> 
> Ravi Varadhan, Ph.D.
> 
> Assistant Professor, The Center on Aging and Health
> 
> Division of Geriatric Medicine and Gerontology 
> 
> Johns Hopkins University
> 
> Ph: (410) 502-2619
> 
> Fax: (410) 614-9625
> 
> Email: rvaradhan at jhmi.edu
> 
> Webpage:
>
<http://www.jhsph.edu/agingandhealth/People/Faculty_personal_pages/Varadhan.
> html>
>
http://www.jhsph.edu/agingandhealth/People/Faculty_personal_pages/Varadhan.h
> tml
> 
>  
> 
>
----------------------------------------------------------------------------
> --------
> 
> 
> 	[[alternative HTML version deleted]]
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>

On Oct 15, 2009, at 6:24 PM, Ravi Varadhan wrote:
> Hi,
>
> Given a positive integer N, and a real number \lambda such that 0 <  
> \lambda
> < 1,  I would like to generate an N by N stochastic matrix (a matrix  
> with
> all the rows summing to 1), such that it has the second largest  
> eigenvalue
> equal to \lambda (Note: the dominant eigenvalue of a stochastic  
> matrix is
> 1).
>
> I don't care what the other eigenvalues are.  The second eigenvalue is
> important in that it governs the rate at which the random process  
> given by
> the stochastic matrix converges to its stationary distribution.
>
> Does anyone know of an algorithm to do this?
I surely don't. My linear algebra is a distant and not entirely  
pleasant memory. I went searching and ended up at Google books reading  
a couple of texts on real analysis and stochastic matrices. Both  
citations reminded me that a matrix induces or implies a polynomial  
form over powers of <some> matrix (? constructed out of the basis  
vectors?) with the eigenvalues representing the coefficients. I  
believe that form can be solved for, but I don't know the process. It  
made me wonder if constructing a matrix out of powers of an  
appropriate stochastic basis would deliver the sought for resultant.  
Such a construction is outside my abilities.

-- 
David Winsemius, MD
Heritage Laboratories
West Hartford, CT

A further idea:

  Consider the triangular square matrices of the form with decreasing  
eigenvalues on the diagonal:

1   0   0   0   0   0
.3 .7   0   0   0   0
.4 .2  .4   0   0   0
.2 .4  .2  .2   0   0
.1 .3  .4  .2  .1   0
.2 .2  .2  .2  .1  .1

This would have the specified eigenvalue composition. Couldn't you  
then apply "Gaussian reduction" row operations not for the purpose of
"reduction" but essentially the inverse? Wouldn't these all be in
the
class of matrices that are "row echelon equivalent"? Don't they
have
identical eigenvalues? Couldn't you fill in the lower triangular  
elements with a random group of elements drawn from runif() calls.   
And then a series of Gaussian row operations that preserved the  
stochastic character?

  e.g. a*Row1 +(1-a)Row6 -> Row1

-- 
David Winsemius, MD
Heritage Laboratories
West Hartford, CT

On Oct 15, 2009, at 6:24 PM, Ravi Varadhan wrote:
> Hi,
>
>
>
> Given a positive integer N, and a real number \lambda such that 0 <  
> \lambda
> < 1,  I would like to generate an N by N stochastic matrix (a matrix  
> with
> all the rows summing to 1), such that it has the second largest  
> eigenvalue
> equal to \lambda (Note: the dominant eigenvalue of a stochastic  
> matrix is
> 1).
>
>
>
> I don't care what the other eigenvalues are.  The second eigenvalue is
> important in that it governs the rate at which the random process  
> given by
> the stochastic matrix converges to its stationary distribution.
>
>
>
> Does anyone know of an algorithm to do this?
>
>
>
> Thanks for any help,
>
> Ravi.
>
>
----------------------------------------------------------------------------
> -------
>
> Ravi Varadhan, Ph.D.
>
> Assistant Professor, The Center on Aging and Health
>
> Division of Geriatric Medicine and Gerontology
>
> Johns Hopkins University
>
> Ph: (410) 502-2619
>
> Fax: (410) 614-9625
>
> Email: rvaradhan at jhmi.edu
>
> Webpage:
>
<http://www.jhsph.edu/agingandhealth/People/Faculty_personal_pages/Varadhan
> .
> html>
>
http://www.jhsph.edu/agingandhealth/People/Faculty_personal_pages/Varadhan.h
> tml
>
>
>
>
----------------------------------------------------------------------------
> --------
>
>
> 	[[alternative HTML version deleted]]
>
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
David Winsemius, MD
Heritage Laboratories
West Hartford, CT

Ravi Varadhan wrote:
> Hi,
> 
> Given a positive integer N, and a real number \lambda such that 0 <
\lambda
> < 1,  I would like to generate an N by N stochastic matrix (a matrix
with
> all the rows summing to 1), such that it has the second largest eigenvalue
> equal to \lambda (Note: the dominant eigenvalue of a stochastic matrix is
> 1).  
> 
> I don't care what the other eigenvalues are.  The second eigenvalue is
> important in that it governs the rate at which the random process given by
> the stochastic matrix converges to its stationary distribution.
An idea...

Form a vector e of desired eigenvalues where the first eigenvalue is
1, the second is \lambda, and the remaining eigenvalues are whatever
is convenient (i*\lambda_i/(N-2) where i=0:(N-3) for example if repeated 
eigenvalues would be inconvenient). Then form A=diag(e) and modify it
to make the matrix stochastic by replacing the element just below
lambda_i with (1-lambda_i) until you get to the lambda_N, where A[1,N]
would be set to (1-lambda_N).

If \lambda=0.8, then we could form

e <- c(1, 0.8, 0.6, 0.4, 0.2)

then I think your desired matrix A is

A <- diag(e)
A[3,2] <- 1-e[2]
A[4,3] <- 1-e[3]
A[5,4] <- 1-e[4]
A[1,5] <- 1-e[5]
eigen(A)

-- 
---------------------------------------------------------------------------
Jeff Newmiller                        The     .....       .....  Go Live...
DCN:<jdnewmil at dcn.davis.ca.us>        Basics: ##.#.       ##.#.  Live
Go...
                                       Live:   OO#.. Dead: OO#..  Playing
Research Engineer (Solar/Batteries            O.O#.       #.O#.  with
/Software/Embedded Controllers)               .OO#.       .OO#.  rocks...1k