Search for the maximum of a random walk

DOI10.1002/rsa.3240060215zbMath0818.60065OpenAlexW1978029981MaRDI QIDQ4697818

Andrew M. Odlyzko

Publication date: 7 August 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240060215

zbMATH Keywords

symmetric random walksymmetric random walk on the integerssearching in an unknown environment

Mathematics Subject Classification ID

Extreme value theory; extremal stochastic processes (60G70) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Related Items

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, Asymptotic enumeration of RNA structures with pseudoknots, Random convex hulls and extreme value statistics, How many probes are needed to compute the maximum of a random walk?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Number theory in science and communication. With applications in cryptography, physics, biology, digital information, and computing
• On the deterministic complexity of searching local maxima
• A Fibonacci Version of Kraft’s Inequality Applied to Discrete Unimodal Search
• Locating the maximum of a simple random sequence by sequential search
• Shape from probing
• Random Search in the Presence of Noise, with Application to Machine Learning
• Parallel minimax search for a maximum
• Optimal Search for a Maximum with Sequences of Simultaneous Function Evaluations
• Sequential Minimax Search for a Maximum