# Algorithm for selecting largest possible value, when observing online sequence of unknown distribution?

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.

• 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 – Ben Bolker Aug 17 '18 at 1:10
• 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? – Marcus C. Aug 17 '18 at 8:37