1
$\begingroup$

I have been trying to devise an algorithm for a problem that's been bugging me for a while. For some weird reason I haven't been able to find any mention of this problem in the literature, so far. I find that curious, though, which is why I would like to ask for help here...

In a nutshell, the problem can be stated as follows: Find the largest possible value in an unsorted sequence of numbers that can only be observed incrementally (online). The numbers in the sequence adhere to some unknown distribution, so you can never be completely sure, if you have already found the largest value. You cannot go back to a previous value and once the current value is selected as the "largest possible", the process is stopped.

In pseudo code:

While there are still numbers in the sequence:
    n = select the next number in the sequence
    do some analysis with the numbers observed so far
    if n meets some criterion for being sufficiently large:
        return n
        break
Repeat

Also, the algorithm should ideally select the first good candidate, instead of running and waiting endlessly.

Does anybody happen to know of an efficient algorithm that solves this problem? Any help would be much appreciated.

$\endgroup$
  • 2
    $\begingroup$ a variant of this problem is called the secretary problem (Wikipedia) (but that's typically with a fixed, known N items you're going to choose from; nonetheless, the Wikipedia link gives a good overview of many variants of the problem $\endgroup$ – Ben Bolker Aug 17 '18 at 1:10
  • $\begingroup$ Thanks a lot for pointing me to this. It seems, the "unified approach" and the "cardinal payoff variant" mentioned on that page will help me devise a suitable solution. Indeed, I vaguely remember having come across that article by Martin Gardner, but when I was researching my current problem I was at a loss as to what terms to google for. Would you like to post your comment as an answer, so that I can accept it? $\endgroup$ – Marcus C. Aug 17 '18 at 8:37
2
$\begingroup$

This is going to be heavily dependent on how you define a loss function. Is it "I win if I get the highest number, I lose if I get anything else?" Is it "I win if I'm in the top 5%?"

The question reminded me of a Ted talk where a woman provided a solution under a very specific set of assumptions. She applies it to finding a spouse, where you're rating each candidate on a numeric scale, but once you stick with one you never change. You could probably do more research into her methods: https://www.ted.com/talks/hannah_fry_the_mathematics_of_love

$\endgroup$
  • $\begingroup$ Thanks for the prompt reply. That "spouse" problem indeed seems to describe a very similar problem, I will look into that, thanks a lot. As to the loss function: Hmm, not sure about that. I was thinking more of of metric like "how close does the selected value/spouse come to the theoretical maximum?" $\endgroup$ – Marcus C. Aug 16 '18 at 19:27
  • 2
    $\begingroup$ This seems to me like as much of a decision theoretic as a statistical question. For instance, one factor that matters a lot in this circumstance but has no purely statistical content is the value of time. $\endgroup$ – dsaxton Aug 16 '18 at 19:43
  • $\begingroup$ But it can be framed in a statistical way. In the example I shared, the goal was to maximize the expected value of the number chosen. $\endgroup$ – jntrcs Aug 16 '18 at 21:24

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.