Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T15:51:41.774Z Has data issue: false hasContentIssue false
  • English
  • Français

Tight Bounds for Blind Search on the Integers and the Reals

Published online by Cambridge University Press:  18 December 2009

MARTIN DIETZFELBINGER,
JONATHAN E. ROWE,
INGO WEGENER and
PHILIPP WOELFEL
MARTIN DIETZFELBINGER
Affiliation:
Fakultät für Informatik und Automatisierung, Technische Universität Ilmenau, 98684 Ilmenau, Germany (e-mail: martin.dietzfelbinger@tu-ilmenau.de)
JONATHAN E. ROWE
Affiliation:
School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK (email: J.E.Rowe@cs.bham.ac.uk)
INGO WEGENER
Affiliation:
Fakultät für Informatik, Technische Universität Dortmund, 44221 Dortmund, Germany
PHILIPP WOELFEL
Affiliation:
Department of Computer Science, University of Calgary, Calgary, Alberta T2N 1N4, Canada (email: woelfel@cpsc.ucalgary.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We analyse a simple random process in which a token is moved in the interval A = {0, . . ., n}. Fix a probability distribution μ over D = {1, . . ., n}. Initially, the token is placed in a random position in A. In round t, a random step sized is chosen according to μ. If the token is in position x ≥ d, then it is moved to position x − d. Otherwise it stays put. Let TX be the number of rounds until the token reaches position 0. We show tight bounds for the expectation Eμ(TX) of TX for varying distributions μ. More precisely, we show that $\min_\mu\{\E_\mu(T_X)\}=\Theta\bigl((\log n)^2\bigr)$. The same bounds are proved for the analogous continuous process, where step sizes and token positions are real values in [0, n + 1), and one measures the time until the token has reached a point in [0, 1). For the proofs, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over [0, 1] with a ‘blind’ optimization strategy.

References

[1]Aspnes, J., Diamadi, Z. and Shah, G. (2002) Fault-tolerant routing in peer-to-peer systems. In Proc. 21st Annual Symposium on Principles of Distributed Computing (PODC 2002), pp. 223–232.CrossRefGoogle Scholar
[2]Aspnes, J., Diamadi, Z. and Shah, G. (2003) Fault-tolerant routing in peer-to-peer systems. arXiv:cs/0302022v2.Google Scholar
[3]Droste, S., Jansen, T. and Wegener, I. (2006) Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst. 39 525–544.CrossRefGoogle Scholar
[4]Jägersküpper, J. (2007) Algorithmic analysis of a basic evolutionary algorithm for continuous optimization. Theoret. Comput. Sci. 379 329–347.CrossRefGoogle Scholar
[5]Kiefer, J. (1953) Sequential minimal search for a maximum. Proc. Amer. Math. Soc. 4 502–506.CrossRefGoogle Scholar
[6]Rowe, J. E. and Hidović, D. (2004) An evolution strategy using a continuous version of the Gray-code neighbourhood distribution. In Genetic and Evolutionary Computation (GECCO 2004), Part I, Vol. 3102 of Lecture Notes in Computer Science, Springer, pp. 725–736.Google Scholar