How to efficiently bias future samples?

Question

My goal is to hit all of my 'targets' through a random variable $Y : [0,1] \rightarrow \mathbb{R}$. An explicit form of $Y$ is unknown but I am able to take a sample point as pass it to $Y$ and get its output.

Specifically, I am initially sampling points uniformly on $[0,1]$. For each sampled point $x_j$ I can compute $Y(x_j)$ easily (and repeated evaluations of the same $x_j$ will give the same output). I also know that outputs should be close with respect to input: $\mathbb{P}[Y(x_i) = Y(x_j)]$ should be roughly proportional to $|x_i - x_j|$.

Suppose $\{ T_j : 1 \leq j \leq m\}$ are my targets. I know that my random variable will necessarily map to one of these targets: $Y(x) = T_j$ for some $j$ and every $x \in [0,1]$. I want to sample until all my targets have been achieved in the sense that $\{ T_1, \dots, T_m \} \subseteq \{ Y(x_1), \dots, Y(x_n)\}$. Once I know of one point $x_j$ that maps to $T_k$, I no longer care about any future sampled point that also maps to $T_k$. Further, the labels of the targets are arbitrary; for example $T_1$ is no closer or further from $T_2$ than it is from $T_{126}$.

In order to minimize $n$, I want to bias my sampling so that successive samples are 'far away' from the values that were successful, for example if $Y(x_1) = T_1$, I want to actively avoid the region around $x_1$ since it is likely that nearby points also map to $T_1$. An idea I had regarding this is to do a sort of reverse kernel density estimate, whereby I can create a density $f$ based on the first point that hits a target and sample from a normalized version of $\max(1 - f, 0)$.

I'm not super familiar with sampling techniques, so if anyone can direct me to some theory that can do what I am seeking it would be greatly appreciated. I am also open to totally different methods of solving my problem.

Answer 1

Begin with uniform distribution $U_0$ on $[0,1]$.

Define a suitable value for $0 < \epsilon <1 $, and $0 < \alpha < 1$.

randomly choose $x_1$, $x_2$ .. until you hit a target.

If from $x_i$ you hit a target, just decrease the probability density by alpha on $[x_i - \epsilon, x_i + \epsilon] \cap [0,1]$ and increase every where else in $[0,1]$ so that you still have a total probability of one. The new probability is $U_1$.

Pick other $x_i$ under $U_1$, and repeat until you hit a target. Following the same plan, you'll get $U_2$, and so on.

Little by little, your probability will concentrate on places where you did'nt found a $x$ that leads to a target. But you may still, with a lower probability pick a $x$ near one other that leads to a taget. If you really want to avoid that, then choose $\alpha = 1$.

By experiment, you will be able to tune $\epsilon$ and $\alpha$ so that you hit the greatest number of target in the shortest time (I suppose this is what you want to do).