Odlyzko [Random Structures Algorithms
6 (1995) 275-295]
exhibited an asymptotically
optimal algorithm, with respect to the average cost,
among algorithms that find the maximum of a random
walk by using only probes and
comparisons. We extend Odlyzko's techniques
to prove that his algorithm is indeed asymptotically
optimal in distribution (with respect to the stochastic order).
We also characterize the limit law of its cost. Computing its moments
in two ways allows us to recover a surprising identity concerning Euler sums.
Publié le : 2003-11-14
Classification:
Analysis of algorithms,
searching,
random walk,
stochastic order,
Brownian motion,
68Q25,
60J65,
60F17,
68P10,
90B40
@article{1069786499,
author = {Chassaing, P. and Marckert, J. F. and Yor, M.},
title = {A stochastically quasi-optimal search algorithm for the maximum of the simple random walk},
journal = {Ann. Appl. Probab.},
volume = {13},
number = {1},
year = {2003},
pages = { 1264-1295},
language = {en},
url = {http://dml.mathdoc.fr/item/1069786499}
}
Chassaing, P.; Marckert, J. F.; Yor, M. A stochastically quasi-optimal search algorithm for the maximum of the simple random walk. Ann. Appl. Probab., Tome 13 (2003) no. 1, pp. 1264-1295. http://gdmltest.u-ga.fr/item/1069786499/