Recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices

Abstract

We analyze a Markovian random walk strategy on undirected regular networks involving power matrix functions of the type Lα2 where L indicates a "simple" Laplacian matrix. We refer to such walks as "fractional random walks" with admissible interval 0 < α ≤ 2. We deduce probability-generating functions (network Green's functions) for the fractional random walk. From these analytical results we establish a generalization of Polya's recurrence theorem for fractional random walks on d-dimensional infinite lattices: The fractional random walk is transient for dimensions d > α (recurrent for d ≤ α) of the lattice. As a consequence, for 0 < α < 1 the fractional random walk is transient for all lattice dimensions d = 1, 2,.. and in the range 1 ≤ α< 2 for dimensions d ≥ 2. Finally, for α = 2, Polya's classical recurrence theorem is recovered, namely the walk is transient only for lattice dimensions d ≥ 3. The generalization of Polya's recurrence theorem remains valid for the class of random walks with Lévy flight asymptotics for long-range steps. We also analyze the mean first passage probabilities, mean residence times, mean first passage times and global mean first passage times (Kemeny constant) for the fractional random walk. For an infinite 1D lattice (infinite ring) we obtain for the transient regime 0 < α < 1 closed form expressions for the fractional lattice Green's function matrix containing the escape and ever passage probabilities. The ever passage probabilities (fractional lattice Green's functions) in the transient regime fulfil Riesz potential power law decay asymptotic behavior for nodes far from the departure node. The nonlocality of the fractional random walk is generated by the non-diagonality of the fractional Laplacian matrix with Lévy-type heavy tailed inverse power law decay for the probability of long-range moves. This non-local and asymptotic behavior of the fractional random walk introduces small-world properties with the emergence of Lévy flights on large (infinite) lattices. © 2017 IOP Publishing Ltd.