LIPIcs.STACS.2008.1348.pdf
- Filesize: 284 kB
- 12 pages
Document
Tight Bounds for Blind Search on the Integers
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
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
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.
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads