A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
From MaRDI portal
Publication:1429105
DOI10.1214/aoap/1069786499zbMath1084.68145OpenAlexW1999128627MaRDI QIDQ1429105
Jean-François Marckert, Marc Yor, Philippe Chassaing
Publication date: 30 March 2004
Published in: The Annals of Applied Probability (Search for Journal in Brave)
Full work available at URL: https://projecteuclid.org/euclid.aoap/1069786499
Inequalities; stochastic orderings (60E15) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Central limit and other weak theorems (60F05) Sums of independent random variables; random walks (60G50) Brownian motion (60J65)
Related Items
Extreme value statistics of correlated random variables: a pedagogical review, On certain functionals of the maximum of Brownian motion and their applications, Random convex hulls and extreme value statistics, On the number of iterations required by Von Neumann addition, How many probes are needed to compute the maximum of a random walk?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Determining the majority
- A formula of S. Ramanujan
- The average height of binary trees and other simple trees
- Excursions in Brownian motion
- Functionals of Brownian meander and Brownian excursion
- A relation between Brownian bridge and Brownian excursion
- Determining the majority: The biased case
- How many probes are needed to compute the maximum of a random walk?
- Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions
- A Random Walk and a Wiener Process Near a Maximum
- Kac's formula, levy's local time and brownian excursion
- Locating the maximum of a simple random sequence by sequential search
- Honest bernoulli excursions
- Average case selection
- A bernoulli excursion and its various applications
- Path Decomposition and Continuity of Local Time for One-Dimensional Diffusions, I
- The distribution of the maximum Brownian excursion
- Euler Sums and Contour Integral Representations
- Noisy Information and Computational Complexity
- The Distribution of Heights of Binary Trees and Other Simple Trees
- A constant arising from the analysis of algorithms for determining the maximum of a random walk
- Search for the maximum of a random walk
- Random Search in the Presence of Noise, with Application to Machine Learning
- On the Random Walk and Brownian Motion
- Brownian Local Times and Taboo Processes
- Optimal Search for a Maximum with Sequences of Simultaneous Function Evaluations
