sci.math
[Top] [All Lists]

Mixing time of markov chain

Subject: Mixing time of markov chain
From:
Date: 31 Oct 2006 10:45:34 -0800
Newsgroups: sci.math
A random walk on a graph can be treated as a Markov Chain. Several
references say that mixing time of Markov-chain on a graph of n
vertices is of the order of

log(n)/(spectral gap)

where spectral gap is the difference between top 2 eigenvalues of the
transition probability matrix of the Markov chain.  I am yet to find a
formal proof of this statement ! Can anybody tell  about a reference in
web that shows the proof?


<Prev in Thread] Current Thread [Next in Thread>
  • Mixing time of markov chain, souptik <=
Privacy Policy