Tight Bounds for Blind Search on the Integers

Details Tight Bounds for Blind Search on the Integers Tight Bounds for Blind Search on the Integers

2008-02-20

arxiv.org/abs/0802.2852v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Data Structures and Algorithms

Scientific paper

We analyze a simple random process in which a token is moved in the interval $A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,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 $a\geq 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)\=\Theta((\log n)^2)$. 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.

Affiliated with

Also associated with

No associations

Rating

Tight Bounds for Blind Search on the Integers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight Bounds for Blind Search on the Integers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Bounds for Blind Search on the Integers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647830