Random Walk| 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 page
– abbreviations
– journals – comments
– other sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 8 may 2020