On 28 Nov 2003 17:52:33 -0800, Robert Dodier <[EMAIL PROTECTED]> wrote: > "Kevin" <[EMAIL PROTECTED]> wrote: > >> I am kind of thinking how to calculate the invariant distribution >> for the large transition matrix of a Markov Chain.
>> Actually, each column in the transition matrix is just like a >> Binomial distribution with probability P(i), where i is the >> index of the column. Can you give me some suggestion on how >> to calculate the invariant distribution efficiently? > > As you know the invariant distribution for a discrete Markov > chain is the eigenvector associated with eigenvalue 1. > There is a package for large-scale eigenvalue problems called > ARPACK that you might use. With ARPACK you define a function > to compute the scalar (dot) product of two columns and this > function is called instead of computing the scalar product in > the usual way. For a matrix with special structure (e.g., > most column elements are zero) it can be much faster. > I don't remember for sure, but I think ARPACK can avoid > storing the matrix (since it has the scalar product function). > > Also, iirc ARPACK can find the eigenvectors associated with > the largest so-many eigenvalues. > > You can find ARPACK on the web. It is in Fortran. > > You didn't say how big a problem you have, but keep in mind > that 1000 by 1000 isn't "large" anymore; such a problem can > be solved by standard techniques, as implemented, for example, by Octave. >> I am more interested in the mean and the variance >> of the states, any simpler ways to calculate them? The mean and variance of the stationary probability vector over resamples of the transtion probabilies? I don't think that has any easily calculable formula in general. Because it's an eigenvector, all the components in the stationary density have dependence on one another, even if the matrix is composed out of independently drawn random numbers. There may be sometething in "random matrix theory" but I don't know much about it, and it may not be easy. The fluctuations of any component individually do not tell you that much. There are two kinds of "variance" here. The first would be A) choose a random Markov matrix with components drawn from distribution. find its unit-eigenvector. Look at that distribution. the second B) imagine the markov chain with a fixed matrix were actually simulated in time, what is the variance of any local "count" of occurences of some state around the stationary density? This could be quite high if you have not well mixing "regions". The next largest eigenvalue may tell you some information about this. > > Could be, I don't know. Maybe someone else has an idea here. > > For what it's worth, > Robert Dodier > -- > Life isn't all beer and skittles, but beer and skittles, > or something better of the same sort, must form a good part > of every Englishman's education. -- Thomas Hughes (1822-96) . . ================================================================= Instructions for joining and leaving this list, remarks about the problem of INAPPROPRIATE MESSAGES, and archives are available at: . http://jse.stat.ncsu.edu/ . =================================================================
