Generic Random Walk and Maximal Entropy Random Walk
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
The plots compare the stationary probability of finding a particle performing a random walk on a 2D square lattice with randomly distributed defects for Generic Random Walk (GRW) and Maximal Entropy Random Walk (MERW). The darker a region, the lower the stationary probability of finding a particle there. For GRW the particle chooses one of the neighboring sites with equal probability, while for MERW the particle moves in such a way that all trajectories of given length between two given points are equiprobable. By changing the density of defects, that is, of randomly erased links (marked in red in the plot), you can observe that for GRW the probability spans the whole lattice while for MERW it is localized in the largest region free of defects.
Contributed by: Bartlomiej Waclaw (March 2011)
After work by: Z. Burda, J. Duda, J. M. Luck, and B. Waclaw
Open content licensed under CC BY-NC-SA
Random walk has many applications in statistical physics, economics, biophysics, and many other disciplines. We compare here two types of random walk processes on graphs: GRW (Generic Random Walk) and MERW (Maximal Entropy Random Walk). The particle performing GRW jumps in a single step to one of the neighboring nodes of the graph with equal probability. One can show that as long as the graph (lattice) is regular, different random walk trajectories that start and end at the same nodes and have the same length are equiprobable. One can, therefore, equivalently define GRW by requiring that all trajectories with the same length and endpoints are equiprobable. The situation changes when the graph is not regular, for example, if it is a square lattice with some edges removed, since GRW trajectories are not equiprobable any longer. In this case the second definition does not give GRW but leads to another type of random walk. This new random walk maximizes Shannon entropy of trajectories and can be thus called maximal entropy random walk (MERW). The difference between GRW and MERW is clearly seen when one considers the stationary probability of finding the particle at a given lattice site after a very long time. In GRW the particle diffuses over the whole lattice while in MERW the diffusion area is constrained to the largest lattice region which is free of defects. It is very similar to the localization phenomenon known from quantum physics. Once the particle is trapped in this region, it will have no chance to leave it again because of the "entropy barrier". The localization occurs for any density of defects if the lattice is sufficiently large. If the defects are distributed at random and uniformly, the localization volume grows with the logarithm of the system size.
This Demonstration shows the difference between the stationary distribution for GRW and MERW on a 2D lattice with periodic boundary conditions and with some fraction of links removed. For technical reasons, to ensure that the lattice is connected, only nonadjacent links are removed. For a connected lattice the GRW stationary probability spreads over the whole lattice, and if the defects are uniformly distributed, the GRW stationary probability is also uniform if viewed on a large scale. By fixing the density of defects and changing the lattice size, you can check that for MERW the particle tends to localize in some nearly circular-shaped region free of defects when the lattice is sufficiently large. By choosing different initial "seeds" for the random number generator you can create various "snapshots" of the defected lattice and see that the localization indeed takes place for almost every configuration.
Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, "Localization of Maximal Entropy Random Walk," http://arxiv.org/abs/0810.4113.
"Generic Random Walk and Maximal Entropy Random Walk"
Wolfram Demonstrations Project
Published: March 7 2011