Maximal entropy random walk: Difference between revisions

Revision as of 14:03, 31 August 2017

Revision as of 05:45, 1 September 2017

Line 29:

=== Sketch of derivation ===

Assume for simplicity that the considered graph is indirected, connected, and aperiodic, what allows to conclude from the [[Perron-Frobenius theorem]] that the dominant eigenvector is unique. Hence <math>A^l</math> can be asymptotically <math>(l\to\infty)</math> approximated withby <math>\lambda^l \psi \psi^T</math> (or <math>\lambda^l |\psi\rangle \langle \psi|</math> in [[bra-ket notation]]).

MERW is uniform distribution among paths. The number of length <math>2l</math> paths with vertex <math>i</math> in the center is <math>\sum_{jk} (A^l)_{ji} (A^l)_{ik} </math> what asymptotically grows like <math>\lambda^{2l} \psi_i^2</math>, getting the <math>\rho_i\propto \psi_i^2</math> behavior.

Analogously calculating probability distribution for two succeeding vertices <math>ij</math>, we canget <math>\textrm{Pr}(ij)\propto \psi_i A_{ij} \psi_j</math>. Dividing by <math>\textrm{Pr}(i)=\rho_i</math> and normalizing to <math>\sum_j S_{ij}=1</math>, we get the above formula for stochastic propagator <math>S_{ij}</math>.

== Examples ==