• Open Access

Exact Spatiotemporal Dynamics of Confined Lattice Random Walks in Arbitrary Dimensions: A Century after Smoluchowski and Pólya

Luca Giuggioli
Phys. Rev. X 10, 021045 – Published 28 May 2020
PDFHTMLExport Citation

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.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • 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)

Statistical Physics & Thermodynamics

Authors & Affiliations

Luca Giuggioli

  • Bristol Centre for Complexity Sciences and Department of Engineering Mathematics, University of Bristol, Bristol, BS8 1UB, United Kingdom

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.

Key Image

Article Text

Click to Expand

Supplemental Material

Click to Expand

References

Click to Expand
Issue

Vol. 10, Iss. 2 — April - June 2020

Subject Areas
Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review X

Reuse & Permissions

It is not necessary to obtain permission to reuse this article or its components as it is available under the terms of the Creative Commons Attribution 4.0 International license. This license permits unrestricted use, distribution, and reproduction in any medium, provided attribution to the author(s) and the published article's title, journal citation, and DOI are maintained. Please note that some figures may have been included with permission from other third parties. It is your responsibility to obtain the proper permission from the rights holder directly for these figures.

×

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×