Abstract.
We analyze a simple random process in which a token is moved in the interval
A={0,...,n}:
Fix a probability distribution mu over {1,dots,n}.
Initially, the token is placed in a random position in A.
In round t, a random value d is chosen according to mu.
If the token is in position a≥d, then it is moved to position a-d.
Otherwise it stays put.
Let T be the number of rounds until the token reaches position 0.
We show tight bounds for the expectation of T for the optimal distribution mu.
More precisely, we show that for the best distribution mu, E(T)=Θ((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.