TY - JOUR
T1 - Tight Bounds for Blind Search on the Integers and the Reals
AU - Dietzfelbinger, M
AU - Rowe, Jonathan
AU - Wegener, I
AU - Woelfel, P
PY - 2010/11/1
Y1 - 2010/11/1
N2 - 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.
AB - 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.
U2 - 10.1017/S0963548309990599
DO - 10.1017/S0963548309990599
M3 - Article
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
SN - 1469-2163
VL - 19
SP - 711
EP - 728
JO - Combinatorics, Probability and Computing
JF - Combinatorics, Probability and Computing
IS - 5-6
ER -