Random
Walk| Random
Walk |
Random Walk > s.a. diffusion.
* Idea: A probability
measure on the space of all paths on a space; For example, Brownian motion.
* Specification: 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 
D2
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 I-6-6 (simple); Franceschetti et al AJP(93)dec
[as eigenvalue problem]; Hughes 95; 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]; Ferraro & Zaninetti PhyA(04)
[statistics of visits]; Nakamura & Small PLA(07)
[test].
@ Related topics: Bellissard et al JPA(97)
[distributions, using non-commutative geometry];
Zia & Schmittmann AJP(03)sep
[distribution of variances].
Special Types
* 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 processes: Burda et al PRL(09)
[maximal entropy random walk, localization].
@ 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].
@ 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].
Quantum Walk > s.a. classical
limit; decoherence; graph
theory and physics; quantum
computation.
@ General references: Aharonov et al PRA(93)
[introduction]; Childs et al QIP(02)qp/01 [vs
classical]; Kempe CP(03)qp [rev];
Konno FNL(05)qp/04 [quantum
to classical, path integral]; Wang & Douglas qp/07-wd
[applied
to graph isomorphism problem]; Yin et al a0708 [in
random environment]; Manouchehri & Wang a0809/PRL
[physical realization].
@ Models: Dür et al PRA(02)qp [experiment
proposal]; Kosik CEJP(03)
[two models]; Schmitz et al PRL(09)
[trapped ion].
@ Continuous time: Strauch PRA(06)
[and discrete]; Manouchehri & Wang JPA(07)qp/06 [state
space must be discrete]; Jafarizadeh & Sufiani a0704 [spectral
analysis];
Childs a0810 [and
discrete]; Agliari et al JPA(08)-a0810;
D'Alessandro a0902 [as
limit of discrete-time quantum walk]; Salimi AP(09) [on star graphs].
@ 1D: Carteret et al JPA(03)qp [asymptotics];
Romanelli et al PhyA(04)qp/03 [as
Markov process]; Fuss et al a0705 [analytic
solution].
@ 2D: Watabe et al PRA(07)-a0802 [1-parameter
family, limit distributions]; Bressler et al a0903 [examples and phenomena].
@ Relativistic effects: Strauch
JMP(07) [and
Dirac equation]; Kurzynski PLA(08) [Klein's
paradox and Zitterbewegung].
@ Other related topics:
Martin et al PRD(05)gq/04 [in
generalized quantum mechanics]; Stefanák et al NJP(09)-a0902 [1D,
biased, Polya number]; Rodríguez-Rosario et al a0905 [quantum stochastic walk].
main page – abbreviations – journals – comments – other
sites – acknowledgements
send feedback and suggestions to bombelli at olemiss.edu – modified 14
sep 2009