Randomized Algorithms

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.''

Well ...''

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

Some More Probability

• If and are independent then

Let .

• - this is the variance. Intuitively, this tells us how concentrated is the distribution of .

• : standard deviation. (i.e., variance is inconvenient to work with because it is a squared quantity).

• .

• .

• Bernoulli distribution

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 .

• Binomial distribution

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

Also, , and .

Proof. Set . This is a positive random variable. We have by Markov inequality

Easy consequence of Chebyshev's inequality, is the following:

LazySelect - Selecting the -th element

1. - distinct elements.
2. - rank of in .
3. - -th element of .
4. We want to compute .

5. - Sample with replacement of elements from .

6. Sort .

7. , .

8. Assume that .

9. Compute the rank of and the rank of in ( comparisons).

Exercise: Show how to do this stage in (expected) comparisons.

10. If is not between and repeat the above process till success.

11. Compute (can be done while computing the rank of and ).

12. If repeat the above process till success.

13. Sort , and compute , where .

14. return .

Proof.
• - if the -th sample smaller equal to , otherwise 0.

• , .

• .

• has binomial distribution with , and parameter .

Chebyshev inequality tells us:

• , . In particular, the probability of is

• Similar analysis to bound the bad event .

• Finally, the only other possible bad event, is that is too large. Let . Arguing as above, we show that with probability at least at least were picked from the range . Namely, with probability at least the element is larger than . Similar analysis shoes that is smaller than where with same probability bound.

Thus, with probability at least .

Any deterministic selection algorithm requires comparisons, and LazySelect can be changes to require only comparisons (expected).

Sariel Har-Peled 2001-01-30