Sheldon Ross 10: Example 3.25 (The best prize problem)

Question: Suppose that we are to be presented with n distinct prizes in sequence. After being presented with a prize we must immediately decide whether to accept it or reject it and consider the next prize. The only information we are given when deciding whether to accept a prize is the relative rank of that prize compared to ones already seen. That is, for instance, when the fifth prize is presented we learn how it compares with the first four prizes already seen. Suppose that once a prize is rejected it is lost, and that our objective is to maximize the probability of obtaining the best prize. Assuming that all n! orderings of the prizes are equally likely, how well can we do?


Solution: It took some time for me to approach this problem. I will be explaining the problem using the same methodology as the text but with the use of multiple steps to illustrate the solution. Let us break this problem down!!

    1. In order to get a systematic way of rejection, let us say that when the gifts are shown to us in sequence, we would be rejecting the first k and then accept the first prize that is larger than all the first k
    2. This means that we need to calculate the probability that we get the first prize when the first k are rejected (shortened as Pk{best})
      • Symbolically we can write: Pk{best} = Σi Pk{best | k = i} P{k = i}
      • As you can see, this above has 2 parts
        1. P{k = i} would be simply 1n regardless of what the i is.
        2. Pk{best | k = i} would be dependent on the i because of the following reasons
          • Consider the sequence 8 4 3 1 7 6 10 x x x 
          • We have “rejected” the ones in red and the possible best prize is 10
          • 7 and 6 have been greyed out because – after the rejection of the first four, we have not stumbled upon a prize that is greater than the first four in the value
          • The last three are irrelevant because we found a number that is larger than the rejected first four
        3. If the number 10 were to be present in the first, then we have already rejected the best prize and then Pk{best | k = i} = 0
          • We can also say this symbolically as a Pk{best | k = i} : i ≤ k
        4. If the largest number occurs much later in the sequence, the probability that ith prize is the largest is also the probability that the largest of the first i-1 prizes is is in the first rejected k.
          • If you look at the example, 10 was where we stopped and we did not find a number that is larger then the rejected sequence of 8 4 3 1
          • ⇒ Pk{best | k = i} = ki-1 when i > k. This is true since there is one best among i-1 and we have ‘k’ available slots for something being the best
    3. Bringing this altogether
      • ⇒ Σi Pk{best | k = i} P{k = i} = Σi ki-1 1n  = k Σi 1i-1 where i ranges from k+1 to n. The adjusted range is due to the fact that we ended up rejecting the first k
      • This can be written as n integral as k∫ 1x dx where k ≤ x ≤ n-1
      • Pk{best} = kn log(nk)
      • Differentiating this with respect to k, we get P`k{best} = 1n log(nk) – 1⁄n
      • and equating this to zero, we get k ≅ ne
    4. In the previous steps, we have “optimized the rejection”
    5. We now can outline the strategy for having the best odds at getting the best prize
      1. If there are “n” prizes arranged in sequence, we reject ne
      2. Then we keep going and select the first one that is better than the rejected k
      3. And the probability for this strategy is 1⁄e ≅ 0.36788 
      4. HIGH odds!! Surprising result

Simulation: We can use the power of code to generalize to many cases of rejected ‘k’ and see how out odds stand. The coding took a while for I needed to build some supporting functions to facilitate the east of rejection and the subsequent selection of the “best expected gift”

  • There have been two parts to the simulation
    • Python code for the simulation and data export
    • Mathematica for import of the files and visualization (like always)
    • I had to results of the simulation as .txt files first and then import them into mathematica for the plots and add finishing touches
      • Simulation and the export of all the (10 + 50 + 100)*2 files took close to 10 hours
      • I am using the PyCharm IDE with Anaconda Python with a custom built mathematical library that has function names similar to that of Mathematica

Reading the plots

  • The plots are not very explanatory.
    • The plot label on the top indicates how many gifts we have been presented that are all different in value
    • Each line shows the odds of getting that number. Which number is indicated by the color legend on the right side
    • The line then shows the number of times we ended up selecting the number (it indicates) as we increase the rejected number of the first shown gifts
    • Intuitively, since out strategy is to find the better one, we see that the best prize has the highest probability of being an outcome.
      • Each plot is a collection of ‘n’ curves, each representing counts vs. k for that number
      • n is also the number of gifts presented to us
      • I have repeated the process for n = 10, n = 50 and n = 100

———————-

———————-

———————-

 

———————-

———————-

———————-


NOTE : You can scroll the code horizontally when viewing in a mobile phone 

Python Code 

from mathematica.random_functions import *
from mathematica.lists import *
from mathematica.monitoring import *
from mathematica.sheldon_ross_problems.sheldon_ross_utilities import *

unknownPath = open('folderPath.txt').readlines()[0]
chapterName = 'sheldon_ross_chapter_03'
problemName = 'sheldon_ross_example_3.25'


def bestGift():
    for variableGifts in [10, 50, 100]:
        numberOfGifts = variableGifts

        for rejInd in range(0, numberOfGifts):
            __fileName = ConstructFileName([unknownPath, chapterName, problemName, problemName], '_' + str(numberOfGifts) + '_'
                                           + str(rejInd) + '.txt')
            __file = open(__fileName, 'w')

            TimeTagMessage('Opening file ' + __fileName)
            TimeTagMessage('Writing into file')

            for r in range(0, 1000000):
                randomSample = RandomSample(Range(numberOfGifts), numberOfGifts)
                rejectedIndex = rejInd
                rejectedSequence = randomSample[0:rejectedIndex]
                unRejectedSequence = randomSample[rejectedIndex:len(randomSample)]

                accepted = None
                for i in unRejectedSequence:
                    if GreaterThanAll(i, rejectedSequence):
                        accepted = i
                        break
                __file.write(str(accepted) + '\n')

            TimeTagMessage('Closing the file ' + __fileName)
            __file.close()
            print('')


def worstGift():
    for variableGifts in [10, 50, 100]:
        numberOfGifts = variableGifts

        for rejInd in range(0, numberOfGifts):
            __fileName = ConstructFileName([unknownPath, chapterName, problemName, problemName],
                                           '_worst_' + str(numberOfGifts) + '_'
                                           + str(rejInd) + '.txt')
            __file = open(__fileName, 'w')

            TimeTagMessage('Opening file ' + __fileName)
            TimeTagMessage('Writing into file')

            for r in range(0, 1000000):
                randomSample = RandomSample(Range(numberOfGifts), numberOfGifts)
                rejectedIndex = rejInd
                rejectedSequence = randomSample[0:rejectedIndex]
                unRejectedSequence = randomSample[rejectedIndex:len(randomSample)]

                accepted = None
                for i in unRejectedSequence:
                    if LessThanAll(i, rejectedSequence):
                        accepted = i
                        break
                __file.write(str(accepted) + '\n')

            TimeTagMessage('Closing the file ' + __fileName)
            __file.close()
            print('')

bestGift()
worstGift()

Mathematica Code

ClearAll[plotBestPrizeSelections];

plotBestPrizeSelections[n_: 10, worstOrBest_: "" | "worst_"] :=
 Module[{plot, fileSuffix = StringDelete[worstOrBest, "_"],
   plotLabel = 
    ToString[n] <> " gifts find " <> 
     If[worstOrBest == "", "best", "worst"]},
  plot = Module[{
     fileNames =
      SortBy[
       FileNames[
        "*3.25_" <> worstOrBest <> ToString[n] <> "_*" ~~ "*txt", 
        NotebookDirectory[]],
       ToExpression@
         Last[StringDelete[StringSplit[#, "_"], ".txt"]] &]},
    
    ListLinePlot[MapThread[#1 &,
      {Transpose[
        Parallelize[
         Module[{file = 
              StringSplit[StringReplace[Import[#], "None" -> "0"], 
               "\n"]},
            Count[file, #] & /@ ToString /@ Range[1, n]] & /@ 
          fileNames]],
       Range[1, n]}], PlotRange -> All, ImageSize -> 788, 
     PlotLegends -> Range[n],
     PlotLabel -> plotLabel]
    ];
  
  Print[plot];
  Export[StringReplace[NotebookFileName[], 
    ".nb" -> "_" <> StringReplace[plotLabel, " " -> "_"] <> ".png"], 
   plot, ImageSize -> 788, ImageResolution -> 500];
  ]

plotBestPrizeSelections[#, ""] & /@ {10, 50, 100}
plotBestPrizeSelections[#, "worst_"] & /@ {10, 50, 100}

It was really fun making this post like always. The emoticon concludes the post. 😉


.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.