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 (MERW). 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 between the stationary probability distribution for GRW and MERW on Cayley trees (also known as Bethe lattice) 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 plot of the probability distribution can also switch between showing the probabilities for just one member node of a generation (zeroth generation corresponds to the root) and probabilities summed over all members of a generation. The probability is rescaled so as to approach the limiting continuous probability distribution function.

Snapshot 1: GRW has a flat stationary probability (per node) distribution but for the root and the leaves of Cayley tree

Snapshot 2: a stationary probability (per generation) distribution for MERW becomes approximately a sine square for the root degree equal to the branching number

Snapshot 3: a stationary probability (per generation) distribution for MERW is approximately a cosine square for the root degree equal to twice the branching number

Snapshot 4: a stationary probability (per generation) distribution for MERW is approximately an exponent for the root degree greater than twice the branching number

[1] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw. "Localization of Maximal Entropy Random Walk."

*arXiv*. (Nov 3, 2008).

arxiv.org/abs/0810.4113.

[2] Z. Burda, J. Duda, J. M. Luck, and B. Waclaw. "The Various Facets of Random Walk Entropy."

*arXiv*. (Apr 21, 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."

*arXiv*. (Jan 6, 2012).

arxiv.org/abs/1201.1420.