The need for speed: maximizing the speed of random walk in fixed environments

Eviatar Ben Procaccia (Weizmann Institute of Science)
Ron Rosenthal (The Hebrew University of Jerusalem)


We study nearest neighbor random walks in fixed environments of $\mathbb{Z}$ composed of two point types : $(\frac{1}{2},\frac{1}{2})$ and$(p,1-p)$ for $p>\frac{1}{2}$. We show that for every environmentwith density of $p$ drifts bounded by $\lambda$ we have $\limsup_{n\rightarrow\infty}\frac{X_n}{n}\leq (2p-1)\lambda$, where $X_n$ is a random walk in the environment. In addition up to some integereffect the environment which gives the greatest speed is given byequally spaced drifts.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-19

Publication Date: February 11, 2012

DOI: 10.1214/EJP.v17-1800


  • N. Berger, N. Kapur, L.J. Schulman, and V. Vazirani, phSolvency games, Proc. of FSTTCS, vol. 8, Citeseer, 2008.
  • Noam. Berger and Eviatar.B. Procaccia, phMutually excited random walk, in preperation.
  • Gilbert, George T. Positive definite matrices and Sylvester's criterion. Amer. Math. Monthly 98 (1991), no. 1, 44--46. MR1083614
  • Golub, Gene H.; Van Loan, Charles F. Matrix computations. Third edition. Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD, 1996. xxx+698 pp. ISBN: 0-8018-5413-X; 0-8018-5414-8 MR1417720
  • Lee, Susan. Optimal drift on $[0,1]$. Trans. Amer. Math. Soc. 346 (1994), no. 1, 159--175. MR1254190
  • Menshikov, M. V.; Wade, Andrew R. Logarithmic speeds for one-dimensional perturbed random walks in random environments. Stochastic Process. Appl. 118 (2008), no. 3, 389--416. MR2389051
  • Mörters, Peter; Peres, Yuval. Brownian motion. With an appendix by Oded Schramm and Wendelin Werner. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. xii+403 pp. ISBN: 978-0-521-76018-8 MR2604525
  • O. Zeitouni, phLecture notes on random walks in random environment, St Flour Summer School (2001).

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.