2026-07-25T19:15:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1348 2024-03-06T10:32:58Z ddc:004 open_access

Tight Bounds for Blind Search on the Integers Dietzfelbinger, Martin Rowe, Jonathan E. Wegener, Ingo Woelfel, Philipp 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Dietzfelbinger and Jonathan E. Rowe and Ingo Wegener and Philipp Woelfel 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1348 urn:nbn:de:0030-drops-13486 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1348 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode