10217

Stationary States of Maximal Entropy Random Walk and Generic Random Walk on Cayley Trees

This Demonstration compares the stationary probabilities of a generic random walk (GRW) and a maximal entropy random walk (MERW) on a Cayley tree. 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 a given length between two given points are equiprobable.
The area of nodes in the plot as well as their color is proportional to the probability of finding a particle performing a random walk in the given node (the brighter the color, the higher the probability). The plot on the right shows the probabilities as a function of the distance from the center, either as a probability for a given node or as a probability summed over a whole generation of nodes (all nodes equidistant from the center). The limiting probability distributions are theoretical curves corresponding to a tree with an infinite number of generations.

DETAILS

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
References
[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.

PERMANENT CITATION

 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 » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.