Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Maximal entropy random walk and some eigenvalue inequality
0 views
Skip to first unread message
Jarek Duda
Dec 1, 2008, 6:59:35 AM12/1/08
to
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.
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 for example gives very strong and looking to be new inequality for
the dominant eigenvalue (lambda) of a symmetric real matrix with
nonnegative terms:
ln(lambda) >= (\sum_i k_i ln(k_i))/(sum_i k_i)
where k_i = sum_j M_ij
It allows to quickly approximate the dominant eigenvalue from below.
Please join the discussion
http://www.scienceforums.net/forum/showthread.php?t=36717
for nicer looking equations and more details.
0 new messages