Algorithm to chase a moving target

Question

Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where $n$ is fixed and known for given $f$. To query $f$, an element $x$ (the guess) from $$\{0, 1, ..., n - 1\}$$ is provided, and the value returned is $(f_S - x) \mod n$. Additionally, the state $f_S$ of$f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

By making uniformly random guesses with each query, one would expect to have to make $n$ guesses before getting $f_S = x$, with variance $n^2 - n$ (stated without proof).

Can an algorithm be designed to do better (i.e., make fewer guesses, possibly with less variance in the number of guesses)? How much better could it do (i.e., what's an optimal algorithm, and what is its performance)?

An efficient solution to this problem could have important cost-saving implications for shooting at a rabbit (confined to hopping on a circular track) in a dark room.

Answer 1

First of all, I will assume that by

Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

you actually mean

Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly at random from $$\left\{- \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|, \ldots, -1, 0, 1, 2, \ldots, \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|\right\} $$

Otherwise, it is not entirely clear that $f_S \in \{ 0, ..., n-1\}$ always holds and how exactly $f_S \pm k$ behaves.

Using this, the problem basically comes down to "missing as much as possible". Observe that the closer we shoot the rabbit, the larger hops he makes; in the extreme case we have $f_S - x = \pm 1 \mod n$. This results in a uniform hop between $ -(\lfloor n/2 \rfloor \pm 1)$ and $ (\lfloor n/2 \rfloor \pm 1)$, which basically completely randomizes the position of the rabbit again. On the other hand, if we miss as badly as possible - by an offset of $f_S - x \mod n = \lfloor n/2 \rfloor$, the rabbit actually does not move at all (!) and the black box actually updates us on this fact. Therefore, we can just turn around and shoot the rabbit.

We are left with finding a procedure for missing increasingly in each shot. I propose a simple "binary search". (I will conveniently omit the rounding.) It proceeds roughly as follows:

1. Reset and shoot at an arbitrary position until you get from the blackbox the answer $(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$ This takes a constant amount of steps in expectation.
2. Now, we know that the rabbit's past position $f_S$, and that it did not move more than $\frac{1}{4}n$ steps in either direction. This basically halves our search space in the next iteration, since the rabbit has to be at a position $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
3. Recurse: Shoot at position $f_S - n/2 \mod n$. With probability $1/2$, the position $f_S'$ the rabbit jumped onto in step 1&2 lies the range $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$. In that case we halved the search space once more. With probability $1/2$, the rabbit did not jump in that range, but since we know that $f_S' - x \mod n = f_S' - f_S + n/2 \mod n \in \{ \frac{1}{2}n - \frac{1}{4}n, ..., \frac{1}{2}n + \frac{1}{4}n \}$, we have the same assumptions as in step (2) and therefore lose nothing.

Each step needs $2 = \mathcal{O}(1)$ expected time to succeed and halves the search space, yielding an overall of $\mathcal{O}(\log n)$ expected number of steps.