Maximal entropy random walk and some eigenvalue inequality

[Duda Jarek]

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