I'm trying to find an optimal item in a list. Evaluating these items is very time-consuming, and I want to go fast. I know how many items there are, and I can choose one at any time.
Given some threshold d in (0, 1], how can I calculate how many items I have to evaluate such that the best item already evaluated is the best with probability > d?
Can this bound be changed if I use a very fast heuristic to order items from "probably good" to "probably not good"?
A paper or book discussing this in detail would be great.
Assuming candidates arrive in a random order then $\lceil dn \rceil$, i.e. rounding up $dn$, seems an obvious answer since the probability the best is in the first $\lceil dn \rceil$ is $$\dfrac{\lceil dn \rceil}{n} \ge d$$
with equality if $dn$ is an integer. If you want strict inequality then $\lfloor dn \rfloor +1$