2
$\begingroup$

I'm playing a game where I'm trying to estimate an unknown real number $x$.

An oracle exists that will answer the question of "Is a number $y$ greater than or equal to $x$?", to which the oracle will reply either yes or no. The question may be asked an $t$ number of times.

For example, with an unknown $x=9.5$, the oracle will reply yes to $15$ and no to $9$.

What's the best approach to estimate $x$? It's okay to assume my first guess $y_1$ will always be answered with yes (so I always have some "best" guess available), but now I'm tasked with getting even closer to $x$ with my second guess $y_2$, third guess $y_3$, ..., and last guess $y_t$.

I'm not necessarily looking for a solution to this problem, but at least the established name for it so I may do some research. Concepts like optimization, numerical analysis, and machine learning come to mind, but they are large, deep fields, and I'm not quite sure where to turn.

My use case for this algorithm is to discover the optimal frequency to send requests to a service which is frequency-capped by an unknown amount. When I send too fast, I get error responses (oracle says no), and when I'm below the cap, I get success responses (oracle says yes). To keep things focused on the important concept, assume the network has no delay.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Use binary search, in this case also known as bisection. $\endgroup$
    – Yuval Filmus
    Sep 10 '15 at 5:57
  • $\begingroup$ Your intended application isn't an example of the oracle you describe. The oracle answers yes or no based only on a single query; in your application, the oracle answers yes or no based your history of queries over some unknown interval of time. For example, suppose you're only allowed five queries per second. If you send ten in the first second, the real oracle will start saying "no". Binary search tells you to back off to five queries in the next second (the right number) but the oracle will keep saying "no" because, after fifteen queries in two seconds, you're averaging 7.5 per second. $\endgroup$
    – David Richerby
    Sep 10 '15 at 7:23
  • 1
    $\begingroup$ The problem you're actually trying to solve is determining the rate of an unknown communication channel, not determining an unknown real number. I'd look look up TCP's congestion avoidance algorithms as a place to start. $\endgroup$
    – David Richerby
    Sep 10 '15 at 7:25
  • $\begingroup$ Fair point @DavidRicherby, but in this case, I can confirm that my rate for the purposes of capping is reset every period (1/frequency). $\endgroup$
    – t-mart
    Sep 10 '15 at 11:07
2
$\begingroup$

For the game you describe, take a look at binary search. It will find the answer in logarithmically many queries: the logarithm of the search space. In some cases interpolation search can perform even better.

For the application you mention at the end, take a look at TCP's congestion avoidance algorithm (additive increase, multiplicative decrease), as David Richerby suggests.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.