Exact solution for statics and dynamics of maximal-entropy random walks on Cayley trees

We provide analytical solutions for two types of random walk: generic random walk (GRW) and maximal-entropy random walk (MERW) on a Cayley tree with arbitrary branching number, root degree, and number of generations. For MERW, we obtain the stationary state given by the squared elements of the eigenvector associated with the largest eigenvalue ${\lambda }_0$ of the adjacency matrix. We discuss the dynamics, depending on the second largest eigenvalue ${\lambda }_1$, of the probability distribution approaching to the stationary state. We find different scaling of the relaxation time with the system size, which is generically shorter for MERW than for GRW. We also signal that depending on the initial conditions, there are relaxations associated with lower eigenvalues which are induced by symmetries of the tree. In general, we find that there are three regimes of a tree structure resulting in different statics and dynamics of MERW; these correspond to strongly, critically, and weakly branched roots.

Figure 1

Cayley tree with root degree $r=5$, branching number $k=2$, and $G=3$ generations.

Figure 2

Finite-size effect: the broken lines correspond to the distribution ${\Pi }_g$ for $G=5,...,45$ in steps of 10, for a tree with $k=r=3$. (a) The distributions for MERW. For $r<k$, the corresponding curves would be skewed and would approach the limiting distribution from the right, while for $r>k$, they would approach from the left. (b) The distributions for GRW. The larger the number of generations, the more peaked the distribution.

Figure 3

(a) Plots for ${\Pi }_g$, which is a total probability for a generation. Curves for large $G$: a sine square for $r<2k$, cosine square for $r=2k$, and hyperbolic sine for $r>2k$ ($k=3$ and $r=3,6,9$). (b) Probability per one node ${\pi }_g$ for $r=3,6,9$, and $G=20$.

Figure 4

Cayley tree with $k=r=2$ and $G=8$: the mild slope (circles) corresponds to the generic relaxation and the steep slope (squares) corresponds to a symmetry-induced one. The data points were generated in a Monte Carlo simulation with $5\times {10}^4$ random walkers, all starting either from a single node in the third generation, which leads to the typical behavior (generic relaxation), or from the root (the most symmetric initial condition), which always leads to a faster relaxation. The distance between the stationary state ${\pi }_i$ and the probability ${\pi }_i\left(t\right)$, measured at a single node $i$ belonging to the second generation, is shown on a logarithmic scale. The lines represent theoretical slopes corresponding to ${\tau }_1={\left[\ln ({\lambda }_0/{\lambda }_1)\right]}^{-1}\approx 83$ and ${\tau }_2={\left[\ln ({\lambda }_0/{\lambda }_{G,2})\right]}^{-1}\approx 6$.

Figure 5

The intersection of the black curve with the other ones marks the solution of Eq. (20). The uppermost brown dotted curve corresponding to a strongly branched root shows no real solutions. The blue dot-dashed sine is an example of the rare case of a strongly branched root with a real solution. The green dashed line is the critically branched root and the red continuous lines correspond to weakly branched roots.