Winning quick and dirty: the greedy random walk

E. Ben-Naim and S. Redner

As a strategy to complete games quickly, we investigate one-dimensional random walks where the step length increases deterministically upon each return to the origin. When the step length after the $k^{\rm th}$ return equals $k$, the displacement of the walk $x$ grows linearly in time. Asymptotically, the probability distribution of displacements is a purely exponentially decaying function of $|x|/t$. The probability $E(t,L)$ for the walk to escape a bounded domain of size $L$ at time $t$ decays algebraically in the long time limit, $E(t,L)\sim L/t^{2}$. Consequently, the mean escape time $\langle t\rangle\sim L\ln L$, while $\langle t^n\rangle\sim L^{2n-1}$ for $n>1$. Corresponding results are derived when the step length after the $k^{\rm th}$ return scales as $k^\alpha$ for $\alpha>0$.


source, ps, pdf