Abstract
A lattice random walk is a mathematical representation of movement through random steps on a lattice at discrete times. It is commonly referred to as Pólya’s walk when the steps occur in either of the nearest-neighbor sites. Since Smoluchowski’s 1906 derivation of the spatiotemporal dependence of the walk occupation probability in an unbounded one-dimensional lattice, discrete random walks and their continuous counterpart, Brownian walks, have developed over the course of a century into a vast and versatile area of knowledge. Lattice random walks are now routinely employed to study stochastic processes across scales, dimensions, and disciplines, from the one-dimensional search of proteins along a DNA strand and the two-dimensional roaming of bacteria in a petri dish, to the three-dimensional motion of macromolecules inside cells and the spatial coverage of multiple robots in a disaster area. In these realistic scenarios, when the randomly moving object is constrained to remain within a finite domain, confined lattice random walks represent a powerful modeling tool. Somewhat surprisingly, and differently from Brownian walks, the spatiotemporal dependence of the confined lattice walk probability has been accessible mainly via computational techniques, and finding its analytic description has remained an open problem. Making use of a set of analytic combinatorics identities with Chebyshev polynomials, I develop a hierarchical dimensionality reduction to find the exact space and time dependence of the occupation probability for confined Pólya’s walks in arbitrary dimensions with reflective, periodic, absorbing, and mixed (reflective and absorbing) boundary conditions along each direction. The probability expressions allow one to construct the time dependence of derived quantities, explicitly in one dimension and via an integration in higher dimensions, such as the first-passage probability to a single target, return probability, average number of distinct sites visited, and absorption probability with imperfect traps. Exact mean first-passage time formulas to a single target in arbitrary dimensions are also presented. These formulas allow one to extend the so-called discrete pseudo-Green function formalism, employed to determine analytically mean first-passage time, with reflecting and periodic boundaries, and a wealth of other related quantities, to arbitrary dimensions. For multiple targets, I introduce a procedure to construct the time dependence of the first-passage probability to one of many targets. Reduction of the occupation probability expressions to the continuous time limit, the so-called continuous time random walk, and to the space-time continuous limit is also presented.
- Received 30 January 2020
- Revised 19 March 2020
- Accepted 31 March 2020
DOI:https://doi.org/10.1103/PhysRevX.10.021045
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
The diffusion equation models random movement and is one of the fundamental equations of physics. To compare model predictions with empirical observations, the diffusion equation needs to be studied in finite space. When space and time are continuous, the analytic solution of the diffusion equation in finite domains has been known for a long time. But finding an exact solution when space and time are discrete has remained an outstanding problem for over a century—until now. I find the analytic solution of the discrete diffusion equation in confined domains and use it to predict how the probability for various reaction diffusion processes changes over time.
I make joint use of two techniques: special mathematical functions known as Chebyshev polynomials and a technique invented to tackle electrostatic problems, the so-called method of images. This approach allows me to construct hierarchically the solution to the discrete diffusion equation in higher dimensions from the one in lower dimensions.
The exact solution allows me to calculate transport quantities that, until now, could be derived only via time-consuming computer simulations or not at all because of prohibitive computational costs. In the context of random search processes, it is now possible to calculate accurately the probability for a “searcher” to reach a target for the first time, to return to its initial starting position, and to remain trapped at special defective locations.
These findings are directly relevant to a vast number of applications such as molecules moving inside a cell, animals foraging for resources in their home ranges, robots searching in a disaster area, and humans passing information or a disease.