1
$\begingroup$

Suppose you have an array of n normally distributed numbers whose values are initially unknown(and the probability parameters are unknown too). You must choose one number and you want it to have maximum value. You examine the numbers one number at a time. You may only choose a number right after it is examined(that is we learn it's value) and before the next number is examined. What strategy would you use to maximize the expected value of chosen number?

My intuition and thinking:.
We can use numbers seen so far to estimate the distribution. We can than calculate the expected value of the maximum number in the rest of the list and if it is less than the current number we will take the current number. First of all is my thinking at all correct? And second of all can someone help me with the actual calculations because I have only taken one course in undergraduate probability so far. Thank you!

$\endgroup$
1
  • $\begingroup$ How many numbers can you choose? All of them? What's the penalty/constraint? $\endgroup$ Sep 29, 2022 at 6:12

2 Answers 2

2
$\begingroup$

So this is not time series in my mind. There is no correllation between observations. In weather, if it rains tomorrow, we might imagine its more likely to rain today. This is not the case here, each observation is in random order and we could endlessly shuffle the observations and not fundemntally change the problem.

This problem could be formulated under an optimal stopping approach. The idea is you can stop early and take an action. When you do you take this early stop to maximize expected long term succcess. Think about dating as an example. Most people eventually stop early (before death) and marry therefore stopping dating.* https://en.wikipedia.org/wiki/Optimal_stopping

*exceptions apply of course.

$\endgroup$
-1
$\begingroup$

Instead of having a look at each and every number we can split the array into two equal halves. After dividing the array we can find the maximum value separately in both the halves by using recursive method and then can compare both the values and find out which is maximum. We can also write a function for recursive method and store the maximum number at an index position so it can be compared easily.

$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Oct 9, 2022 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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