1

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!

user70889
  • 313
  • 1
  • 6
AutisticRat
  • 123
  • 1
  • 6

2 Answers2

2

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.

user70889
  • 313
  • 1
  • 6
-1

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.

Azana
  • 16
  • 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](/help/how-to-answer). – Community Oct 09 '22 at 03:52