We analyze a random walk strategy on undirected regular networks involving power matrix functions of the type $L^{frac{alpha}{2}}$ where $L$ indicates a `simple Laplacian matrix. We refer such walks to as `Fractional Random Walks with admissible interval $0<alpha leq 2$. We deduce for the Fractional Random Walk probability generating functions (network Greens functions). From these analytical results we establish a generalization of Polyas recurrence theorem for Fractional Random Walks on $d$-dimensional infinite lattices: The Fractional Random Walk is transient for dimensions $d > alpha$ (recurrent for $dleqalpha$) of the lattice. As a consequence for $0<alpha< 1$ the Fractional Random Walk is transient for all lattice dimensions $d=1,2,..$ and in the range $1leqalpha < 2$ for dimensions $dgeq 2$. Finally, for $alpha=2$ Polyas classical recurrence theorem is recovered, namely the walk is transient only for lattice dimensions $dgeq 3$. The generalization of Polyas recurrence theorem remains valid for the class of random walks with Levy flight asymptotics for long-range steps. We also analyze for the Fractional Random Walk mean first passage probabilities, mean first passage times, and global mean first passage times (Kemeny constant). For the infinite 1D lattice (infinite ring) we obtain for the transient regime $0<alpha<1$ closed form expressions for the fractional lattice Greens function matrix containing the escape and ever passage probabilities. The ever passage probabilities fulfill Riesz potential power law decay asymptotic behavior for nodes far from the departure node. The non-locality of the Fractional Random Walk is generated by the non-diagonality of the fractional Laplacian matrix with Levy type heavy tailed inverse power law decay for the probability of long-range moves.
Download