Content deleted Content added
Line 22:
MERW chooses the stochastic matrix which maximizes <math>H(S)</math>, or equivalently assumes uniform probability distribution among all paths in a given graph. Its formula is obtained by first calculating the dominant [[eigenvalue]] and corresponding [[eigenvector]] of the adjacency matrix: <math>\max_{|\lambda|}\ \psi A = \lambda \psi</math>. Then stochastic matrix and stationary probability distribution are given by:
<math>S_{ij} = \frac{A_{ij}}{\lambda} \frac{\psi_j}{\psi_i} \qquad\qquad \rho_i \propto \psi_i^2</math>
for which every length <math>l</math> possible path from <math>i</math> to <math>j</math> has probability <math>\frac{1}{\lambda^l} \frac{\psi_j}{\psi_i}</math>. Its entropy rate is <math> \log(\lambda) </math>.
Line 33:
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 get <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
== Examples ==
| |||