Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-23T13:42:43.953Z 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: [email protected])
JONATHAN E. ROWE
Affiliation:
School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK (email: [email protected])
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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 . 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.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 5-6: Papers from the 2009 Oberwolfach Meeting on Combinatorics and Probability , November 2010 , pp. 711 - 728
Copyright
Copyright © Cambridge University Press 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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