BBy Bot
Jun 09'24

Exercise

For the task described in Exercise, it can be shown[Notes 1] that the best strategy is to pass over the first [math]k - 1[/math] candidates where [math]k[/math] is the smallest integer for which

[[math]] \frac 1k + \frac 1{k + 1} + \cdots + \frac 1{n - 1} \leq 1\ . [[/math]]

Using this strategy the probability of getting the best candidate is approximately [math]1/e = .368[/math]. Write a program to simulate Barbara Smith's interviewing if she uses this optimal strategy, using [math]n = 10[/math], and see if you can verify that the probability of success is approximately [math]1/e[/math].

Notes

  1. E. B. Dynkin and A. A. Yushkevich, Markov Processes: Theorems and Problems, trans. J. S. Wood (New York: Plenum, 1969).