A stochastically quasi-optimal search algorithm for the maximum of the simple random walk

• 成果类型: Article
• 署名作者: Chassaing, P; Marckert, JF; Yor, M
• 署名单位: Universite de Lorraine; Universite Paris Saclay; Universite Paris Cite; Sorbonne Universite
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 2003
• 页码: 1264-1295
• 关键词: brownian bridge; LAWS; functionals; FORMULA

摘要

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.