Large deviations and slowdown asymptotics for one-dimensional excited random walks

Jonathon Peterson (Purdue University)


We study the large deviations of excited random walks on $\mathbb{Z}$. We prove a large deviation principle for both the hitting times and the position of the random walk and give a qualitative description of the respective rate functions. When the excited random walk is transient with positive speed $v_0$, then the large deviation rate function for the position of the excited random walk is zero on the interval $[0,v_0]$ and so probabilities such as $P(X_n < nv)$ for $v \in (0,v_0)$ decay subexponentially. We show that rate of decay for such slowdown probabilities is polynomial of the order $n^{1-\delta/2}$, where $\delta>2$ is the expected total drift per site of the cookie environment. 

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

Pages: 1-24

Publication Date: June 21, 2012

DOI: 10.1214/EJP.v17-1726


  • Basdevant, Anne-Laure; Singh, Arvind. On the speed of a cookie random walk. Probab. Theory Related Fields 141 (2008), no. 3-4, 625--645. MR2391167
  • Basdevant, Anne-Laure; Singh, Arvind. Rate of growth of a transient cookie random walk. Electron. J. Probab. 13 (2008), no. 26, 811--851. MR2399297
  • Benjamini, Itai; Wilson, David B. Excited random walk. Electron. Comm. Probab. 8 (2003), 86--92 (electronic). MR1987097
  • Brillinger, David R. A note on the rate of convergence of a mean. Biometrika 49 1962 574--576. MR0156372
  • Bryc, Włodzimierz; Dembo, Amir. Large deviations and strong mixing. Ann. Inst. H. Poincaré Probab. Statist. 32 (1996), no. 4, 549--569. MR1411271
  • Comets, Francis; Gantert, Nina; Zeitouni, Ofer. Quenched, annealed and functional large deviations for one-dimensional random walk in random environment. Probab. Theory Related Fields 118 (2000), no. 1, 65--114. MR1785454
  • de Acosta, A. Upper bounds for large deviations of dependent random vectors. Z. Wahrsch. Verw. Gebiete 69 (1985), no. 4, 551--565. MR0791911
  • Dembo, Amir; Peres, Yuval; Zeitouni, Ofer. Tail estimates for one-dimensional random walk in random environment. Comm. Math. Phys. 181 (1996), no. 3, 667--683. MR1414305
  • Dembo, Amir; Zeitouni, Ofer. Large deviations techniques and applications. Corrected reprint of the second (1998) edition. Stochastic Modelling and Applied Probability, 38. Springer-Verlag, Berlin, 2010. xvi+396 pp. ISBN: 978-3-642-03310-0 MR2571413
  • Dolgopyat, Dmitry. Central limit theorem for excited random walk in the recurrent regime. ALEA Lat. Am. J. Probab. Math. Stat. 8 (2011), 259--268. MR2831235
  • Dmitry Dolgopyat and Elena Kosygina, Scaling limits of recurrent excited random walks on integers, January 2012, available at arXiv:math/1201.0379.
  • Kesten, H.; Kozlov, M. V.; Spitzer, F. A limit law for random walk in a random environment. Compositio Math. 30 (1975), 145--168. MR0380998
  • Kosygina, Elena; Mountford, Thomas. Limit laws of transient excited random walks on integers. Ann. Inst. Henri Poincaré Probab. Stat. 47 (2011), no. 2, 575--600. MR2814424
  • Kosygina, Elena; Zerner, Martin P. W. Positively and negatively excited random walks on integers, with branching processes. Electron. J. Probab. 13 (2008), no. 64, 1952--1979. MR2453552
  • Lawler, Gregory F. Introduction to stochastic processes. Second edition. Chapman & Hall/CRC, Boca Raton, FL, 2006. xiv+234 pp. ISBN: 978-1-58488-651-8; 1-58488-651-X MR2255511
  • Mogulʹskiĭ, A. A. Small deviations in the space of trajectories. (Russian) Teor. Verojatnost. i Primenen. 19 (1974), 755--765. MR0370701
  • Nagaev, S. V. Large deviations of sums of independent random variables. Ann. Probab. 7 (1979), no. 5, 745--789. MR0542129
  • Ney, P.; Nummelin, E. Markov additive processes II. Large deviations. Ann. Probab. 15 (1987), no. 2, 593--609. MR0885132
  • Rassoul-Agha, Firas. Large deviations for random walks in a mixing random environment and other (non-Markov) random walks. Comm. Pure Appl. Math. 57 (2004), no. 9, 1178--1196. MR2059678
  • Solomon, Fred. Random walks in a random environment. Ann. Probability 3 (1975), 1--31. MR0362503
  • Zerner, Martin P. W. Multi-excited random walks on integers. Probab. Theory Related Fields 133 (2005), no. 1, 98--122. MR2197139

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