Date: January 30, 2001
``Why,'' he said, ``were all the ship's computations being done on a waiter's bill pad?''
Slartibartfast said, ``Because in space travel all the numbers are awful.''
He could tell that he wasn't getting his point across.
``Listen,'' he said. ``On a waiter's bill pad numbers dance. You must have encountered the phenomenon.''
``On a waiter's bill pad,'' said Slartibartfast, ``reality and unreality collide on such a fundamental level that each becomes the other and anything is possible, within certain parameters.''
-- Life, the Universe, and Everything, Douglas Adams
We flip a coin, get (heads) with probability , and 0 (i.e., tail) with probability . Let be this random variable. The variable is has Bernoulli distribution with parameter . Then , and .
Assume that we repeat a Bernoulli experiments times (independently!). Let be the resulting random variables, and let . The variable has the binomial distribution with parameters and . We have
Easy consequence of Chebyshev's inequality, is the following:
Exercise: Show how to do this stage in (expected) comparisons.
Chebyshev inequality tells us:
Thus, with probability at least .
Any deterministic selection algorithm requires
comparisons, and LazySelect can be changes to require only