How many probes are needed to compute the maximum of a random walk?

probes are necessary to compute the maximum of a simple symmetric random walk with n steps, in which c appears under the form of a triple integral. In this paper we prove that (log n/log p-log q)+o(log n) probes are necessary to compute the maximum of a simple asymmetric random walk with n steps. We also give c under closed form.

MoreLess

Year of publication:	1999
Authors:	Chassaing, Philippe
Published in:	Stochastic Processes and their Applications. - Elsevier, ISSN 0304-4149. - Vol. 81.1999, 1, p. 129-153
Publisher:	Elsevier
Keywords:	Average case analysis of algorithms Quasi-optimal algorithm Random walk Brownian motion Brownian meander

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10008875769