1

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.

Bryden C
  • 71
  • The problem doesn't quite make sense yet. What's the relationship between the value of $X(x)$ (which, by the way, would be much clearer as $f(x)$) and whether or not a particular $x$ value is in $T$? Are the $T$ the local maxima of $X(x)$, or something? – Eoin Mar 06 '22 at 22:48
  • It's also not clear what "achieving a target" or "success" mean here. – Eoin Mar 06 '22 at 22:52
  • Depending on what you're actually trying to do, the solution may be to look at applications of Gaussian Processes to reinforcement learning, e.g. https://gdmarmerola.github.io/ts-for-bayesian-optim/ – Eoin Mar 06 '22 at 22:53
  • Thanks for the resource. I agree that my question is somewhat broad and perhaps ill-posed.

    There is no 'hard' relationship between $X(x)$ and $T$. The exact relationship is highly sensitive to the input. The only knowledge I know is that for values in a neighborhood of $x$, $X$ will map them to the same target with some high but unknown.

     – Bryden C Mar 06 '22 at 23:00
  • So each time you evaluate $X(x)$, it tells you which of the targets that value of $x$ is closest to? – Eoin Mar 06 '22 at 23:02
  • Actually, every time I evaluate $X(x)$ it will necessarily hit one of the targets. The goal from there would be to try to avoid $x$ from that region since nearby $x$ will probably hit the same target. Once any value of $x$ hits a target, I no longer care about future sampled values that also hit the same target. That should have been more clear in the question, sorry. – Bryden C Mar 06 '22 at 23:10
  • Thanks. You might want to update your question to include this information. In this case, I don't have a good answer, but I would be pleasantly surprised if anything would be more efficient than just repeatedly bisecting $x$, e.g. $.5$, then $.25, .75$, then $.125, .375, .625, .875$, and so on. – Eoin Mar 07 '22 at 11:12
  • Maybe you can get some ideas from here? https://stats.stackexchange.com/questions/40384/fake-uniform-random-numbers-more-evenly-distributed-than-true-uniform-data – num_39 Mar 07 '22 at 12:12
  • Sorry but the question is still far from clear. Is $Y(x)$ random or just a constant function ? (i.e. if you evaluate $Y$ twice with the same input does it return the same output?) . What is $X(x)$ ? you didn't define it anywhere in your question. Does the output have to be exactly equal to the targets or just close enough ? – J. Delaney Mar 08 '22 at 12:32
  • Thanks for the points, I've clarified all of these in the post. Indeed, $Y(x)$ is a constant function. The notation $X(x)$ was the (admittedly poor) notation I initially had and I forgot to change that when I moved everything over to $Y(x)$. Finally, yes the output needs to be exactly equal to the targets - in fact there isn't any definition of 'close enough' to a target. – Bryden C Mar 08 '22 at 19:47

1 Answers1

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

MrSmithGoesToWashington
  • 118