MAXIMAL ENTROPY RANDOM WALK: SOLVABLE CASES OF DYNAMICS

We focus on the study of dynamics of two kinds of random walk: generic random walk (GRW) and maximal entropy random walk (MERW) on two model networks: Cayley trees and ladder graphs. The stationary probability distribution for MERW is given by the squared components of the eigen-vector associated with the largest eigenvalue lambda(0) of the adjacency matrix of a graph, while the dynamics of the probability distribution approaching to the stationary state depends on the second largest eigenvalue lambda(1). Firstly, we give analytic solutions for Cayley trees with arbitrary branching number, root degree, and number of generations. We determine three regimes of a tree structure corresponding to strongly, critically, and weakly branched roots. Each of them results in different statics and dynamics of MERW. We show how the relaxation times, generically shorter for MERW than for GRW, scale with the graph size. Secondly, we give numerical results for ladder graphs with symmetric defects. MERW shows a clear exponential growth of the relaxation time with the size of defective regions, which indicates trapping of a particle within highly entropic intact region and its escaping that resembles quantum tunneling through a potential barrier. GRW shows standard diffusive dependence irrespective of the defects.