Conductance and Eigenvalue

Details Conductance and Eigenvalue Conductance and Eigenvalue

2010-09-09

arxiv.org/abs/1009.1756v1

Computer Science

Discrete Mathematics

Scientific paper

We show the following. \begin{theorem} Let $M$ be an finite-state ergodic time-reversible Markov chain with transition matrix $P$ and conductance $\phi$. Let $\lambda \in (0,1)$ be an eigenvalue of $P$. Then, $$\phi^2 + \lambda^2 \leq 1$$ \end{theorem} This strengthens the well-known~\cite{HLW,Dod84, AM85, Alo86, JS89} inequality $\lambda \leq 1- \phi^2/2$. We obtain our result by a slight variation in the proof method in \cite{JS89, HLW}; the same method was used earlier in \cite{RS06} to obtain the same inequality for random walks on regular undirected graphs.

Affiliated with

Also associated with

No associations

Rating

Conductance and Eigenvalue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Conductance and Eigenvalue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conductance and Eigenvalue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-559014