Randomized Algorithms (Spring 2010)/Balls and bins: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>WikiSysop
imported>WikiSysop
Line 12: Line 12:
=== Markov's inequality ===
=== Markov's inequality ===


=== Variance and Chebyshev's inequality ===
=== Chebyshev's inequality ===


=== The coupon collector revisited ===
=== The coupon collector revisited ===


== The <math>k</math>-Median Problem ==
== The <math>k</math>-Median Problem ==

Revision as of 07:21, 10 January 2010

Expectation

Linearity of Expectation

Balls-into-bins model

The coupon collector problem

Deviation

Markov's inequality

Chebyshev's inequality

The coupon collector revisited

The [math]\displaystyle{ k }[/math]-Median Problem