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

DOI10.1016/S0304-4149(98)00077-5zbMath0962.60018MaRDI QIDQ1593629

Philippe Chassaing

Publication date: 17 January 2001

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

zbMATH Keywords

Brownian motionrandom walkBrownian meanderaverage case analysis of algorithmsquasi-optimal algorithm

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50)

Related Items (2)

On certain functionals of the maximum of Brownian motion and their applications ⋮ A stochastically quasi-optimal search algorithm for the maximum of the simple random walk

Cites Work

• An almost optimal algorithm for unbounded searching
• Functionals of Brownian meander and Brownian excursion
• A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
• A Fibonacci Version of Kraft’s Inequality Applied to Discrete Unimodal Search
• More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case
• More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case
• A Random Walk and a Wiener Process Near a Maximum
• Branching Processes in Simple Random Walk
• A constant arising from the analysis of algorithms for determining the maximum of a random walk
• Search for the maximum of a random walk
• Generalized Kraft’s Inequality and Discrete k-Modal Search
• Parallel minimax search for a maximum
• A property of power series with positive coefficients
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: How many probes are needed to compute the maximum of a random walk?