Random walks are among the most fundamental stochastic processes that occur ubiquitously in various interdisciplinary contexts such as in biological networks, the foraging of animals, the spread of diseases, in finance, human mobility in cities, friendship networks, among many other “complex systems”. Generally, random walks are microscopic models for diffusion processes and play a crucial role in the development of “random search” strategies. One of the main goals of this field is to find a strategy that a given set of targets distributed among a larger set is most quickly visited by the walker. This and similar questions constitute one of the major motivations and driving forces for the subjects of this book. The analysis of new random walk strategies, especially those which allow faster exploration of a network or a subset of it, is highly desirable for many interdisciplinary applications and interesting from a theoretical point of view. Last but not least, the recent upswing of online networks such as Google and social networks has launched a huge interest in stochastic motions on networks. In many of these problems of real life such as in population dynamics, chaotic motions, the time evolution of stock-market prices and many others, it is impossible and even meaningless to describe time evolutions using deterministic equations. Instead, one is interested in extracting a maximum of “statistical information” from these processes. As a result, many different kinds of random walk models have been proposed and extensively studied.

The “random walk history” started more than a century ago when the notion of “random walk” was coined by K. Pearson in 1905 coming along with the groundbreaking works of A. Einstein who formulated the stochastic motion of particles, and similar ideas were developed by M. von Smoluchovski at about the same time. Then later on P. Lévy together with R. von Mises, A. Kolmogorov, N. Wiener, L. Doob and K. Itô were among the founders of modern probability theory, and many further classical works are connected with the names of L. Bachelier, R. Brown, G. Pólya, Lord Rayleigh, W. Feller, M. Kac, F. Spitzer, A. Khinchin, E.W. Montroll, G.H. Weiss, A.A. Markov, B. Mandelbrot and many others. The systematic study of random walks was probably inspired by the “Gambler’s Ruin” problem, which was analyzed by Bernoulli, Fermat, Huygens, Pascal, among others.

Random walks are today a highly interdisciplinary basic approach to statistical physics. In the meantime, a burst of remarkable literature has been published on the subject. The features of random motions depend sensitively on the topology of the “environments” and “spaces” where they occur. Many of them can be conceived as taking place on well-defined and countable sets of “states”. If these sets of states are finite and countable, then they can be considered as (finite) graphs or synonymously networks. When random transitions within these well-defined sets of states occur, then we can describe these processes as “random walks on graphs”. In more general situations, where random walks are performed either in continuous compact spaces or on disjoint (often fractal sub-) sets where the points are uncountable, it appears to be fruitful to describe such walks in terms of “probability measures” by means of the language of measure theory.

G. Pólya was one of the first to demonstrate the importance to study random walks on simple multidimensional integer lattices. He disclosed in a celebrated paper the crucial role of the dimension of the lattice for the recurrence/transience behavior of a walk. This behavior emerges in the so-called Pólya walks having a most simple generating law, namely, that the walker in one time step can jump with equal probabilities only to connected neighbor nodes. The great achievement of that work was also to have shown that universal behavior can be obtained already by most simple generating laws. We consider in Chapter 7 a generalization of the Pólya walk problem and by assuming a “fractional generating law” we derive a generalized recurrence theorem as a universal feature of the “fractional random walk” and all walks with asymptotic Lévy flight behavior emerging from the fractional dynamics on infinite multidimensional lattices and spaces.

We will see in the course of this book that whatever be the generating law for a Markovian walk on an undirected network, after sufficiently many time steps the probability distributions may converge only to two distinct kinds of limiting distributions, namely either Gaussian distributions when the jump lengths on the network in one time step are limited (e.g. to neighbor nodes or light-tailed distributed to further distant neighbors) with finite mean squared jump distance, or Lévy distributions when the jump lengths on the network are heavy tailed with infinite mean square jump distance. Any further complication or sophistication in the generating laws apart from these essential features does not affect this universal asymptotic behavior. We will analyze these behaviors for Markovian walks on networks thoroughly in the course of the book. By this observation for the behavior after sufficiently long times of observation, it is sufficient to consider “simple” generating laws leading to the same of the two possible universal asymptotic behaviors as the “real” perhaps complicated unknown generating law.

In this book, we uniquely consider Markovian walks where the walker undertakes uncorrelated steps on a network or in the continuum limit on a continuous space. We mainly analyze time discrete walks but also derive limiting transitions to time continuous walks. One principal focus is concentrated on the analysis of “long-range navigation” of walks with “long-range steps” where the walker in one-time step can reach far distant nodes. The notion of “distance” may appear in two different senses, either as the distance on the network counting the smallest number of steps between two nodes, or especially important for continuum limit analysis, where “distance” means the Euclidean distance in the embedding space. “Long-range step” means in the first place that the walker during one-time step can cover a large “network distance”.

For different kinds of random walks, especially walks exhibiting long-distance jumps strategies, we derive dynamic characteristics such as first passage quantities, mean occupation times, the number of distinct nodes visited by a walker, recurrence features and several further quantities of interest. One might expect that there is an infinite family of generating laws leading to an infinite set of different long-range behaviors. However, as mentioned on “sufficiently large” networks the limiting distributions after sufficiently large observation times (on undirected connected networks and lattices) are either Gaussian distributions with Brownian motion or Lévy distributions with Lévy flights. Both cases can be classified by symmetric α stable distributions where the only real long-range navigation that is stable toward rescaling of the network are “fractional walks” with fat-tailed (Lévy) distributions emerging after many time steps. The jump patterns that occur from such heavy-tailed jump distributions with the occurrence of long-range steps leading to diverging mean square jump distances are indeed characteristic for Lévy flights (these can also be referred to as Lévy motions). This behavior is contrasted by the finite mean square displacements of normal diffusive Brownian motions with localized short-distance jumps.

The present book consists of two parts comprising eight principal chapters. The first part “Dynamics on General Networks” (Chapters 1–5) is devoted to the analysis of Markovian random walk features that generally hold in connected undirected networks where we consider both finite and infinite networks. The second part “Dynamics on Lattices” (Chapters 6–8) is devoted to Markovian walks that take place on regular networks and lattices such as hyper-tori and multidimensional integer lattices. All results presented and discussed are systematically derived either within the main text in the chapters or, when the derivations become too lengthy or may disturb the course of the explanations, we have put them into appendices at the ends of the chapters. In the derivations, we have chosen a rather intuitive approach avoiding a formalistic and abstract level of the proofs. All the derivations are performed by employing elementary mathematical methods that students of physics, engineering science or mathematical disciplines in a progressed level should be familiar with.

In Chapter 1, we give a general introduction to basic graph theory where we introduce the Laplacian matrix containing the topological information of the network. We also consider some examples such as the ring and interacting cycles where the eigenvectors and eigenvalues of the Laplacian matrix are explicitly known. In this chapter, we derive the good properties of Laplacian matrices and define matrical functions of the Laplacian matrix that conserve these good properties. In this way, we can later define generalized random walk strategies with new generating rules allowing fast navigation and long-range moves on the network. Among the most interesting candidates, we identified power law matrix functions of the Laplacian matrix, the so-called “fractional Laplacian matrix”, where we demonstrate in detail that its powers are restricted to be between zero and one. We will see in the course of the book that the fractional Laplacian stands out to be the essential generator for asymptotically scale-free long-range navigation and emergence of Lévy flights. Once we have derived the good properties that admissible Laplacian matrix functions need to fulfill, we construct these functions and obtain, when these functions are continuously differentiable, the family of good Laplacian functions as a class of functions with completely monotonic derivatives. In all cases, the family of good Laplacian functions constitutes a certain class of “Bernstein functions”. An essential outcome of this chapter is that any admissible Laplacian matrix function starts with the lowest order either with the Laplacian matrix (“type (i) matrix functions”) or by non-integer fractional power of the Laplacian matrix where the power is restricted between zero and one (“type (ii) matrix function”). Then, we consider several examples of admissible Laplacian matrix functions that define new random walk strategies. We demonstrate in the course of the book, coming from several directions, that the lowest order determines the limiting distribution of the walks generated by these functions after many time steps, namely type (i) walks converge to Gaussian distributions and type (ii) walks to Lévy distributions given that the network is sufficiently large. This universal limiting behavior is purely determined by the lowest orders of the series expansion of the functions explored. The effect of all the higher orders is wiped out and therefore is irrelevant.

In Chapter 2, we discuss a particular case of the Laplacian functions that maintain the good structure of the Laplacian as outlined in Chapter 1 to explore the properties of the fractional Laplacian of a network. The introduction of the fractional Laplacian is motivated by the emergence of long-range correlations in a network. In this way, by using this information we can define different global quantities and dynamical processes that consider the whole structure of a network. We discuss the construction of Laplacian matrix functions and obtain integral representations, especially for the fractional Laplacian matrix by Mellin transforms being equivalent to the so-called “Lévy-Kintchin representation” by employing Lévy densities or Lévy measures. In the appendix of Chapter 2 (section 2.5) we briefly discuss some basic relations and definitions of “measures” by considering “probability measures”.

In Chapter 3, we analyze general properties of Markovian random walks on finite connected (undirected) networks where we can identify this type of walk with Markov chains. The generating laws of time-discrete Markovian random walks are defined by master equations involving the (one-step) transition matrix that contains the Laplacian matrix (function) of the walk. We deduce good properties for a Markovian random walk on connected finite graphs and relate these good properties to ergodicity and aperiodic ergodicity of the Markov chain. We perform a detailed analysis of the spectral properties of ergodic (irreducible) and aperiodic ergodic Markov chains and consider some basic laws such as the “fundamental theorem of Markov chains” and ergodic hypothesis and theorem of Markov chains. We further discuss the relation to the “strong law of large numbers”. We derive further the stationary distribution of normal walks (walks simply generated by the Laplacian matrix) allowing only steps to connected neighbor nodes, and we obtain in this way the mean recurrence time for finite Markov chains (Kac’s formula). Also, we discuss in this chapter periodic ergodicity as realized in bipartite graphs and analyze the related spectral structure of the one-step transition matrix. In an appendix, we analyze the asymptotic behavior of the transition matrix of classical Pólya walks taking place on infinite multidimensional integer lattices Z^d that are bipartite. We show there that in such classical Pólya walks Gaussian distributions emerge after many time steps.

In Chapter 4, we explore the good properties of a Laplacian matrix to obtain a Markovian stochastic random walk (one-step) transition matrix defining the transition probabilities between the nodes of a network in order to generalize random walk strategies to obtain walks with long-distance steps. The chapter is devoted to a systematic study of the non-local dynamics generated by a series of important good Laplacian matrix functions where we investigate characteristics describing the speed of the navigation on the network such as global times the walker needs to visit any node of the network. In this study, the outstanding random walk search capacity of the “fractional walk” is demonstrated.

In Chapter 5, we discuss fractional classical versus fractional quantum transport. First, in this chapter, by starting with master equations defining the random walks on multidimensional lattices, we derive two cases. (1) The classical normal diffusion equation as a continuum limit of a “normal walk” where the step length is constant. This case corresponds to a Pólya type walk on the lattice. (2) The fractional diffusion equation obtained from a master equation with inverse power law fat-tailed step distributions. This walk corresponds to a “fractional walk” (Lévy flight) on the lattice. After deducing several key quantities, such as return probabilities to the departure nodes for the classical walk, we discuss the fractional Schrödinger equation and its network counterpart. In this way, we analyze several essential universal features of fractional quantum walks where remarkable phase effects generate universal behavior independent from the fractional index that characterizes the search efficiency of the fractional quantum walk.

The second part of the book, “Dynamics on Lattices”, is devoted to the analysis of Markovian walks in lattices where we strongly focus on the “fractional random walk” generated by fractional powers of the Laplacian matrix. In Chapter 6, we consider as the most simple one-dimensional cases finite and infinite rings. First, we derive an explicit form of the fractional Laplacian matrix for the infinite ring and use this result to construct the fractional Laplacian matrix for the finite ring. Finally, we deduce pertinent continuum limit distributions of nodes: the infinite space continuum limit and the periodic string continuum limit. In these continuum limits, the fractional Laplacian matrix takes the distributional representations of the kernels of the fractional Laplacian kernel (Riesz fractional derivative kernel). These explicit representations allow a thorough explicit analysis of the fractional walk and its continuum limits on rings. In this chapter, uniquely the fractional operators that generate the fractional walk on the ring and their continuum limits are derived. These results are then employed for an explicit analysis of the fractional walk on the infinite ring in Chapter 7.

In Chapter 7, we consider the fractional walk, i.e. the Markovian random walk that is generated by the fractional power of the Laplacian matrix on the d-dimensional (d = 1, 2, 3, 4, …) periodic d-torus and the infinite lattice limit, which is the d-dimensional integer lattice Z^d. We introduce basic quantities characterizing random walks such as the probabilities of first passage; the numbers of first passage paths connecting a pair of nodes; the probability that a node is ever visited; the mean first passage time (MFPT), i.e. the number of time steps the walker is expected to need to visit a node; the mean occupation time or mean residence time (MRT) the walker stays on a node or a set of nodes; the mean recurrence time (Kac formula); the mean step distance (MSD) (or average velocity) of the walker and the number of distinct nodes visited by the walker, among other characteristics. We analyze these characteristics for the “fractional random walk”, i. e. the random walk generated by a fractional non-integer power of the Laplacian matrix (with an admissible exponent between zero and one). This walk is the “fractional” generalization of the classical Pólya walk. We derive in this chapter the recurrence theorem for this walk (being the fractional counterpart of Pólya’s recurrence theorem) where the fractional walk for exponent one recovers the Pólya walk and Pólya’s recurrence theorem. We further derive asymptotic representations for the Green’s function matrix for the fractional walk where its symmetric elements have the interpretation of mean occupation times. In the recurrent regime, the Green’s function diverges due to infinitely many returns to nodes, whereas in the transient regime the Green’s function exists and is finite. We derive for the transient regime the asymptotic representation of the Green’s function (far from the departure node) taking the representation of Riesz potentials where in the Pólya limit the classical Newtonian potentials are recovered. In the second part, the fractional walk on the infinite ring is analyzed. For the infinite ring, all results including the Green’s functions and their Riesz limits are derived in an explicit form by utilizing the results of Chapter 6.

Finally, Chapter 8 is devoted to the asymptotic analysis of Markovian walks on undirected networks. We derive from the characteristic matrices such as the Laplacian matrix, adjacency matrix and transition matrix continuum limit kernels, which have to be conceived as distributions or generalized functions. Further, we deduce the convolutional diffusion equation governing the asymptotic behavior of Markovian walks. We especially focus on universal asymptotic behavior, i.e. the limiting probability distributions that emerge after sufficiently many time steps in the infinite network limits. We further introduce some “constitutive assumptions” on the node distributions in the infinite multidimensional embedding space where we assume spatially homogeneous and isotropic node distributions leading to isotropic kernels. We analyze especially the distinct asymptotic behavior of types (i) and (ii) Laplacian kernels, where type (i) corresponds to light-tailed adjacency density kernels and type (ii) corresponds to heavy-tailed adjacency density kernels. We deduce the limiting distributions of walks generated by types (i) and (ii) densities: the probability density functions (PDFs) of type (i) walks converge to Gaussian distributions, whereas the PDFs of type (ii) walks converge to Lévy distributions. As an example, we consider the Pearson walk that serves as a proto-example for a type (i) walk with restricted (constant) step distance that the walker can cover in one-time step. We also derive for the transient regime the asymptotic Riesz potential Green’s functions for type (ii) walks taking in the Pólya walk limit (representing hence the universal asymptotic Green’s functions of all type (i) walks) the representations of Newtonian potentials. In this way, we demonstrate again the emergence of Brownian motions for type (i) walks where the steps lengths are drawn from normal distributions, and for type (ii) walks the asymptotic emergence of Lévy flights where the step lengths are drawn from Lévy distributions. At the end of this chapter, we outline some ideas about how to approach the asymptotic behavior of fractal node distribution by considering a Cantor dust distribution of nodes. In the appendices of this chapter, we derive several important integrals and normalization constants that occur repeatedly in the context of Lévy flights and the involved fractional continuum limit distributional kernels. Especially we outline some properties of α-stable symmetric distributions occurring as limiting PDFs in the present analysis. We also derive the “spectral dimension” of Lévy flights in an appendix (section 8.4). The spectral dimension is a generalization of the dimension of the reciprocal (dual) state space. In all demonstrations, we try to give physical interpretations to the derived quantities, and special care is taken with signs of the kernels and their physical interpretations related to the stochastic properties of PDFs.

The present book represents a snapshot of some of our present results and is an attempt to relate them with state-of-the-art contexts. At the same time, we hope that this attempt may bear some fruit in terms of inspiration for the reader. We are happy to receive any feedback.

We would like to express our sincere thanks to Professor Noël Challamel (Université Européenne de Bretagne) for inviting us to compose this book. T.M.M. and A.P.R. would like to express their thanks to the colleagues of the Institut Jean le Rond d’Alembert (Sorbonne Université) for an excellent inspiring atmosphere, and Dr. Ying Huang for reading parts of the manuscript and giving some valuable hints. T.M.M. would like to thank his family for recurrent helpful encouragements. Last but not least we would like to express our gratitude to Professor Stéphane Zaleski (Head of the Institut Jean le Rond d’Alembert) who approved financial support for two visiting stays for A.P.R. at the Institut Jean le Rond d’Alembert (Paris) in 2017 and 2018, which were crucial for the composition of this book.

Thomas MICHELITSCH

Alejandro PÉREZ RIASCOS

Bernard COLLET

Andrzej NOWAKOWSKI

Franck NICOLLEAU

January 2019