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 (5)
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
This page was built for publication: A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
