| 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> |
|---|---|---|
| ||
| Previous by Date: | Re: Multigraph edges, Marc Olschok |
|---|---|
| Next by Date: | Re: An uncountable countable set, stephen |
| Previous by Thread: | Goldbach minus, vernonner3voltazim |
| Next by Thread: | Re: Divisibility Proof - Help Needed, Bill Dubuque |
| Indexes: | [Date] [Thread] [Top] [All Lists] |