Generic Random Walk and Maximal Entropy Random Walk

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
  • After work by: Z. Burda, J. Duda, J. M. Luck, and B. Waclaw



  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2018 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+