Hi,
I want to understand this concept.
http://timroughgarden.org/w17/l/l16.pdf
Somebody please guide me.
Zulfi.
I want to understand this concept.
http://timroughgarden.org/w17/l/l16.pdf
1. What is 25% probability?Specifically, when the numbers are adversarially chosen but then randomly ordered, it is easy to stop on the largest number with 25% probability: watch the first n/2 numbers go by, and stop on the first subsequent number that exceeds them all (if any). As long as the highest number is in the second half of the sequence and the second-highest number is in the first half of the sequence (with ≥ 25% probability), you are guaranteed to stop on the highest number. An optimized version of this algorithm (which looks at the first 1/e fraction of the elements) and analysis yields a success probability of ≈ 1 e ≈ 36.7% (see e.g. Wikipedia), thus yielding the “37% rule”
Somebody please guide me.
Zulfi.