\documentclass{article} \usepackage{me,wide} \parindent0pt

Basic Probability Tools

This lecture will review everything you learned in 6.042.

Deviations from Expectation

Sometimes expectation isn't enough. Want to study deviations--- probability and magnitude of deviation from expectation.

Example: coupon collection/stable marriage.

Lower bound:

Do Exact Balls in Bins here next time

Tail Bounds---Markov Inequality

At other times, don't want to get down and dirty with problem. So have developed set of bounding techniques that are basically problem independent.

Markov inequality.

Example: coupong collecting $\Pr[> tn\log n]=O(1/t)$.

Application: $ZPP=RP \cap coRP$.

Does this mean can switch Las Vegas to Monte Carlo? Yes.

Monte Carlo to Las Vegas? No, unless have checker.


Can make Markov much stronger by generalizing: $\Pr[h(Y) > t] \le E[h(Y)]/t$ for any positive $h$.

Better than Markov because uses more info: variance.

Example: coupon collecting.

Median Finding

In homework, simple randomized linear-time algorithm

Sampling idea


Exact Algorithm?


Running time:

Want to improve?

Randomized is strictly better:

Pairwise Independence

pseudorandom generators.

Pairwise independence

More bits

Generating larger numbers over $Z_p$.

Application: median

Application: conserving Random Bits