Dynamics of Maximal Entropy Random Walk and Generic Random Walk on Cayley Trees

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration compares the relaxation of probability distributions to the stationary state for a generic random walk (GRW) and a maximal entropy random walk (MERW) on a Cayley tree. For GRW a particle chooses one of the neighboring sites with equal probability, while for MERW the particle moves in such a way that all trajectories of a given length between two given points are equiprobable.


The area of nodes in the plot as well as their color corresponds to the probability of finding a particle performing a random walk in the given node (the brighter the color, the higher the probability). The logarithmic plot on the right shows how much the probability measured at the red-circled point differs from the probability reached after infinite time (so-called stationary state). You can change the choice of the two initial points (the dash-circled vertices) together with their probabilities.


Contributed by: Jeremi K. Ochab and Z. Burda (January 2012)
Open content licensed under CC BY-NC-SA



Random walks have many applications in statistical physics, economics, biophysics, and many other disciplines. Here, two strikingly different types of random walk processes on graphs are compared: generic random walk (GRW) and maximal entropy random walk (MERW). A particle performing GRW jumps in a single step to one of the neighboring nodes of the graph with equal probability. You can show that as long as the graph is regular, different random walk trajectories that start and end at the same nodes and have the same length are equiprobable. You can, therefore, equivalently define GRW as requiring that all trajectories with the same length and endpoints are equiprobable.

The situation changes when the graph is not regular (for example, leaves of a tree graph have fewer neighbors), since GRW trajectories are not equiprobable any longer. In this case, the second definition does not generate GRW, but leads to another type of random walk. This new random walk maximizes Shannon entropy of trajectories and can thus be called maximal entropy random walk. The difference between GRW and MERW is clearly seen when you consider the stationary probability of finding the particle at a given node of a graph after a very long time. In GRW the particle diffuses over the whole graph, while in MERW the particles gather around the root of the tree. This is very similar to the localization phenomenon known from quantum physics. Once the particle is trapped in this region it will be extremely unlikely to leave it, because of the "entropy barrier".

This Demonstration shows the difference in the speed of probability distribution relaxing to the stationary state for GRW and MERW on Cayley trees (also known as Bethe lattices) with varying root degree (the number of neighbors of the central node), number of generations of the tree (the length of the branches counted from the center), and branching number (the number of nodes descending from a given node to the next generation). The Demonstration lets you change the initial conditions and the measurement point, so that you can observe how symmetries can induce different speeds of relaxation. In general, however, the relaxation process is much faster for MERW than for GRW. This shows as steeper slopes in the plot on the right-hand side. Points in this plot represent the logarithm of the difference between the probability measured at the red-circled point at a given time step and the probability that is reached there after infinite time. As this difference dwindles with time exponentially fast, the logarithm produces straight lines.

Snapshot 1: one can choose two starting points (checking the option "numbering" marks them with dashed circles) with a different probability of a random walker departing from each of them (real values are allowed) and one vertex that measures the relaxation (marked with red circle)

Snapshot 2: two types of relaxation can be observed; the lines correspond to theoretical predictions

Snapshot 3: as it is the symmetry that induces the faster relaxation, it can always be observed for GRW and MERW (e.g. the root taken as the initial or measuring vertex)

Snapshot 4: the faster relaxation can also be observed if the initial conditions are symmetric


[1] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, "Localization of Maximal Entropy Random Walk," Physical Review Letters, 102(16), 2009. arxiv.org/abs/0810.4113.

[2] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw, "The Various Facets of Random Walk Entropy," Acta Physica Polonica B, 41(5), 2010 arxiv.org/abs/1004.3667.

[3] J. K. Ochab and Z. Burda. "Exact Solution for Statics and Dynamics of Maximal Entropy Random Walk on Cayley Trees." (Jan 6, 2012) arxiv.org/abs/1201.1420.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.