Document Open Access Logo

Tight Bounds for Blind Search on the Integers

Authors Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2008.1348.pdf
  • Filesize: 284 kB
  • 12 pages

Document Identifiers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We analyze a simple random process in which a token is moved in the
   interval $A={0,dots,n$: Fix a probability distribution $mu$
   over ${1,dots,n$.  Initially, the token is placed in a random
   position in $A$.  In round $t$, a random value $d$ is chosen
   according to $mu$.  If the token is in position $ageq d$, then it
   is moved to position $a-d$.  Otherwise it stays put.  Let $T$ be
   the number of rounds until the token reaches position 0.  We show
   tight bounds for the expectation of $T$ for the optimal
   distribution $mu$.  More precisely, we show that
   $min_mu{E_mu(T)=Thetaleft((log n)^2
ight)$.  For the
   proof, 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.

Cite As Get BibTex

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel. Tight Bounds for Blind Search on the Integers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 241-252, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008) https://doi.org/10.4230/LIPIcs.STACS.2008.1348

Author Details

Martin Dietzfelbinger
Jonathan E. Rowe
Ingo Wegener
Philipp Woelfel
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact