Random Walk  

Random Walks in General > s.a. diffusion; Semigroups.
* Idea: A probability measure on the space of all paths on a space; Can be considered as a type of open system; For example, Brownian motion.
* Specification: It can be assigned as a transition probability from each incomplete, n-step path, to each extension to n+1 steps; A simple type of situation is a Markov process, in which the probability only depends on the n-th configuration.
* Displacement: In a space of Hausdorff dimension d, the mean square displacement after N steps is \(\langle\)D2\(\rangle\) ~ N 2/d; The planar (d = 2) self-avoiding walk has rms displacement exponent 3/4 (long conjectured, proved in 2001).
* Applications: Used to sample a space of states in randomized algorithms.
@ General references: Feynman et al 63, I-6-6 (simple); Franceschetti et al AJP(93)dec [as eigenvalue problem]; Hughes 95, 96; in Ambjørn et al 97; Marchetti & da Silva BJP(99)mp/04 [and Brownian motion]; Barkema et al PRL(01) [with random static traps]; Campanino & Petritis in(04)m.PR/02 [survey and relevance]; Nakamura & Small PLA(07) [test]; Lawler & Limic 10; Rudnick & Gaspari 10 [advanced intro].
@ Statistics: Ferraro & Zaninetti PhyA(04) [statistics of visits]; Zhang et al CTP(11)-a1010 [1D, recurrence properties]; Bénichou & Voituriez PRP(14) [evaluation of mean first-passage time].
@ Related topics: Bellissard et al JPA(97) [distributions, using non-commutative geometry]; Zia & Schmittmann AJP(03)sep [distribution of variances]; Majumdar & Trizac PRL(19) + news pt(19)aug [application to integral calculations]; > s.a. particle effects in quantum gravity.

Special Types > s.a. Lévy Process; dynamical triangulations.
* Polya walk: The walker takes one step at integer numbers of time steps of the same width.
* Montroll-Weiss continuous-time walk: The time intervals between successive steps are independent, exponentially and identically distributed random variables.
* Self-avoiding: In 3D the expected length after N steps goes like N 0.6 rather than N 0.5 as the simple random walk or diffusion.
* Types of flights: Benoît Mandelbrot called Lévy flight, Cauchy flight and Rayleigh flight random walks with different step size probability distributions.
@ Types of processes: Burda et al PRL(09) [maximal entropy random walk, localization]; Cabezas et al JSP(14)-a1307 [activated, critical behavior]; Bénichou et al PhyA(13) [inequivalence of the discrete-time Polya walk and the Montroll-Weiss continuous-time random walk]; Garbaczewski & Żaba APPB(15)-a1412 [non-local]; Sciarretta a1605 [simulating quantum mechanics].
@ On random sets: Barat & Chakrabarti PRP(95); Faggionato et al CMP(06); Caputo & Faggionato AAP(07)m.PR/06; Zeitouni JPA(06) [rev]; Bogachev in(06)-a0707 [rev]; Juhász JPA(08) [renormalization group approach]; Lenci a0810-wd [invariance principle and recurrence]; > s.a. voronoi tilings.
@ On other sets: Bender et al JMP(94) [non-integer dimension]; Woess 00 [infinite graphs]; Davison et al JPA(01) [fractals]; Kostrykin & Schrader m.CO/04 [on graphs, generating functions]; Franceschetti JSP(07) [inside n-disk]; Mazzolo JPA(09) [bounded geometries]; Telcs JSP(10) [Penrose lattice]; Turban JPA(14) [fully connected lattice].
@ Self-avoiding: Prellberg JPA(01) [scaling]; Hueter m.PR/01 [D = 2], m.PR/01 [D > 2]; Brydges et al ProbS(09)-a0906 [functional-integral representation]; Clisby JSP(10)-a1005 [pivot algorithm]; Guttmann APN-a1212 [rev].

Quantum Walk > s.a. classical limit; decoherence; quantum computation.
* Rem: A quantum random walker is capable of moving much faster than its classical counterpart.
@ Reviews: Kempe CP(03)qp; Venegas-Andraca QIP(12)-a1201 [comprehensive review].
@ General references: Aharonov et al PRA(93) [introduction]; Childs et al QIP(02)qp/01 [vs classical]; Konno FNL(05)qp/04 [quantum to classical, path integral]; Wang & Douglas qp/07-wd [applied to graph isomorphism problem]; Yin et al PRA(08)-a0708 [in a random environment]; Manouchehri & Wang PRA(09)-a0809 [physical realization]; Chandrashekar PhD(09)-a1001; Sarkar et al Pra(17)-a1505 [effective Hamiltonian approach]; Boettcher et al PRA(15)-a1410, Dadras et al a1802 [relation with classical random walk]; Funakawa et al a1901 [time operators]; Sako a2003 [categorical framework].
@ Models, realizations: Dür et al PRA(02)qp [experiment proposal]; Kosik CEJP(03) [two models]; Schmitz et al PRL(09) [trapped ion]; Krovi et al PRA(10) [spatial search with hitting time ∝ tclassical1/2 using adiabatic quantum computing]; Grünbaum & Velázquez a1111 [on the non-negative integers]; Matsue et al a1507 [on simplicial complexes].
@ Discrete time: Molfetta & Debbasch JMP(12) [continuous limit]; Joshi et al a1802 [path-integral approach]; Arnault et al PRA(19)-a1807 [as lattice fermions]; Chagas & Portugal EPTCS-a2001 [on oriented graphs]; Vallejo et al a2004 [entropy production].
@ Continuous time: Strauch PRA(06) [and discrete]; Manouchehri & Wang JPA(07)qp/06 [state space must be discrete]; Jafarizadeh & Sufiani a0704 [spectral analysis]; Childs CMP(10)-a0810 [and discrete]; Agliari et al JPA(08)-a0810; Salimi AP(09) [on star graphs]; Mülken & Blumen PRP(11) [and coherent transport on complex networks]; Falloon et al CPC(17)-a1606 [on arbitrary graphs, QSWalk Mathematica package]; Chia et al Quant(17)-a1608 [hitting time].
@ Continuous, as limit of discrete: D'Alessandro RPMP(10)-a0902; Dheeraj & Brun PRA(15)-a1501; Arrighi et al a1505 [continuum limit as Dirac particle in curved spacetime]; Arrighi & Facchini a1609 [arbitrary dimensions, curved spacetime]; Arrighi et al a1711; Arrighi et al PRA(18)-a1803 [Dirac equation, honeycomb and triangular lattices]; Di Molfetta & Arrighi a1906 [with a continuous-spacetime limit].
@ 1D: Carteret et al JPA(03)qp [asymptotics]; Romanelli et al PhyA(04)qp/03 [as Markov process]; Fuss et al a0705 [analytic solution]; Štefaňák et al NJP(09)-a0902 [biased, Polya number]; Hinarejos et al a1204 [using Wigner functions]; Dukes RiP(14)-a1405 [on circles, state revivals]; > s.a. Wojcik Model.
@ 2D: Watabe et al PRA(07)-a0802 [1-parameter family, limit distributions]; Bressler et al a0903 [examples and phenomena]; Baryshnikov et al JSP(10).
@ Relativistic effects: Strauch JMP(07) [and Dirac equation]; Kurzyński PLA(08) [Klein's paradox and Zitterbewegung].
@ Related topics: Martin et al PRD(05)gq/04 [in generalized quantum mechanics]; Rodríguez-Rosario et al PRA(10)-a0905 [quantum stochastic walk]; Feng et al a1010 [of waves]; Gudder & Sorkin GRG(11)-a1105 [two-site, quantum measure]; Ellinas et al RPMP(12)-a1207 [role of discrete randomness]; Schuhmacher et al a2004 [quantum simulation]; > s.a. quantum statistical mechanics [thermalization].
> Related topics: see dirac equation; graph theory and physics; quaternions [quaternion walks].

main pageabbreviationsjournalscommentsother sitesacknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 8 may 2020