Duda Jarek Posted December 1, 2008 Share Posted December 1, 2008 (edited) While thinking about random walk on a graph, standard approach is that every possible edge is equally probable - kind of maximizing local entropy. There is new approach (MERW) - which maximizes global entropy (of paths) - for each two vertexes, each path of given length is equally probable. For a regular graph it gives the same, but usually they are different - it MERW we get some localizations, not known in standard random walk. It was derived in http://www.arxiv.org/abs/0710.3861 in the context of optimal encoding. In http://www.arxiv.org/abs/0810.4113 are analyzed it's localization properties. It can also suggest the nature of quantum physics ( http://www.advancedphysics.org/forum/showthread.php?p=47998 ) . In the second paper is also introduced some nice inequality for dominant eigenvalue ([math]\lambda[/math]) of a symmetric real matrix [math]M[/math] with nonegative terms, I'll write it in full generality: [math]\forall_{n>0}\qquad\lg(\lambda)\geq \frac{1}{n}\frac{\sum_i k_{ni} \lg(k_{ni})}{\sum_i k_{ni}}[/math] where [math]k_{ni}:=\sum_j (M^n)_{ij}[/math] In 0/1 matrix and n=1 case it's just the comparison between the entropies of both random walks. To generalize it to other symmetric matrices with nonnegative terms, we have observe in the case with potential ([math] M_{ij}=e^{-V_{ij}}[/math]), we have optimized not average entropy, but so called (average) free energy - the inequality is the result of that [math]\max_p\ \left(-\sum_i p_i \ln(p_i)-\sum_i E_i p_i\ \right) = \ln\left(\sum_i e^{-E_i}\right)\quad \left(=\ln(\lambda)=-F\right)[/math] and the maximum is fulfilled for [math] p_i \sim e^{-E_i}[/math]. Finally to get the equation above, we have to get [math] M^n [/math] instead of [math]M[/math]. This inequality is much stronger than this type of inequalities I know and quickly gives quite good below approximation of the dominant eigenvalue. Have You met with this/similar inequality? How to prove it straightforward (not using sequence interpretation) ? Edited December 1, 2008 by Duda Jarek Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now