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