Tight Bounds for Blind Search on the Integers and the Reals

We analyse a simple random process in which a token is moved in the interval A = {0,...,n}. Fix a probability distribution p over D = {1,...,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 >= d, then it is moved to position x - d. Otherwise it stays put. Let Tx be the number of rounds until the token reaches position 0. We show tight bounds for the expectation E-mu(Tx) of Tx for varying distributions mu. More precisely, we show that min(mu){E-mu(Tx)} = 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.