TY - GEN

T1 - Search for the maximum of a random walk (extended abstract)

AU - Odlyzko, A. M.

PY - 1994/5/23

Y1 - 1994/5/23

N2 - This paper examines the efficiency of various strategies for searching in an unknown environment. The model is that of the simple random walk, which can be taken as a representation of a function with a bounded derivative that is difficult to compute. Let Xl, X2, . . be independent and identically distributed with Prob(Xj = 1) = Prob(Xj = -1) = l/2, andlet S =X1+ X2+. ..+X-. Thus sk is the position of a symmetric random walk on the line after k steps. The number of the sk that have to be examined to determine their maximum &ln = max{So, . . . . S. } is shown to be N n/2 as n - co, but that is a worst case result. Any algorithm that determines M with certainty must examine at least (co + O(1)) nl /2 of the sk on average for a certain constant co >0, if all random walks with n steps are considered equally likely. There is also an algorithm that on average examines only (CO+ O(1))n]1/2 of the Sk to determine M.. Different results are obtained when one allows a nonzero probability of error, or else asks only for an estimate of J!&. Absolute certainty in the answer, even for an approximation to M, is shown to be much costlier to obtain than a value that differs from Mn with low probability.

AB - This paper examines the efficiency of various strategies for searching in an unknown environment. The model is that of the simple random walk, which can be taken as a representation of a function with a bounded derivative that is difficult to compute. Let Xl, X2, . . be independent and identically distributed with Prob(Xj = 1) = Prob(Xj = -1) = l/2, andlet S =X1+ X2+. ..+X-. Thus sk is the position of a symmetric random walk on the line after k steps. The number of the sk that have to be examined to determine their maximum &ln = max{So, . . . . S. } is shown to be N n/2 as n - co, but that is a worst case result. Any algorithm that determines M with certainty must examine at least (co + O(1)) nl /2 of the sk on average for a certain constant co >0, if all random walks with n steps are considered equally likely. There is also an algorithm that on average examines only (CO+ O(1))n]1/2 of the Sk to determine M.. Different results are obtained when one allows a nonzero probability of error, or else asks only for an estimate of J!&. Absolute certainty in the answer, even for an approximation to M, is shown to be much costlier to obtain than a value that differs from Mn with low probability.

UR - http://www.scopus.com/inward/record.url?scp=0028123962&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028123962&partnerID=8YFLogxK

U2 - 10.1145/195058.195182

DO - 10.1145/195058.195182

M3 - Conference contribution

AN - SCOPUS:0028123962

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 336

EP - 345

BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994

PB - Association for Computing Machinery

T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994

Y2 - 23 May 1994 through 25 May 1994

ER -