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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)0897916638
StatePublished - May 23 1994
Event26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada
Duration: May 23 1994May 25 1994

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129502
ISSN (Print)0737-8017


Other26th Annual ACM Symposium on Theory of Computing, STOC 1994


Dive into the research topics of 'Search for the maximum of a random walk (extended abstract)'. Together they form a unique fingerprint.

Cite this