Recurrence of random walks with long-range steps generated by fractional Laplacian matrices on regular networks and simple cubic lattices
Résumé
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 Green's functions).
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 > \alpha$ (recurrent for $d\leq\alpha$) 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 $1\leq\alpha < 2$ for dimensions $d\geq 2$. Finally, for $\alpha=2$
Polya's classical recurrence theorem is recovered, namely
the walk is transient only for lattice dimensions $d\geq 3$.
The generalization of Polya's recurrence theorem remains valid for the class of random walks with L\'evy 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 Green's 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 L\'evy 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 emergence of L\'evy flights on large (infinite) lattices.
Mots clés
Kemeny constant
Polya Walk
Mean first passage times (MFPT)
Fractional Laplacian operator
Fractional Random Walk
Lattice
Recurrence Theorem
First passage probabilities
Lévy flights
Probability generating functions
Search efficiency
Regular undirected networks
Laplacian matrix
Riesz potentials
Heavy tailed distribution
Fractional Laplacian matrix
Lattice Green's functions
Origine : Fichiers produits par l'(les) auteur(s)