when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-13486
URL:

; ; ;

### Tight Bounds for Blind Search on the Integers

 pdf-format:

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

### BibTeX - Entry

```@InProceedings{dietzfelbinger_et_al:LIPIcs:2008:1348,
author =	{Martin Dietzfelbinger and Jonathan E. Rowe and Ingo Wegener and Philipp Woelfel},
title =	{{Tight Bounds for Blind Search on the Integers}},
booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
pages =	{241--252},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-939897-06-4},
ISSN =	{1868-8969},
year =	{2008},
volume =	{1},
editor =	{Susanne Albers and Pascal Weil},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},