Controlled random walk with a target site

Kenneth S. Alexander (University of Southern California)


We consider a symmetric simple random walk $\{W_i\}$ on $\mathbb{Z}^d, d=1,2$, in which the walker may choose to stand still for a limited time.  The time horizon is $n$, the maximum consecutive time steps which can be spent standing still is $m_n$ and the goal is to maximize $\mathbb{P}(W_n=0)$.  We show that for $d=1$, if $m_n \gg (\log n)^{2+\gamma}$ for some $\gamma>0$, there is a strategy for each $n$ yielding $\mathbb{P}(W_n = 0) \to 1$.  For $d=2$, if $m_n \gg n^\epsilon$ for some $\epsilon>0$ then there are strategies yielding $\liminf_n \mathbb{P}(W_n=0)>0$.

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

Pages: 1-6

Publication Date: June 6, 2013

DOI: 10.1214/ECP.v18-2763


  • Hoeffding, Wassily. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc. 58 1963 13--30. MR0144363
  • McNamara, J. M. Optimal control of the diffusion coefficient of a simple diffusion process. Math. Oper. Res. 8 (1983), no. 3, 373--380. MR0716119
  • McNamara, J. M. A regularity condition on the transition probability measure of a diffusion process. Stochastics 15 (1985), no. 3, 161--182. MR0869198

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