Summary: We analyse a simple random process in which a token is moved in the interval \(A= \{ 0,\ldots ,n\} \). Fix a probability distribution {\(\mu\)} over \(D= \{ 1,\ldots ,n \} \). Initially, the token is placed in a random position in \(A\). In round \(t\), a random step size \(d\) is chosen according to {\(\mu\)}. If the token is in position \(x\geqslant d\) then it is moved to position \(x - d\). Otherwise it stays put. Let \(T_X\) be the number of rounds until the token reaches position 0.
We show tight bounds for the expectation \(\mathbf E_{\mu }(T_X)\) of \(T_X\) for varying distributions {\(\mu\)}. More precisely, we show that \(\min_{\mu }\{ \mathbf E_{\mu }(T_X)\} = \Theta ((\log n)^2)\). The same bounds are proved for the analogous continuous process, where step sizes and token positions are real values in \([0,n+ 1)\), and one measures the time until the token has reached a point in [0, 1). For the proofs, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over [0, 1] with a ‘blind’ optimization strategy.