Maximal entropy random walk: Difference between revisions

Revision as of 19:47, 27 August 2019

Revision as of 08:17, 9 September 2019

Line 10:

[[Image:General picture for Maximal Entropy Random Walk.png|thumb|upright=2.65|right|'''Left:''' basic concept of the generic random walk (GRW) and maximal entropy random walk (MERW)<br>'''Right:''' example of their evolution on the same inhomogeneous 2D lattice with cyclic boundary conditions – probability density after 10, 100 and 1000 steps while starting from the same vertex. The small boxes represent defects: all vertices but the marked ones have additional [[self-loop]] (edge to itself). For regular lattices (no defects), GRW and MERW are identical. While defects do not strongly affect the local beha&shy;vior, they lead to a completely different global stationary probability here. While GRW (and based on it standard [[diffusion]]) leads to nearly uniform stationary density, MERW has strong localization property, imprisoning the walkers in entropic wells in analogy to electrons in defected lattice of [[semi-conductor]].]]

Imagine there isConsider a [[Graph (discrete mathematics)|graph]] with <math>n</math> vertices, givendefined by an [[adjacency matrix]] <math>A \in \left\{0, 1\right\}^{n \times n}</math>: <math>A_{ij}=1</math> if there is an edge from vertex <math>i</math> to <math>j</math>, 0 otherwise. For simplicity assume it is an [[Graph (discrete mathematics)#Undirected graph|undirected graph]], whatwhich corresponds to a symmetric <math>A</math>; however, MERW can be also be generalized for directed and [[Graph (discrete mathematics)#Weighted graph|weighted graphs]] (gettingfor example [[Boltzmann distribution]] among paths instead of uniform).

We would like to choose a random walk as a [[Markov process]] on this graph: for every vertex <math>i</math> and its outgoing edge to <math>j</math>, choose probability <math>S_{ij}</math> of the walker randomly using this edge after visiting <math>i</math>. Formally, find a [[stochastic matrix]] <math>S</math> (containing the transition probabilities of a Markov chain) such that

* <math>0\leq S_{ij} \leq A_{ij}</math> for all <math>i, j</math> and

* <math>\sum_{j=1}^n S_{ij}=1</math> for all <math>i</math>.

Assuming this graph is connected and not [[Periodic graph (graph theory)|periodic]], [[ergodic theory]] says that evolution of this [[stochastic process]] leads to some stationary probability distribution <math>\rho</math> such that <math>\rho S = \rho</math>.

Using [[Shannon entropy]] for every vertex and averaging over probability of visiting this vertex (to be able to use its entropy), we get the following formula for average entropy production ([[entropy rate]]) of athe stochastic process:

:<math>H(S)=\sum_{i=1}^n \rho_i \sum_{j=1}^n S_{ij} \log(1/S_{ij})</math>

This definition turns out to be equivalent withto the asymptotic average entropy (per length) of the probability distribution in the space of paths for this stochastic process.

In the standard random walk, referred to here as generic random walk (GRW), we naturally choose that each outgoing edge is equally probable:

:<math>S_{ij} = \frac{A_{ij}}{\sum\limits_{k=1}^n A_{ik}}</math>.

For a symmetric <math>A</math> it leads to a stationary probability distribution <math>\rho</math> with

Line 36:

:<math>\rho_i = \frac{\psi_i^2}{\psi^2}</math>.

In contrast to GRW, the MERW transition probabilities generally depend on the structure of the entire graph (are nonlocal). Hence, they rather should not be imagined as directly applied by the walker – if randomly random-looking decisions are performedmade based on the local situation, like a person would domake, the GRW approach is rather more appropriate. MERW is based on the [[principle of maximum entropy]], making it the safest assumption when we don't have any additional knowledge about the system. For example, it would be appropriate for modelling our knowledge about an object performing some complex dynamics – not necessarily random, like a particle.

=== Sketch of derivation ===