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!!

 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
 This means that we need to calculate the probability that we get the first prize when the first k are rejected (shortened as P_{k}{best})
 Symbolically we can write: P_{k}{best} = Σ_{i} P_{k}{best  k = i} P{k = i}
 As you can see, this above has 2 parts
 P{k = i} would be simply ^{1}⁄_{n} regardless of what the i is.
 P_{k}{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
 If the number 10 were to be present in the first, then we have already rejected the best prize and then P_{k}{best  k = i} = 0
 We can also say this symbolically as a P_{k}{best  k = i} : i ≤ k
 If the largest number occurs much later in the sequence, the probability that i^{th} prize is the largest is also the probability that the largest of the first i1 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
 ⇒ P_{k}{best  k = i} = ^{k}⁄_{i1} when i > k. This is true since there is one best among i1 and we have ‘k’ available slots for something being the best
 Bringing this altogether
 ⇒ Σ_{i} P_{k}{best  k = i} P{k = i} = Σ_{i}^{ k}⁄_{i1} ^{1}⁄_{n} = ^{k}⁄_{n } Σ_{i}^{ 1}⁄_{i1}_{ }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}⁄_{n }∫ ^{1}⁄x dx where k ≤ x ≤ n1
 P_{k}{best} = ^{k}⁄_{n} log(n⁄k)
 Differentiating this with respect to k, we get P`_{k}{best} = 1⁄_{n} log(n⁄k) – 1⁄_{n}
 and equating this to zero, we get k ≅ ^{n}⁄e
 In the previous steps, we have “optimized the rejection”
 We now can outline the strategy for having the best odds at getting the best prize
 If there are “n” prizes arranged in sequence, we reject ^{n}⁄e
 Then we keep going and select the first one that is better than the rejected k
 And the probability for this strategy is 1⁄e ≅ 0.36788
 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. 😉
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.